Search

The inverse eigenvalue problem of a graph $G$ is the problem of characterizing all lists of eigenvalues of real symmetric matrices whose off-diagonal pattern is prescribed by the adjacencies of $G$. The strong spectral property is a powerful tool in this problem, which identifies matrices whose entries can be perturbed while controlling the pattern and preserving the eigenvalues. The Matrix Liberation Lemma introduced by Barrett et al.~in 2020 advances the notion to a more general setting. In this paper we revisit the Matrix Liberation Lemma and prove an equivalent statement, that reduces some of the technical difficulties in applying the result. We test our method on matrices of the form $M=A \oplus B$ and show how this new approach supplements the results that can be obtained from the strong spectral property only. While extending this notion to the direct sums of graphs, we discover a surprising connection with the zero forcing game on Cartesian products of graphs. Throughout the paper we apply our results to resolve a selection of open cases for the inverse eigenvalue problem of a graph on six vertices.

Delo obravnava algebraično strukturo polkolobarja z dodatno pozornostjo dano na posebni primer dioida. Množica $R$ je polkolobar za binarni notranji operaciji $oplus$ in $otimes$, če je $(R,oplus)$ komutativen monoid z enoto $0$, $(R,otimes)$ monoid z enoto $1$, med $otimes$ in $oplus$ velja leva ali desna distributivnost ter velja, da $0$ izniči $otimes$, torej ⠀$forall a in R a otimes 0 = 0otimes a = 0$. Če je $(R,oplus)$ poleg tega še delno urejen s kanonično relacijo $le$, polkolobarju $(R,oplus,otimes)$ pravimo dioid. Tako pojem dioida kot pojem polkolobarja obstajata že nekaj časa in mnogo klasičnih vprašanj v povezavi s temi strukturami, s stališča linearne algebre, že ima odgovore. V nalogi bodo obravnavana zgolj osnovna izmed teh. Obravnavana vprašanja so predvsem centrirana na lastnostih polkolobarjev in dioidov ter posplošitvah konceptov iz klasične linearne algebre nad polji, kot so obstoj in lastnosti baz $R$-polmodula nad polkolobarjem $R$, lastnosti in obrnljivost matrik nad polkolobarjem $R$ ter Cayley-Hamiltonov izrek. This paper discusses the algebraic structure of a semiring, with additional attention given to the special case of a dioid. The set $R$ is a semiring for the binary internal laws $oplus$ and $otimes$ if $(R,oplus)$ is a commutative monoid with the neutral element $0$, $(R,otimes)$ is a monoid with the neutral element $1$, $otimes$ is left- or right-distributive with respect to $oplus$ and if $0$ is absorbing for $otimes$, i. e. $forall a in R a otimes 0 = 0otimes a = 0$. If additionally $(R,oplus)$ is also ordered with the canonical order relation $le$, we instead call $(R,oplus,otimes)$ a dioid. Both terms have existed for some time now and most of the classical questions relating to the structures, from the perspective of linear algebra, have already been answered. From among those, this paper will present some of the more elementary results. In particular, the focus will be on properties of semirings and dioids and on generalizations of concepts from classical linear algebra over fields such as the existence and properties of bases of an $R$-semimodule, the properties and invertibility of a matrix over a semiring $R$ and the Cayley-Hamilton theorem.

Rational functions in $d$ variables over a field ${mathbb F}$ are actual (partial) functions from ${mathbb F}^d$ to ${mathbb F}$ that can be formed using coordinate functions and rational operations (addition, scalar multiplication, multiplication, inversion). Such functions form a field. Noncommutative rational functions in $d$ variables over ${mathbb F}$ are partial functions from $d$-tuples of equally sized square matrices over ${mathbb F}$ 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 ${mathbb C}$ and ${mathbb R}$ 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 $S_3$ and $S_4$ 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 ${mathbb Q}$ 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 $p$-groups of rank up to five. Racionalne funkcije v $d$ spremenljivkah nad poljem ${mathbb F}$ so delne funkcije iz ${mathbb F}^d$ v ${mathbb F}$, ki jih lahko izrazimo s koordinatnimi funkcijami (spremenljivkami) in racionalnimi operacijami (seštevanje, množenje, deljenje). Nekomutativne racionalne funkcije v $d$ spremenljivkah nad ${mathbb F}$ so delne funkcije, ki slikajo iz $d$-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 ${mathbb C}$ in ${mathbb R}$, 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 $S_3$ in $S_4$. 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 ${mathbb Q}$ 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 $p$-grupe ranga največ pet.

We determine the upper and lower bound for possible values of Kendall's tau of a bivariate copula given that the value of its Spearman's footrule or Gini's gamma is known, and show that these bounds are always attained. Mathematics Subject Classification (2020). 62H20, 62H05, 60E05.

V diplomskem delu je predstavljen kolobar Int$(mathbb{Z})$, ki ga sestavljajo polinomi z racionalnimi koeficienti, ki za cela števila zavzemajo celoštevilske vrednosti. Ta kolobar ima drugačne lastnosti kot večina kolobarjev, ki jih preučujemo v komutativni algebri. Največ pozornosti smo posvetili dejstvu, da ima kolobar polinomov s celoštevilskimi vrednostmi lastnost dveh generatorjev. Znani dokazi te lastnosti so precej zapleteni, saj uporabljajo močne topološke argumente. V tem delu je predstavljen konstruktivni dokaz, ki uporablja osnovna algebraična orodja. Za lažje razumevanje smo definirali pojme, kot so kolobar, ideal, noetherski kolobar in Prüferjeva domena. Za pomoč pri dokazu lastnosti dveh generatorjev smo uporabili razširjen Evklidov algoritem, Skolemovo lastnost karakterizacije idealov z njihovimi ideali vrednosti ter druge potrebne trditve in leme. Skozi celotno diplomsko delo kolobar polinomov s celoštevilskimi vrednostmi primerjamo s kolobarjem polinomov s celoštevilskimi koeficienti in opisane lastnosti ponazorimo z zgledi. In this thesis we introduce the ring Int$(mathbb{Z})$, which consists of polynomials with rational coefficients that take integer values for integers. This ring has different properties from most of the rings studied in commutative algebra. We have focused on the fact that the polynomial with integer values has the property of two generators. The known proofs of this property are rather complicated, since they use strong topological arguments. In this paper we present a constructive proof that uses basic algebraic tools. For a better understanding, we define notions such as the ring, the ideal, Noethererian ring and the Pr ̈ufer domain. For the proof of the two-generator property, we have used the extended Euclidean algorithm, the Skolem property of characterising ideals by their ideals of values, and other necessary assertions and lemmas. Throughout the thesis, we compare the polynomial ring with integer values with the polynomial ring with integer coefficients and illustrate the described properties with examples.

