1,721,071 research outputs found
Non-commutative Gröbner bases and improvements of Buchberger\u27s algorithm
No full textNamen tega magistrskega dela je predstaviti teorijo Gröbnerjevih baz idealov v kolobarju nekomutativnih polinomov in tri glavne algoritme za njihov izračun, Buchbergerjev algoritem ter Faugèrjeva algoritma in . Začnemo pri osnovah teorije nekomutativnih polinomov, predstavimo algoritem deljenja, definiramo Gröbnerjeve baze idealov nekomutativnih polinomov in dokažemo nekaj njihovih temeljnih lastnosti. Nadaljujemo s klasičnim Buchbergerjevim algoritmom, vpeljemo pojem ovire in nato sledimo korakom Tea More do nekomutativne različice algoritma. Pri tem z Dicksonovo lemo pokažemo končnost prvotnega komutativnega Buchbergerjevega algoritma ter dokažemo nekomutativno različico Buchbergerjevega kriterija in pravilnost nekomutativnega Buchbergerjevega algoritma. Pokažemo, kako množice polinomov pretvoriti v matrike ter hkrati formuliramo komutativen in nekomutativen algoritem . Dokažemo pravilnost algoritma in pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo končnost algoritma F4. Definiramo modul vezi množice polinomov in dokažemo nekaj osnovnih lastnosti. Buchbergerjevo teorijo dvignemo v prosti modul nad kolobarjem komutativnih polinomov in definiramo polinomske podpise. Predstavimo osnovnega predstavnika družine podpisnih algoritmov ter dokažemo njegovo pravilnost in končnost. Vpeljemo kriterij in podpisni algoritem uporabimo, da formuliramo algoritem . Za konec ponovimo prejšnje korake in predstavimo podpisni algoritem za nekomutativne polinome in dokažemo pravilnost nekomutativnega algoritma . Pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo še njegovo končnost.The goal of this Master\u27s thesis is to present the theory of Gröbner bases of ideals in the ring of non-commutative polynomials, and the three main algorithms for computing them, Buchberger\u27s algorithm and Faugère\u27s and algorithms. We start with the basic theory of non-commutative polynomials, present the division algorithm, define Gröbner bases of ideals of non-commutative polynomials, and prove some of their fundamental properties. We continue with the classical Buchberger\u27s algorithm, introduce the concept of obstruction sets, and follow the steps of Teo Mora to the non-commutative version of the algorithm. Doing so, we use Dickson\u27s lemma to show that the original Buchberger\u27s algorithm terminates, and we prove the non-commutative version of Bucherger\u27s Criterion and correctness of the non-commutative version of Buchberger\u27s algorithm. We show how to transform sets of polynomials into matrices, and simultaneously formulate the commutative and non-commutative algorithm. We prove the correctness of the algorithm, and we prove it terminates if a finite Gröbner basis exists for the given ideal. For a finite set of polynomials, we define the syzygy module and prove some of its basic properties. We lift Buchberger\u27s theory into a free module over the ring of commutative polynomials and define polynomial signatures. We present the principal representative of the family of signature-based algorithms and prove its correctness and termination. We introduce the Criterion and use the signature-based algorithm to formulate the algorithm. We conclude by repeating the previous steps to arrive at a non-commutative signature-based algorithm and show the correctness of the non-commutative version of the algorithm. We prove this algorithm terminates if a finite Gröbner bases exists for the given ideal
Konveksnost v matričnih prostorih, ekstremne točke in lica
No full textThis thesis investigates the notions of exposed points and (exposed) faces in the matrix convex setting. Matrix exposed points in finite dimensions were first defined by Kriel in 2019. Here this notion is extended to matrix convex sets in infinite-dimensional vector spaces. Then a connection between matrix exposed points and matrix extreme points is established: a matrix extreme point is ordinary exposed if and only if it is matrix exposed. This leads to a Krein-Milman type result for matrix exposed points that is due to Straszewicz-Klee in classical convexity: a compact matrix convex set is the closed matrix convex hull of its matrix exposed points. Moreover, with similar techniques, an even stronger result is obtained, namely that the matrix exposed points are dense in the matrix extreme points. Several notions of a fixed-level as well as a multilevel matrix face and matrix exposed face are introduced to extend the concepts of a matrix extreme point and a matrix exposed point, respectively. Their properties resemble those of (exposed) faces in the classical sense, e.g., it is shown that the -extreme (matrix extreme) points of a matrix face (matrix multiface) of a matrix convex set are matrix extreme in . As in the case of extreme points, any fixed-level matrix face is ordinary exposed if and only if it is a matrix exposed face. From this it follows that every fixed-level matrix face of a free spectrahedron is matrix exposed. On the other hand, matrix multifaces give rise to the noncommutative counterpart of the classical theory connecting (archimedean) faces of compact convex sets and (archimedean) order ideals of the corresponding function systems. The final part of this thesis studies several generalizations of (matrix) convexity, e.g., partial convexity or biconvexity, which are summed up in the term -convexity. Here is a tuple of symmetric free polynomials determining the geometry of a -convex set. The notions of -operator systems and -ucp maps are introduced and a Webster-Winkler type categorical duality between -operator systems and -convex sets is established. Next, a notion of extreme points of -convex sets is introduced so that it extends the concept of a free extreme point. To ensure that such points exist, matrix (but also -) convex sets are extended to include an operator level. The existence of free extreme points of the operator convex hull of then guarantees existence of the so called -extreme points of an operator -convex set . This result is key to establish a Krein-Milman theorem for -convex sets. Finally, relying on the results of Helton, Klep and McCullough, a construction of an approximation scheme for the -convex hull of the matricial positivity domain of a symmetric free polynomial is given. The approximation consists of a decreasing family of -analogs of free spectrahedra, which under mild assumptions captures the -convex hull of the matricial positivity domain of .Ta disertacija raziskuje pojme izpostavljenih točk in (izpostavljenih) lic matrično konveksnih množic. Matrično izpostavljene točke v končnih dimenzijah je leta 2019 prvič definiral Kriel, v disertaciji pa je ta pojem razširjen na matrično konveksne množice v neskončno-razsežnih vektorskih prostorih. Obravnavana je korespondenca med matrično izpostavljenimi točkami in matrično ekstremnimi točkami: matrično ekstremna točka je običajna izpostavljena točka natanko tedaj, ko je matrično izpostavljena. Ta povezava vodi do rezultata tipa Krein-Milman za matrično izpostavljene točke, ki sta ga v teoriji klasične konveksnosti dokazala Straszewicz in Klee: kompaktna matrično konveksna množica je zaprta matrično konveksna ogrinjača svojih matrično izpostavljenih točk. S podobnimi tehnikami je dokazan še močnejši rezultat, namreč da so matrično izpostavljene točke goste v matrično ekstremnih točkah. V drugem delu disertacije je uvedenih več pojmov tako enonivojnih kot večnivojnih matričnih lic in matrično izpostavljenih lic, ki razširjajo pojma matrično ekstremne točke oziroma matrično izpostavljene točke. Njihove lastnosti so podobne lastnostim običajnih (izpostavljenih) lic, na primer, dokazano je, da so -ekstremne (matrično ekstremne) točke matričnega lica (večnivojnega matričnega lica) matrično konveksne množice matrično ekstremne v . Tako kot pri ekstremnih točkah je vsako enonivojno matrično lice izpostavljeno natanko tedaj, ko je matrično izpostavljeno lice. Iz tega sledi, da je vsako matrično lice prostega spektraedra na fiksnem nivoju matrično izpostavljeno. Po drugi strani pa večnivojna matrična lica privedejo do nekomutativnega ekvivalenta klasične teorije, ki povezuje (arhimedska) lica kompaktnih konveksnih množic in arhimedske ureditvene ideale pripadajočih funkcijskih sistemov. Zadnji del disertacije preučuje več posplošitev (matrične) konveksnosti, kot sta na primer parcialna konveksnost ali bikonveksnost. Te posplošene oblike konveksnosti so združene v izraz -konveksnost. Pri tem je terica simetričnih prostih polinomov, ki določajo geometrijo -konveksne množice. Uvedeni so pojmi -operatorskih sistemov in unitalnih Γ-povsem pozitivnih preslikav, vzpostavljena je kategorična dualnost tipa Webster-Winkler med -operatorskimi sistemi in -konveksnimi množicami. V nadaljevanju je predstavljen pojem ekstremnih točk -konveksnih množic, in sicer na tak način, da razširja koncept proste ekstremne točke. Da bi zagotovili obstoj takih točk, so matrično (pa tudi -) konveksne množice razširjene tako, da vključujejo operatorski nivo. Obstoj prostih ekstremnih točk operatorsko konveksne ogrinjače nato zagotavlja obstoj tako imenovanih -ekstremnih točk operatorsko -konveksne množice . Ta rezultat je ključen za dokaz Krein-Milman izreka za -konveksne množice. Nazadnje je na podlagi rezultatov Heltona, Klepa in McCullougha podana konstrukcija aproksimacijske sheme za -konveksno ogrinjačo matrične domene pozitivnosti simetričnega prostega polinoma . Aproksimacija je sestavljena iz padajoče družine -analogov prostih spektraedrov in ob blagih predpostavkah zajame -konveksno ogrinjačo matrične domene pozitivnosti
Matrix invariants and trace identities
Get PDFV delu obravnavamo invariante -teric matrik glede na hkratno konjugacijo. Pokažemo, da je vsako invarianto možno zapisati z matričnimi sledmi. Obravnavamo tudi konkomitante in pokažemo, da so kot algebra nad invariantami generirane s projekcijami na . Vpeljemo polinome s sledmi in centralne polinome s sledmi. Prvi služijo zapisu konkomitant, drugi pa zapisu invariant. Spoznamo tudi identitete s sledmi in centralne identitete s sledmi, tj. polinome, ki določajo ničelno konkomitanto oziroma invarianto. Pokažemo, da je vsaka identiteta posledica Cayley-Hamiltonovega izreka.We consider invariants of -tuples of matrices under simultaneous conjugation. We show that any invariant can be expressed using the trace. We also consider concomitants and describe them as an algebra over the invariants generated by the projections on . For the purpose of describing invariants and concomitants we introduce trace polynomials. We consider trace identities, i.e. trace polynomials describing the zero invariant or concomitant. We show that any identity is a consequence of the Cayley-Hamilton theorem
NONNEGATIVE MATRICES
Get PDFDiplomsko delo je sestavljeno iz štirih poglavij.
Prvo poglavje je namenjeno ponovitvi osnovnih pojmov matrik. V drugem poglavju so predstavljene nenegativne matrike s poudarkom na Perron-Frobeniusovem izreku, ki opisuje lastne vrednosti in lastne vektorje kvadratnih nenegativnih matrik. Kot poseben primer nenegativnih matrik so opisane stohastične matrike.
V zadnjih dveh poglavjih pa predstavimo povezavo nenegativnih matrik z M-matrikami in posplošenimi permutacijskimi matrikami.The thesis includes four chapters.
The first chapter serves as an overview of the basic phrases from the field of matrices. The second chapter introduces nonnegative matrices with an emphasis on the Perron-Frobenius theorem, which describes eigenvalues and eigenvectors of nonnegative square matrices. As a special example of nonnegative matrices the thesis also describes stohastic matrices.
The last two chapters demonstrate the connection between nonnegative matrices and M-matrices as well as generalized permutation matrices
Nekomutativne racionalne invariante
No full textRational functions in variables over a field are actual (partial) functions from to that can be formed using coordinate functions and rational operations (addition, scalar multiplication, multiplication, inversion). Such functions form a field. Noncommutative rational functions in variables over are partial functions from -tuples of equally sized square matrices over to matrices of the same size that can be formed using coordinate functions and rational operations. Such functions form a skew-field where every relation between the variables follows from the existence of inverses of nonzero elements, hence, the skew-field of noncommutative rational functions is also called a free skew-field. One of the major problems of invariant theory is Noether’s problem – given an action of a finite group on a field of rational functions, is the field of invariant functions isomorphic to a field of rational functions? In the thesis, we investigate a noncommutative version of Noether’s problem – given an action of a finite group on a free skew-field, is the skew-field of invariant functions free, i.e., isomorphic to a free skew-field? We study the actions of finite abelian groups on the free skew-field over and that are given by linear representations and show that their invariant skew-subfields are always free. We define complete representations – a type of linear representation of solvable groups that admit an inductive extension of the result for linear actions of abelian groups. For example, the standard representations of the symmetric groups and are complete. We also investigate so-called multiplicative actions of finite cyclic groups – actions that are defined by an automorphism of a free group and show that they are equivalent to linear actions. We give some interesting examples of invariants of cyclic groups over and invariants of the general linear group. The last part of the thesis is more group theoretic. We give an alternative characterisation of the groups that admit complete representations and name them totally pseudo-unramified groups. We present some group theoretic properties of totally pseudo-unramified groups and classify totally pseudo-unramified -groups of rank up to five.Racionalne funkcije v spremenljivkah nad poljem so delne funkcije iz v , ki jih lahko izrazimo s koordinatnimi funkcijami (spremenljivkami) in racionalnimi operacijami (seštevanje, množenje, deljenje). Nekomutativne racionalne funkcije v spremenljivkah nad so delne funkcije, ki slikajo iz -teric kvadratnih matrik iste velikosti v kvadratne matrike, ki jih lahko izrazimo s koordinatnimi funkcijami in racionalnimi operacijami. Take funkcije tvorijo obseg, v katerem je vsaka relacija med spremenljivkami posledica obstoja inverzov neničelnih elementov, zato obseg nekomutativnih racionalnih funkcij imenujemo tudi prosti obseg. Eden glavnih problemov teorije invariant je problem Emmy Noether – ali je, za dano delovanje končne grupe na prosto polje, polje invariant izomorfno prostemu polju? V disertaciji obravnavamo nekomutativno različico problema Emmy Noether – ali je, za dano delovanje končne grupe na prost obseg, obseg invariant izomorfen prostemu obsegu? Preučujemo delovanja končnih abelovih grup na proste obsege nad in , ki so določena z linearnimi upodobitvami. Pokažemo, da je obseg njihovih invariant vedno prost. Definiramo kompletne upodobitve – družino linearnih upodobitev rešljivih grup, ki omogočajo induktivno razširitev rezultata o delovanjih abelovih
grup. Primera kompletnih upodobitev sta standardni upodobitvi simetričnih grup in . Obravnavamo tudi multiplikativna delovanja končnih cikličnih grup – delovanja, ki so določena z avtomorfizmom proste grupe. Predstavimo nekaj zanimivih primerov invariant cikličnih grup nad in invariant splošne linearne grupe. V zadnjem delu disertacije obravnavamo grupe, ki imajo kompletne upodobitve – imenujemo jih popolnoma psevdo-nerazvejane grupe. Predstavimo lastnosti popolnoma psevdo-nerazvejanih grup in karakteriziramo popolnoma psevdo-nerazvejane -grupe ranga največ pet
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Elementary equivalence of valued fields and Ax-Kochen-Eršov theorem
Get PDFValuacija je homomorfizem, ki slika multiplikativno grupo obrnljivih elementov polja v urejeno abelovo grupo. Če valuacija slika v aditivno grupo celih števil, je diskretna. Chevalleyev izrek nam pove, da lahko vsako valuacijo polja razširimo tudi na nadpolja. Če za vsako algebraično razširitev polja z valuacijo obstaja natanko ena razširitev valuacije, pravimo, da je polje Henselovo. Primeri Henselovih
polj so polna polja z diskretno valuacijo.
Dve strukturi v jeziku sta elementarno ekvivalentni natanko tedaj, ko vsak stavek v tem jeziku velja v eni natanko tedaj, ko velja v drugi. Vse izomorfne strukture so elementarno ekvivalentne, obratno pa v splošnem ne velja. Izrek Ax-Kochen-Jeršov za pare Henselovih polj z valuacijo natančno pove, kdaj so elementarno ekvivalentni. Po njegovi posledici vsak stavek velja v polju -adičnih števil za skoraj vsa praštevila p natanko tedaj, ko velja v polju Laurentovih vrst za skoraj vsa praštevila .A valuation on a field is a homomorphic mapping from the multiplicative group of invertible elements of a field into an ordered abelian group. If it maps into the additive group of integers, it is called discrete. By Chevalley’s theorem, every valuation on a field extends to any field extension. Henselian valued fields are those for which valuation extends uniquely to any algebraic field extension. For example, complete discrete valued fields are Henselian.
Two structures of a given language are elementary equivalent if and only if every sentence in this language holds in the first structure if and only if it also holds in the second. All isomorphic structures are elementary equivalent, but the converse is not true in general. The Ax-Kochen-Eršov theorem explains when any two Henselian valued fields are elementary equivalent. As a consequence, a sentence holds in the field of -adic numbers for almost all primes if and only if it holds in the field of Laurent series for almost all primes
The Krein-Milman theorem for matrix convex sets
Get PDFTeorijo konveksnih množic v Evklidskih prostorih lahko na naraven način prestavimo v nekomutativno okolje matričnih prostorov.
V magistrski nalogi predstavimo matrične konveksne množice, njihove lastnosti in primere, obravnavamo matrične ekstremne točke in vpeljemo matrične izpostavljene točke. Poskušamo pa tudi razumeti, v kolikšni meri rezultati v matričnem svetu spominjajo na tiste iz klasične teorije, med katere sodi tudi Krein-Milmanov izrek. Kot sredstvo za dokaz matrične ustreznice Krein-Milmanovega izreka razložimo tudi Hahn-Banachov izrek za matrične konveksne množice.The theory of convex sets in Euclidean spaces can be in a natural way transferred to the noncommutative setting of matrix spaces. In this master\u27s thesis we discuss matrix convex sets, their properties and examples, we deal with matrix extreme points and introduce matrix exposed points. We also aspire to understand how much the results in the matrix world resemble those from the classical theory, such as the Krein-Milman theorem. As a device to prove the matricial analogue of the Krein-Milman theorem we explain the Hahn-Banach theorem for matrix convex sets
- …