V tem seminarskem delu definiramo nekaj osnovnih pojmov univerzalne algebre, kot so algebre, izrazi in raznoterosti. Definiramo pojem interpretacije. Uvedemo mreže, verige in Heytingove algebre ter dokažemo nekaj preprostejših dejstev o mrežah in operacijah na njih. Končno dokažemo, da so vse interpretacije omejenih distributivnih mrež v podrazred Heytingovih algeber, sestavljen iz verig, bodisi trivialne bodisi dualne. In this seminar paper, we introduce some basic concepts of universal algebra such as algebras, terms, and varieties. We define interpretations. Also, we define lattices, chains, and Heyting algebras, and procede to prove some simple facts about lattices and operations on lattices. Finally, we prove that all interpretations of bounded distributive lattices into the subclass of Heyting algebras which consists of chains, are either trivial or dual.

Za dano drevo $T$ se lahko vprašamo, ali lahko določimo vse možne spektre matrik, ki jih lahko priredimo drevesu $T$. Najmanjše možno število različnih lastnih vrednosti med spektri matrik, ki pripadajo drevesu $T$, označimo s $q(T)$. S pomočjo kombinatoričnih lastnosti danega drevesa lahko dobimo spodnjo mejo za parameter $q(T)$. Pomemben izrek na tem področju, ki sta ga razvila Parter in Wiener, pove, kako se večkratnost lastne vrednosti obnaša, če pripadajoči matriki izbrišemo istoležno vrstico in stolpec. Zanimalo nas bo tudi, kakšna je povezava med inverznim problemom lastnih vrednosti in vsemi možnimi urejenimi seznami večkratnosti. Uporabo dobljenih rezultatov bomo sproti predstavili na številčnih primerih. An important problem is to characterize all possible eigenvalues over all symmetric matrices corresponding to a given tree $T$. The minimum number of distinct eigenvalues over this family of symmetric matrices, is denoted by $q(T)$. Using combinatorial properties of tree $T$, we are able to construct a lower bound for the parameter $q(T)$. A theorem developed by Parter and Wiener ensures the existence of a principal submatrix, in which the multiplicity of a non-simple eigenvalue is increased. This could be used for a partial solution to the inverse eigenvalue problem for a tree and resolving possible ordered multiplicity lists. We will present the application of the obtained results on numerous examples throughout the work.

Naj bosta $g, h$ naključno izbrana elementa permutacijske grupe $S_n$. Ob predpostavki, da $g, h$ generirata $S_n$, pokažemo, da velja ${rm diam}({rm Cay}(S_n, {g, h, g^{-1}, h^{-1}})) leq O(n^2(log n)^c)$ z verjetnostjo $1- o(1)$ za neko konstanto $c$. Pri tem dokaz naslonimo na dejstvo, da imajo Schreierjevi grafi množice $r$-teric različnih števil iz ${1, 2,ldots, n}$ glede na množico $d$ naključnih permutacij iz $S_n$ skoraj gotovo dobre ekspanzivne lastnosti, kar tudi dokažemo. Let $g, h$ be a random pair of elements of the permutation group $S_n$. Under the assumption that $g, h$ generate $S_n$, we show that ${rm diam}({rm Cay}(S_n, {g, h, g^{-1}, h^{-1}})) leq O(n^2(log n)^c)$ with probabilty $1-o(1)$ for some constant $c$. We base our proof on the fact that Schreier graphs on the set of $r$-tuples of distinct elements of ${1, 2,ldots, n}$ with respect to the set of $d$ random permutations are almost always good expanders, which we also prove.

Najprej bomo definirali tenzorje v vsej splošnosti in spoznali nekaj operacij z njimi.Nato bomo naše zanimanje zožili na poseben tip tenzorjev (tenzorje drugega reda)in opazovali njihove lastnosti. Potem se bomo osredotočili na eno vrsto funkcij in preslikav, ki slikajo iz prostora tenzorjev in jim pravimo izotropične funkcije oziroma preslikave. Na koncu pa bomo preko skalarnih, vektorskih in tenzorskih polj spoznali še integralske izreke kot posplošitev rezultatov iz vektorske analize. First, we will define tensors in all generality and define some operations with them. Then we will focus on special kinds of tensors, called tensors of second order, and observe their properties. Later we are going to study special functions mapping from tensor spaces, called isotropic functions. At the end, we will define scalar, vector and tensor fields, and prove some integral theorems.

Definirali bomo relacijo leve ekvivalence na matrikah, katerih elementi pripadajo nekemu glavnemu kolobarju. Poiskali bomo Hermitovo normalno formo in obravnavali njene posledice. We will define the left equivalence relation on matrices whose elements belong to a principal ideal ring. We will find the Hermite normal form and explore some of its consequences.

Hilbertov izrek o ničlah tvori osnovo algebraične geometrije. V delu izpeljemo analogno trditev za realna števila – realni izrek o ničlah. Nato vpeljemo posplošitev pojma realnosti na nekomutativne kolobarje. Dokažemo korespondenco med ideali v kolobarju realnih polinomov in kolobarju kvaternionskih polinomskih funkcij. S tem rezultatom prevedemo kvaternionski izrek o ničlah na realnega. Na koncu podamo znane posplošitve in nadaljnje smeri obravnave. Hilbert’s Nullstellensatz forms the basis of algebraic geometry. In this paper we derive an analogous statement over the field of real numbers – the real Nullstellensatz. After that we introduce a generalization of real rings to the noncommutative setting. We prove a correspondence of ideals in the ring of real polynomials with the ideals in the ring of quaternionic polynomial functions. With this result we reduce the quaternionic Nullstellensatz to the real one. Finally, we state known generalizations and some further courses of study.

V diplomski nalogi dokažemo, da pri mešanju z naključnimi transpozicijami pride do odreza ob času $frac{1}{2}nlog{n}$. Pri dokazu zgornje meje odreza uporabimo nekomutativno Fourierovo transformacijo, za njeno uporabo pa predstavimo teorijo upodobitev končnih grup s posebnim poudarkom na simetrične grupe. Klasificiramo Spechtove module in pokažemo, da standardni politabloidi tvorijo njihove baze. Spodnjo mejo odreza dokažemo z verjetnostnimi metodami. Predstavimo tudi nekaj nadaljnjih primerov odreza pri sprehodih po grupah. In this thesis we prove that in the case of random transposition shuffling cutoff occurs at time $frac{1}{2}nlog{n}$. The upper bound is proved using noncommutative Fourier transform. To understand it representation theory of finite groups is presented with emphasis on symmetric groups. Specht modules are classified and it is shown that standard polytabloids form their bases. Lower bound is proved using methods from probability. We also discuss some further examples of cutoff for random walks on groups.

Naj bo $f(x,y,z)$ multilinearen nekomutativen polinom tretje stopnje. Slika polinoma $f$ v matrični algebri $M_d(mathbb{C})$ je vektorski prostor za vsak $d in mathbb{N}$. Let $f(x,y,z)$ be a multilinear noncommutative polynomial of degree three. The image of $f$ in the matrix algebra $M_d(mathbb{C})$ is a vector space for every $d in mathbb{N}$.

Najprej se seznanimo s tropskim polkolobarjem, polinomi nad tropskim polkolobarjem in tropskimi matrikami. Glavna tema je simetrični Barvinokov rang, eden izmed mnogih možnih rangov tropskih matrik. Preučimo matrike z rangom $1$ in tiste z neskončnim rangom ter si ogledamo transformacijo matrik, ki ohranja rang. Poiščemo tudi zgornjo mejo za simetrični Barvinokov rang, pri čemer ugotovimo, da rang lahko preseže velikost matrike. Pri obravnavi ranga si pomagamo tudi s teorijo grafov in na ta način zgornjo mejo še nekoliko izboljšamo. Teorijo grafov uporabimo tudi pri obravnavi primera matrike z rangom, večjim od njene velikosti. First we get familiar with the tropical semiring, polynomials over tropical semiring and tropical matrices. The main theme is the symmetric Barvinok rank, one of the many possible ranks of tropical matrices. We examine matrices with rank $1$ and those with infinite rank and look at the transformation of matrices that preserve rank. We also find the upper bound for the symmetric Barvinok rank, noting that the rank can exceed the size of the matrix. When dealing with rank, we also use graph theory to improve the upper limit a bit. Graph theory is also used to consider an example of a matrix with a rank greater than its size.

V diplomski nalogi je formuliran algoritem za iskanje lastnih vrednosti in lastnih vektorjev brez uporabe determinante. Za algoritem je ključno razumevanje linearne neodvisnosti oziroma odvisnosti, zato je v delu to temeljito opisano. Definirali smo lastne vrednosti, lastne vektorje, matrični polinom, minimalni polinom matrike, minimalni polinom vektorja glede na matriko in v povezavi s temi pojmi navedli trditve, ki so nam pomagale pri konstrukciji algoritma. Postopek za iskanje lastnih vrednosti in vektorjev smo skozi delo gradili postopoma. Najprej smo ga uporabili na nedefektnih matrikah. Nato smo si pogledali še definicijo defektnih matrik, korenskih lastnih vektorjev, Jordanovo verigo korenskih lastnih vektorjev in trditve v povezavi z njimi. Skozi celotno diplomsko nalogo so nova dognanja uporabljena na primerih. Na koncu smo zapisali celoten univerzalen algoritem, ne glede na začetno matriko. In this bachelor thesis we formulate the algorithm for finding eigenvalues and eigenvectors without the use of determinant. For the algorithm to work, the understanding of linear independance and dependance is crucial, that is why we chose to present these two principles in more detail. We defined eigenvalues, eigenvectors, matrix polynomial, minimal polynomial of the matrix, and minimal polynomial of a vector with respect to matrix. These definitions and theorems helped us to construct our algorithm. We built our method step-by-step through our bachelor thesis. First, we used it on non defective matrices. Then we defined defective matrices, generalized vectors and Jordan chain of generalized eigenvectors. Throughout the thesis, examples are used to show what we have discovered till then. In the end, we formulated the whole universal algorithm, which works no matter what kind of the matrix we start with.

Naloga se ukvarja s tenzorskimi produkti in njihovo uporabo pri študiju algeber. Predvsem se osredotočimo na centralne enostavne algebre. Iz lastnosti tenzorskega produkta na takih algebrah sledijo mnogi zanimivi izreki. The thesis deals with tensor products and their applications in studying algebras. We mainly focus on central simple algebras. Many interesting theorems follow from the properties of tensor products of such algebras.

Cilj tega diplomskega dela je predstaviti reprezentacijo Banachovih mrež s krepko enoto s prostori funkcij C(K) na kompaktnih topoloških prostorih K. V ta namen je vpeljan pojem Boolove algebre in dokazan Stoneov reprezentacijski izrek, ki služi kot močno orodje pri reprezentaciji Banachovih mrež. Nato je definiran Rieszov prostor, ki je vektorski prostor in hkrati mreža. Dokazanih je nekaj osnovnih lastnosti Rieszovih prostorov. Vpeljani so pojmi ideala, pasu, glavne projekcijske lastnosti, komponent pozitivnega vektorja in polnosti. Brez dokaza je naveden Freudenthalov spektralni izrek. Na koncu je dokazan glavni izrek, ki pravi, da je vsaka Banachova mreža s krepko enoto Rieszovo izomorfna nekemu prostoru funkcij C(K). The aim of this thesis is to introduce the representation of Banach lattices with a strong unit by function spaces C(K) on compact topological spaces. To this end, the notion of Boolean algebra is introduced and Stone’s representation theorem is proven, which serves as a powerful tool in representation of Banach lattices. The Riesz space is defined, which is both a vector space and a lattice. After that, some basic properties of Riesz spaces are shown and the notions of the ideal, band, principal projection property, components of a positive vector and completeness are introduced. Freudenthal’s spectral theorem is stated without proof. In the end, the main theorem is proven, which states that every Banach lattice with a strong unit is Riesz isomorphic to some function space C(K).

Za kolobar $R$ definiramo komutirajoči graf $Gamma(R)$ kot graf, v katerem so vozlišča necentralni elementi kolobarja $R$, dve vozlišči pa sta povezani natanko tedaj, ko pripadajoča elementa komutirata v $R$. Pokažemo, da je za kolobarje matrik nad poljem in $n ge 3$, komutirajoči graf $Gamma (M_n(F))$ povezan natanko tedaj, ko ima vsaka $F$-razširitev stopnje $n$ pravo vmesno polje. Nadalje pokažemo, da je $Gamma (M_n(mathbb{Q}))$ nepovezan $n ge 2$. Dokažemo, da če je $Gamma (M_n(F)))$ povezan, potem je njegov premer vsaj 4 in največ 6. Poiščemo nekaj primerov komutirajočih grafov s premerom 4. Dokažemo še, da če je $F$ končno polje in $n$ ni praštevilo ali kvadrat praštevila, je ${rm diam},Gamma (M_n(F)) le 5$. We define the commuting graph of ring $R$ as the graph $Gamma(R)$ in which vertices are non-central elements of ring $R$. Two vertices are adjacent if and only if the corresponding elements commute in $R$. We show that for the ring of matrices over a field where $n ge 3$ the commuting graph $Gamma (M_n(F))$ is connected if and only if for every $F$-extension of degree $n$ exists a proper intermediate field. We also show that $Gamma (M_n(mathbb{Q}))$ is not connected for $n ge 2$. We prove that if $Gamma (M_n(F))$ is connected then $4 le {rm diam},Gamma (M_n(F)) le 6$. We find some examples of commuting graphs with diameter 4. We also prove that ${rm diam},Gamma (M_n(F)) le 5$ if $F$ is a finite field and $n$ is not a prime nor square of a prime.

Namen 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 $F_4$ in $F_5$. 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 $F_4$. Dokažemo pravilnost algoritma $F_4$ 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 $F_5$ in podpisni algoritem uporabimo, da formuliramo algoritem $F_5$. Za konec ponovimo prejšnje korake in predstavimo podpisni algoritem za nekomutativne polinome in dokažemo pravilnost nekomutativnega algoritma $F_5$. Pod pogojem, da za dani ideal obstaja končna Gröbnerjeva baza, dokažemo še njegovo končnost. The goal of this Master's 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's algorithm and Faugère's $F_4$ and $F_5$ 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's 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's lemma to show that the original Buchberger's algorithm terminates, and we prove the non-commutative version of Bucherger's Criterion and correctness of the non-commutative version of Buchberger's algorithm. We show how to transform sets of polynomials into matrices, and simultaneously formulate the commutative and non-commutative $F_4$ algorithm. We prove the correctness of the $F_4$ 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's 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 $F_5$ Criterion and use the signature-based algorithm to formulate the $F_5$ 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 $F_5$ algorithm. We prove this algorithm terminates if a finite Gröbner bases exists for the given ideal.

Diplomska naloga se ukvarja s friznimi grupami. Na Evklidski ravnini, opremljeni z Evklidsko metriko, definira množico vseh izometrij, nato pa obravnava najpreprostejše primere le-teh (to so translacija, rotacija in zrcaljenje). S pomočjo kompozitumov translacij, rotacij in zrcaljenj nato predstavi tudi vse frizne grupe. Cilj diplomske naloge je opisati (klasificirati) frizne grupe ter dokazati, da jih je, geometrijsko gledano, natanko sedem. The diploma thesis deals with frieze groups. In the Euclidean space under the Euclidean metric, it defines the set of all isometries and then deals with the most basic cases of such isometries (them being translation, rotation and reflection). Using compositions of translations, rotations and reflections, it then presents all the frieze groups. The goal of the diploma thesis is to classify frieze groups and prove that there are exactly seven geometrically different types of them.

Delo obravnava inverzni problem lastnih vrednosti nenegativnih matrik manjših dimenzij. Nanaša se predvsem na članek A. M. Nazarija in Sherafata z naslovom On the inverse eigenvalue problem for nonegative matrices of order two to five. Obravnavamo problem do dimenzije 5x5 s trditvami in njihovimi dokazi, hkrati pa tudi sestavimo pravila oz. pogoje s katerimi pridemo do matrik večjih dimenzij in možnih začetkov trditev za te dimenzije. Z dokazi tudi pridemo do preprostih nastavkov, če želimo iz danih lastnih vrednosti, ki upoštevajo pogoje, priti takoj do nenegativne matrike. V dokazih matrike sestavimo s trditvijo o konstrukciji, ki je tudi razložena v delu. The work focuses on the inverse eigenvalue problem for nonnegative matrix of smaller dimensions with its main source being a research article by A. M. Nazari and F. Sherafat titled On the inverse eigenvalue problem for nonnegative matrices of order two to five. We study the problem of dimensions for up to 5x5 with corresponding thesis and proof. Simultaneously we also try to find conditions with which we can address problems of bigger dimensions and possible sources for claims for those dimensions. With proofs we also get matrix “models” if we want to quickly find the possible nonnegative solution for the given values. We create the matrix using the newer claim of construction, that is also explained.

Diplomska naloga se osredotoča na potence pozitivnih matrik. Te so tesno povezane z lastnimi vrednostmi in lastnimi vektorji matrik, zato delo razloži postopek za njihovo računanje in lastnosti matrik v povezavi z njimi. Na podlagi Jordanove kanonične forme je v delu razložen preprostejši postopek za računanje potenc in hkrati tudi drugih funkcij matrik. Razložene so tudi lastnosti potenc stohastičnih oziroma verjetnostnih matrik. Osrednja izreka dela sta Perron-Frobeniusov in Perronov izrek. Prvi razloži lastnosti pozitivnih matrik, ki jih nato drugi uporabi pri računanju limit zaporedja potenc pozitivnih matrik. Vse preučeno je na koncu uporabljeno na primerih iz realnega življenja, kjer lahko vidimo uporabnost potenc pozitivnih matrik in razlog zakaj smo to temo sploh preučevali. The thesis focuses on powers of positive matrices. They are closely related to eigenvalues and eigenvectors of said matrices. For this reason the thesis explains the procedure for calculating eigenpairs and their characteristics. On the basis of Jordan normal form the thesis explains a simpler way of calculating powers of matrices and also other matrix functions. It also explains the characteristics of powers of stochastic or probability matrices. The centre theorems of this thesis are Perron-Frobenius and Perron theorem. The first focuses on characteristics of positive matrices, which then the second uses to compute limits of sequences of powers of positive matrices. Everything we learn is then used in examples from real life, where we can see the usefulness of powers of positive matrices and the reason we started studying them in the first place.

V delu karakteriziramo kvadratne idempotentne ničelno-neničelne matrike z elementi iz množice ${0, ast}$. Da bi identificirali vse take matrike, ta problem prevedemo na iskanje kvadratnih binarnih matrik nad poljem realnih števil, ki ta problem rešijo. Nato določimo največje število možnih neničelnih elementov v idempotentni ničelno-neničelni matriki z danim rangom. We first characterize square idempotent zero-nonzero patterns with elements from ${0, ast}$. To identify these matrices, we convert this problem into characterizing square binary idempotent matrices over the real numbers. Next we determine maximal possible number of nonzero entries in indempotent zero-nonzero pattern with a given minimum rank.

Normalnost matrik je ena od bolj zanimivih poglavij linearne algebre. Ne samo zato, ker imajo normalne matrike razmeroma preprosto definicijo, ampak tudi zato, ker so uporabne v praksi, kar je razlog, da je bilo odkritih že $89$ karakterističnih lastnosti normalnih matrik. V tem delu smo si izbrali $25$ karakterističnih lastnosti in pokazali ekvivalence med njimi. Posvetili pa smo se tudi vprašanju, kako “blizu” sta si dve kvadratni matriki glede na njune lastne vrednosti. Ali še bolj zanimivo, kaj se zgodi z lastnimi vrednostmi matrike, če matriko malo perturbiramo. V tem delu smo na ti dve vprašanji odgovorili za normalne matrike. Matrix normality is one of the most interesting topics in linear algebra and matrix theory, since normal matrices have not only simple structures under unitary similarity but also many applications, that is why it has been done a great deal of work on them. There are $89$ different characteristic properties. In this thesis we chose $25$ of those characteristic properties and proved their equivalence to basic definition of normal matrices. We were also interested in how “close” are the matrices in terms of their eigenvalues. More interestingly, if a matrix is “perturbed” a little bit, how would the eigenvalues of the matrix change? In this thesis we present answers to these two questions if the matrices are normal.

Definiramo družino algeber, imenovano algebre, določene z dvostranskim ničelnimproduktom. Kot glavni rezultat dokažemo, da se te algebre pod določenimi pred-postavkami ujemajo z dobro znanimi separabilnimi algebrami. Od tod izpeljemokarakterizacijo končno-dimenzionalnih polenostavnih algeber, določenih z dvostran-skim ničelnim produktom. Da dokažemo glavni rezultat, prej razvijemo ustreznoteorijo obeh družin algeber. Med drugim obravnavamo družino algeber, določenih zničelnim produktom in karakteriziramo separabilne algeber nad polji. We define a family of algebras, called 2-sided zero product determined algebras.As our main result, we prove that this family of algebras, under some conditions,coincides with the well known family of separable algebras. This makes it possiblefor us to characterize finite-dimensional semisimple 2-sided zero product determinedalgebras. To establish the main result, we first develop the theory of both aforemen-tioned families of algebras. In this context, we consider zero product determinedalgebras and characterize separable algebras over fields.

V diplomskem delu obravnavamo upodobitve končnih grup. Povemo, da je upodobitev homomorfizem iz grupe G v linearno grupo GL(V), stopnja upodobitve pa je enaka dimenziji prostora V. Nato povemo, kaj so G-invariantni podprostori in nerazcepne upodobitve. Definiramo ekvivalenčno relacijo med upodobitvami in dokažemo, da se nerazcepnost in razgradljivost ohranjata na ekvivalenčnih razredih. Prvi večji cilj je rezultat, da je poljubna upodobitev končne grupe ekvivalentna direktni vsoti nerazcepnih upodobitev. Nato s teorijo upodobitev dokažemo nekaj rezultatov iz linearne algebre. Dokažemo, da je poljubna nerazcepna upodobitev abelove grupe prve stopnje. Za konec si pogledamo karakterje upodobitev, to so preslikave, ki vsakemu elementu iz grupe priredijo sled njegove upodobitve. Pokažemo, da lahko s karakterji povemo, ali je upodobitev nerazcepna. Zadnji večji rezultat pa je, da je poljubna upodobitev ekvivalentna natanko eni direktni vsoti nerazcepnih upodobitev, pri čemer so posamezni elementi v vsoti določeni do ekvivalenčnega razreda natančno. In this work we deal with representations of finite groups. First, we say that a representation is a homomorphism from a group G to a linear group GL(V) and the degree of the representation is equal to the dimension of the space V. We then tell what G-invariant subspaces and irreducible representations are. We further define the equivalence relation between the representations and prove that the irreducibility and decomposability are preserved on the equivalence classes. The first major goal is to prove that any representation of a finite group is equivalent to the direct sum of irreducible representations. Then, with the theory of representations, we prove some results from linear algebra. We prove that any irreducible representation of the abelian group is of the first degree. Finally, we look at the characters of the representations. The character is a mapping that returns the trace of the representation evaluated at element for each element in the group. We show that we can tell with characters whether representation is irreducible. The last major result, however, is that any representation is equivalent to exactly one direct sum of irreducible representations, with the individual elements in the sum determined to the equivalence class exactly.

Element $u$ iz kolobarja je izjemna enota, če sta $u$ in $1-u$ enoti, torej če sta $u$ in $1-u$ obrnljiva. V delu se najprej posvetimo kolobarjem ostankov ${mathbb Z}_n$, nato pa sledi posplošitev na poljubne končne komutativne kolobarje z enico. V obeh primerih najprej dokažemo formulo za izračun števila izjemnih enot, nato pa še formulo za izračun predstavitev poljubnega elementa iz kolobarja kot vsoto $k$ izjemnih enot. Element $u$ from some ring is an exceptional unit if both $u$ and $1-u$ are units, so if both $u$ and $1-u$ are invertible. In this work we first focus on the residue class rings modulo $n$, and then generalize it to all finite commutative rings with identity. In both cases, we first prove the formula for calculating the number of exceptional units, and then the formula for calculating the representations of any element in the ring as the sum of $k$ exceptional units.

V delu diplomskega seminarja obravnavamo matrične potence in zaporedja matričnih potenc. Sprva navedemo motivacijska zgleda in naredimo pregled pojmov iz linearne algebre, potrebnih za razumevanje besedila. Nato pogledamo matrične polinome in funkcije ter navedemo nekaj osnovnih pojmov iz spektralne teorije. V osrednjem delu si ogledamo koordinatna zaporedja, asimptotsko obnašanje matričnih zaporedij in Cesàrovo konvergenco. Na koncu znanje, pridobljeno tekom diplomskega dela, uporabimo za analizo markovskih verig. In the thesis we discuss matrix powers and sequences of matrix powers. We first give motivating examples and make an overview of the concepts from linear algebra needed to understand the text. We look at matrix polynomials and functions and list some basic concepts from spectral theory. In the central part, we look at coordinate sequences, asymptotic behavior of matrix sequences, and Cesàro summability. Finally, the knowledge gained during the thesis is used to analyze Markov chains.

V diplomskem delu predstavljamo nekaj zanimivih primerov z avtomati generiranih grup. V prvem delu predstavimo input in output avtomatona z simboli abecede X. Množico končnih zaporedij teh simolov, imenovano končni slovar, razumemo kot monoid ali kot množico vozlišč drevesa. Nato preidemo na definicijo Mealyjevega končnega determinističnega avtomata A in jo grafično prikažemo z Moorovimi diagrami. Nato definiramo koncept začetnega avtomata in njegovega delovanja. V drugem delu opišemo delovanje avtomatov abstraktno prek koncepta sinhrone avtomatne transformacije f. Se osredotočimo le na obrnljive avtomate. Preučimo še vpliv obrnljivnosti avtomata na dostopnost njegovih stanj in podamo definicijo z avtomatom generirane grupe. Tretji del opisuje vrsto algebraičnih orodij potrebnih pri analizi z avtomatom generiranih grup. Pričnemo z definicijo levega in desnega delovanja grupe G na množico X in na grupo N, semidirektnega produkta in nazadnje venčnega produkta. V naslednjem razdelku opisujemo povezavo teh struktur z avtomi. V četrtem in zadnjem delu predstavimo klasifikacijo grupe generirane z avtomati z dvema stanjema nad abecedo dveh črk. Preden izrek navedemo predstavimo grupe, ki se pojavijo v rezultatu, začenjši z neskončno diedersko grupo, torej grupe simetrij Z. Sledi grupa svetilničarja (lamplighter group), in definicija posebne sinhrone avtomatske transformacije, imenovane seštevalni stroj. Nazadnje predstavimo del dokaza klasifikacijskega izreka, kjer si pomagamo z analizo primerov. In this bachelor thesis we present some interesting examples and results on groups generated by Mealy automata. In the first section we introduce the input and output of an automaton as sequences of symbols from an alphabet X, and we discuss their properties. In particular, we present the set X^* of finite sequences as the set of vertices of a rooted tree. Then we go on to the formal definition of a finite deterministic Mealy automaton (we will simply call it an automaton) A, and we provide some examples of automata given by Moore diagrams (graph representations of automata). We define the concept of an initial automaton and its action. In the second section we give an abstract characterization of actions of automata: the notion of a synchronous automatic transformation f. We pay a special attention to invertible automata. Then we provide the definition of a group generated by an automaton. In the third section we describe some algebraic structures that arise in connection to groups of automata. We first revise the notions of left and right actions of a group on a set and on a group, the semidirect product construction and finally the wreath product construction. We then study the relationship of these notions with automata. In the fourth section we present the classification of groups generated by 2-state automata over a 2-letter-alphabet. Before formulating the result we introduce two important groups that arise in this theorem, i.e., the infinite dihedral group and the lamplighter group. The latter group can be realized as a wreath product of the infinite cyclic group Z and the two-element group Z/2Z. Then we define a synchronous automatic transformation called the adding machine. Finally we present a detailed account of a part of the proof of the classification theorem. It is based on careful case consideration.

Delo obravnava matrike nad tropskim polkolobarjem. Vpeljan je tropski polkolobar in matrike nad tropskim polkolobarjem. Vzpostavljena je povezava med tropskimi matrikami in uteženimi usmerjenimi grafi. Karakterizirane so lastne vrednosti tropskih matrik in pripadajoči lastni podprostori. Pridobljeno znanje se uporabi na matrikah za primerjanje parov alternativ. Za pridobitev vektorja točk, ki pripada alternativam, se obravnava tri metode in njihove lastnosti. Obravnavane metode so Perronova razvrstitev, Hodgeva razvrstitev in tropska razvrstitev. Izpostavljene so medsebojne povezave in razlike med metodami. In the thesis matrices over the tropical semiring are studied. The tropical semiring and matrices over this semiring are introduced. The connection between tropical matrices and weighted directed graphs is established. Tropical eigenvalues and the corresponding tropical eigenspaces are characterized. The acquired knowledge is used on pairwise comparison matrices. To obtain the score vector for the alternatives, three methods and their properties are examined. The methods are the PerronRank, the HodgeRank and the TropicalRank. Connections and differences between these methods are highlighted.

Presečni graf kolobarja je graf, v katerem so vozlišča pravi ideali v kolobarju, dve vozlišči pa sta sosedni, če imata ideala netrivialen presek. Obravnavamo presečne grafe komutativnih kolobarjev s posebnim poudarkom na kolobarjih ostankov pri deljenju $mathbb{Z}_{n}$. Pokažemo, kdaj so presečni grafi komutativnih kolobarjev povezani, polni, brez triciklov, $r$-delni ali ravninski. Pri kolobarjih $mathbb{Z}_{n}$ pokažemo tudi, kdaj so njihovi presečni grafi Eulerjevi ali Hamiltonovi. An intersection graph of a ring is a graph in which the vertices are nontrivial ideals of the ring, and two vertices are adjacent if the ideals have a nontrivial intersection. We consider intersection graphs of commutative rings with special emphasis on the rings of integers modulo $n$. We discuss which commutative rings have graphs that are connected, complete, tricycle free, $r$-partite or planar. We also find rings $mathbb{Z}_{n}$ that have Eulerian or Hamiltonian intersection graphs.

Besedilo obravnava osnovne vrste kolobarjev, kot so na primer enostavni kolobarji, prakolobarji, polprakolobarji, itd. Sproti se rezultate analogno prilagaja za algebre, saj je glavni cilj besedila dokazati Wedderburnov strukturni izrek za končno razsežne algebre. Precejšen poudarek je na pojmu modula. Potreben je tako za dokaze pomembnih rezultatov, kot tudi za vpeljavo pojma primitivnega kolobarja, ki je ključen pri formulaciji Jacobsonovega izreka o gostoti, na katerem sloni dokaz Wedderburnovega strukturnega izreka. This work deals with basic types of rings, such as simple rings, prime and semiprime rings, etc. Along the way, the results are being adjusted to hold also for algebras, since the main goal of the thesis is to prove Wedderburn’s structure theorem for finite dimensional algebras. The concept of a module is emphasised in the text. It is often used when proving some of the important results, and, moreover it plays a key role in introducing the notion of a primitive ring. The latter is used in the formulation of Jacobson Density Theorem, which provides the necessary tool to prove Wedderburn’s structure theorem.

Glavni cilj diplomskega dela je dokaz izreka Monskega. Pomembni orodji za dokaz izreka sta Spernerjeva lema in p-adična norma. V delu zato predstavimo in dokažemo Spernerjevo lemo. p-adično normo definiramo na polju racionalnih števil in pokažemo, da jo je mogoče razširiti na realna števila. The main goal of this work is to present a proof of Monsky's Theorem. Two of the important tools to prove the theorem are Sperner's lemma and p-adic norm. In the work we formulate and prove Sperner's lemma. We define p-adic norm on the field of rational numbers and show that it is possible to extend it to the field of real numbers.

Delo se ukvarja s perfektoidnimi prostori, razredom objektov v p-adični geometriji, ki jih je vpeljal fieldsov nagrajenec Peter Scholze leta 2011 v svoji doktorski disertaciji. Najprej si ogledamo nekaj osnov teorije valuacij in adičnih prostorov, ki predstavljajo geometrijsko ozadje teme. Nato definiramo perfektoidne kolobarje in polja in si ogledamo nekaj njihovih lastnosti. Vpeljemo funktor naklona, ki nam omogoča prehajanje med objekti v karakteristiki 0 in karakteristiki p. Za konec si še ogledamo perfektoidne prostore, ki so v grobem ravno skupaj zlepljene perfektoidne algebre, podobno kot so snopi ravno skupaj zlepljeni afini snopi. The work is about perfectoid spaces, a class of objects in p-adic geometry that was introduced by the Fields medalist Peter Scholze in his PhD thesis in 2011. First, we will discuss some basic theory of valuations and adic spaces, which represent the geometric background of the topic. Then we define perfectoid rings and fields and look at their properties. We introduce the tilt functor, a tool that helps us to transfer from characteristic 0 to characteristic p. At the end, we look at perfectoid spaces, which we get by glueing together perfectoid algebras, similarly to how we get the schemes from affine schemes.

V diplomski nalogi predstavimo latinske kvadrate, izotopijo, kvazigrupe in zanke. Dokažemo, da je vsaka kvazigrupa izotopna zanki, torej vsak izotopni razred vsebuje vsaj eno zanko. Posvetimo se odnosu med kvazigrupami in latinskimi kvadrati ter pokažemo, da je latinski kvadrat ekvivalenten Cayleyjevi tabeli kvazigrupe. Na protiprimeru pokažemo, zakaj trditve ne moremo razširiti na grupe. Predstavimo kriterije, ki zagotavljajo, da je latinski kvadrat izotopen grupi, torej porojen z grupo. Na primerih in protiprimerih podrobneje spoznamo njihovo delovanje. Seznanimo se s štirikotnim kriterijem in njegovimi različicami. Predstavimo Thomsenov pogoj, ki zagotavlja porojenost latinskega kvadrata z Abelovo grupo. Predstavimo tudi kriterij, ki je zasnovan na permutaciji stolpcev in vrstic Cayleyjevih tabel. In this thesis we present Latin squares, isotopy, quasigroups and loops. We prove that each quasigroup is isotopic to a group, therefore each isotopy class contains at least one loop. We focus on a relationship between quasigroups and Latin squares and show equivalence between Latin squares and Cayley tables of a quasigroup. Reason why this can not be generalised to groups is shown on a counterexample. Criteria which ensure Latin square is isotopic to a group, therefore based on a group, are presented. Functioning of those criteria is closely explained using examples and counterexamples. Quadrangle criterion and his variations are presented. Thomsen condition, which ensures a Latin square is based on an Abelian group, is also presented. Criteria based on permutations of rows and columns of a Cayley tabele is also introduced.

Kolobarji z enolično faktorizacijo so celi kolobarji, v katerih lahko neničelne neobrnljive elemente zapišemo kot končni produkt nerazcepnih elementov in je ta zapis enoličen do asociiranosti in vrstnega reda natančno. Veljajo naslednje vsebovanosti: polja $subset$ evklidski kolobarji $subset$ glavni kolobarji $subset$ kolobarji z enolično faktorizacijo $subset$ celi kolobarji, kjer so vse vsebovanosti stroge. Polja, evklidski kolobarji in glavni kolobarji so torej primeri kolobarjev z enolično faktorizacijo. Kolobar polinomov $K[x]$ je kolobar z enolično faktorizacijo natanko tedaj, ko je $K$ kolobar z enolično faktorizacijo. Unique Factorization Domains are integral domains in which nonzero elements that are not units can be written as a finite product of irreducible elements and this decomposition is unique up to associates and the order of factors. We have the following inclusions: fields $subset$ Euclidean Domains $subset$ Principal Ideal Domains $subset$ Unique Factorization Domains $subset$ integral domains with all containments being proper. Thus: fields, Euclidean Domains and Principal Ideal Domains are examples of Unique Factorization Domains. The polynomial ring $K[x]$ is a Unique Factorization Domain if and only if $K$ is a Unique Factorization Domain.

Realne simetrične matrike so diagonalizabilne, kar pa v splošnem za kompleksne simetrične matrike, ki so obravnavane v diplomski nalogi, ne velja. Kompleksna simetrična matrika je diagonalizabilna natanko tedaj, ko vsak lastni podprostor vsebuje ortonormirano bazo. Če obstaja lastni podprostor, katerega vsaka ortogonalna baza vsebuje kak izotropični vektor, matrike ne moremo diagonalizirati. V diplomski nalogi so izotropični vektorji podrobneje predstavljeni, saj vplivajo na diagonalizabilnost obravnavanih matrik. Poleg tega sta za matrike, ki niso diagonalizabilne, predstavljeni dve možni simetrični kanonični formi, katerima je vsaka kompleksna simetrična matrika ortogonalno podobna. A real symmetric matrix can be diagonalised by an orthogonal transformation. This statement is not true, in general, for a symmetric matrix with complex elements, which is discussed in the present thesis. A complex symmetric matrix can be diagonalised by an orthogonal transformation, if and only if each eigenspace of the matrix has an orthonormal basis. If there is an eigenspace, where every orthogonal basis contains an isotropic vector, the matrix can not be diagonalised. In the present thesis isotropic vectors are presented in greater detail. Also, two possible symmetric canonical forms are obtained for the non-diagonalisable case.

Linearna diskriminantna analiza je metoda, ki se uporablja v statistiki, pri strojnem učenju in pri metodah prepoznavanja vzorcev. Njen cilj je poiskati takšno kombinacijo merjenih spremenljivk, ki kar najbolje ločuje med vnaprej določenimi razredi. Definirana je kot optimizacijski problem, ki vključuje kovariančne matrike, ki zadoščajo pogoju nesingularnosti. Ker ta pogoj otežuje aplikativnost metode, predstavimo posplošitev linearne diskriminantne analize, ki je uporabna tudi v primeru, ko navadna linearna diskriminantna analiza odpove. Uporabo posplošene diskriminantne analize preizkusimo na primeru iz področja medicine, kjer v razrede razvrščamo merjene podatke. Linear discriminant analysis is a method used in statistics, machine learning and pattern recognition. Its aim is to find a combination of features that separates between pre-structured clusters. It is defined as an optimization problem involving covariance matrices, that have to be nonsingular. Since this condition makes it difficult to apply the method on every data, we aim to generalize linear discriminant analysis and make it useful also in cases, when classic linear discriminant analysis fails. Usage of generalized discriminant analysis is shown on medical case of cluster prediction.

Rdeča nit tega dela diplomskega seminarja je predstavitev in primerjava različnih metod strojnega učenja za identificiranje "dobrega izposojevalca", na podlagi podatkov priljubljene spletne platforme za posojanje denarja Lending Club (kratica LC). V delu so predstavljeni rezultati ugotovitev članka z naslovom Risk assessment in social lending via random forests, avtorjev Milada Malekipirbazarija in Vurala Aksakallija, ki sta z uporabo programa WEKA prikazala, da je matoda naključnih gozdov pri identificiranju "dobrega izposojevalca" boljša od točk FICO in ocene s strani LC. To sta metodi, ki ju za identificiranje "dobrega izposojevalca" dandanes uporabljajo agencije, ki se ukvarjajo z računanjem kreditne ocene posameznika za spletne posojilnice. V zaključku dela je predstavljena rekonstrukcija in potrditev navedb članka na podlagi rezultatov, ki sem jih dobil, ko sem simulacije v programu WEKA zagnal še sam. Metode strojnega učenja, ki so predstavljene v tem delu diplomskega seminarja, so: metoda naključnih gozdov, logistična regresija, metoda podpornih vektorjev in metoda k-najbližjih sosedov. The cohesive thread of the following seminar thesis is the presentation and comparison of different methods of machine learning to identify a "good borrower", according to the popular online lending platform Lending Club (acronym LC). The paper presents the results of the findings of an article entitled Risk assessment in social lending via random forests by Milad Malekipirbazari and Vural Aksakalli, who, with the help of WEKA program, showed that the random forests method in identifying a "good borrower" is better than FICO score and LC grades. These methods for identifying a "good borrower" are used by today's agencies to identify the credit rating of an individual for social lending. In the conclusion of the thesis's seminar, a reconstruction and confirmation of results of the article is presented, based on results I have obtained after running the simulations in WEKA program first-hand. Machine learning methods presented in this thesis's seminar are: random forests, logistic regression, support vector machines, and k-nearest neighbours method.

Na realnih bločnih matrikah definiramo Schurov komplement. Motivacija za definicijo izvira iz sistema linearnih enačb, ki se ga s pomočjo Schurovega komplementa lahko zreducira na reševanje manjšega sistema linearnih enačb. Na več načinov zapišemo inverz matrike, izražen s Schurovim komplementom, ki ga je že leta 1939 zapisal matematik Aitken. Dokažemo kvocientno formulo in izračunamo Schurov komplement vgnezdene matrike. Ogledamo si tudi nekaj lastnosti determinante matrik s pomočjo Schurovega komplementa. Na simetričnih bločnih matrikah dokažemo izrek o pozitivni definitnosti bločne podmatrike in njegovih Schurovih komplementov. S pomočjo Schurovega komplementa izpeljemo tudi razcep Choleskega simetričnih pozitivno definitnih matrik. We define the Schur complement on a block matrix over real numbers. Motivation for the definition comes from the system of linear equations which can be reduced to a smaller system of linear equations by using the Schur complement. We write the inverse matrix which blocks are expressed by Schur complement. Those equalities were established already in 1939 by mathematician Aitken. We prove the quotient property of nested Schur complement. We also investigate the properties of determinants using Schur complement. We develop some properties of positive semidefiniteness of Schur complement of a symmetric matrix. We use Schur complement to construct the Cholesky decomposition of a symmetric positive definite matrix.

Polkolobar $S$ je algebrska struktura z dvema notranjima operacijama $oplus$ in $odot$. Pri tem je $(S,oplus)$ komutativni monoid z enoto $0_{S}$, $(S,odot)$ monoid z enoto $1_{S}$, množenje je distributivno nad seštevanjem ter velja, da se vsak element iz $S$ pri množenju z $0_{S}$ zmnoži v $0_{S}$. Vendar pa ne obstajajo nujno inverzni elementi niti za $oplus$ niti za $odot$. V magistrskem delu bomo obravnavali polkolobarje, njihove lastnosti, različne primere in nekatere primere uporabe, predvsem optimizacijske. Osredotočili se bomo na polkolobarje matrik. Pri teh bomo definirali različne range, ki v splošnem med seboj niso enaki. Vemo, da je nad poljem veliko definicij rangov matrik, ki so med seboj ekvivalentne. Te ekvivalence pa ne držijo nujno za range matrik nad polkolobarjem. V delu bomo dokazali nekatere neenakosti ter pokazali na primerih, da enakosti v splošnem ne veljajo. Dokazali bomo tudi nekatere neenakosti, ki veljajo za rang vsote dveh matrik in za rang produkta dveh matrik. The semiring $S$ is an algebraic structure with two binary operations $oplus$ and $odot$, such that $(S, oplus)$ is an Abelian monoid with identity $0_{S}$, $(S, odot)$ is a monoid with identity $1_{S}$, multiplication is distributive over addition and $0_{S}$ is an absorbing element for multiplication. However, there might not exist inverse elements for $oplus$ or for $odot$. In this work we present semirings, their properties, various examples and some examples of applications, in particular in optimization. We concentrate on the semirings of matrices. We define different ranks of matrices over semirings, which in general do not coincide. We know that there are many equivalent definitions of ranks of matrices over the field. These equivalences need not hold for matrix ranks over the semiring. In this work we prove some inequalities among ranks and show by examples that the strict inequalities might apply. We also prove some inequalities that hold for the rank of the sums of two matrices and for the rank of the product of two matrices.

V magistrskem delu preučujemo lastne vrednosti realnih simetričnih matrik. Zanima nas najmanjše možno število $q(G)$ različnih lastnih vrednosti vseh matrik, katerih ničelno-neničelni vzorec pripada vnaprej predpisanemu grafu $G$. Za različne družine grafov $G$ izračunamo $q(G)$. Pri tem si pogledamo tudi lastnosti spojev grafov ter kartezičnih, tenzorskih in krepkih produktov grafov. V posebnem nas zanimajo grafi $G$ na $n$ točkah, za katere velja $q(G)=1,2,n-1$ ali $n$. The aim of this work is to present the properties of eigenvalues of real symmetric matrices. We are interested in finding the minimum number of distinct eigenvalues $q(G)$ of all matrices whose zero-nonzero pattern belongs to a given graph $G$. For some families of graphs $G$ we calculate $q(G)$. We mention the properties of the join of two graphs and also Cartesian, tensor and strong products of graphs. In particular, we are interested in graphs $G$ on $n$ points, for which $q(G)=1,2, n-1$ or $n$.

V tej diplomski nalogi bomo govorili o ničlah polinomov in njihovih odvodov - bolj natančno o geometriji ničel. Raziskovali bomo, kako so ničle polinomov in njihovih odvodov povezane in kakšne geometrijske lastnosti imajo. The main topic of this thesis is the geometry of the zeros of polynomials and their derivatives. We will explore, how the zeros of polynomials and their derivatives are linked and what type of geometric properties they have.

Matrika je evklidsko razdaljna (Euclidian distance matrix -- EDM), če obstajajo točke, tako da so elementi matrike kvadrati evklidskih razdalj med temi točkami. V tem delu dokažemo nekaj pomembnih lastnosti EDM. Nato pa se osredotočimo na inverzni problem lastnih vrednosti za EDM. Inverzni problem lastnih vrednosti (inverse eigenvalue problem -- IEP) je sledeč: konstruirati (ali dokazati obstoj) matrike z danim spektrom in določenimi lastnostmi (konkretno, da je matrika EDM). Dobro je znano, da ima IEP za EDM velikosti 3x3 rešitev. V tem delu so podane vse rešitve tega problema, proučujemo njihovo povezavo z geometrijo ter možno razširitev na večje EDM z uporabo obrobljenih matrik. Poleg tega pa predstavimo tudi povezavo med znanim problemom obstoja Hadamardovih matrik in IEP za EDM. The matrix is an Euclidean distance (EDM) if there exist points so that the matrix elements are squares of the euclidean distances between these points. In this work, we prove some important properties of EDM. Then we focus on the inverse eigenvalue problem for EDM. The inverse eigenvalue problem is as follows: to construct (or to prove the existence of) a matrix with a given spectrum and required properties (in particular that the matrix is EDM). It is well known that the IEP for EDM of size 3 has a solution. Here we find all the solutions to this problem, we study their connection with geometry and possible extension to larger EDM using bordered matrices. Then we show the connection between the well known problem of the existence of Hadamard matrices and the IEP for EDM.

V delu obravnavamo invariante $m$-teric $n times n$ matrik $X_1, ldots, X_m$ 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 $X_i$. 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 $m$-tuples of $n times n$ matrices $X_1, ldots, X_m$ 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 $X_i$. 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.