Vjerojatnost da je slučajna matrica singularna

diplomski rad

• Naslov (engleski): The probability that a random matrix is singular
• Autor: Jura Jurčević
• Mentor: Rudi Mrazović (mentor)
• Član povjerenstva: Rudi Mrazović (predsjednik povjerenstva)
• Član povjerenstva: Vanja Wagner (član povjerenstva)
• Član povjerenstva: Tomislav Berić (član povjerenstva)
• Član povjerenstva: Matija Bašić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2020-09-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu promatramo slučajne \(n \times n\pm 1\) matrice, pri čemu je slučajnost definirana uniformnom distribucijom, odnosno za svaki element matrice nezavisno jedan od drugog na slučajan (uniformni) način biramo 1 ili -1.
Za tako definirane matrice; zanima nas kako se ponaša \(P_n=\mathbb{P} \)(\(M_n\) je singularna) kada \(n\) raste u beskonačnost. Već je pokazano da \(P_n \to 0\) i da vrijedi da \(P_n= O\left( \frac{1}{\sqrt{n}} \right) \) .
U ovom radu prezentiramo rezultat Kahna, Komlosa i Szemeredija koji su pokazali eksponencijalnu gornju među, odnosno da postoji \(\epsilon\) takav da vrijedi \(P_n < (1-\epsilon)^n\).
U prvom poglavlju postavit ćemo problem te iskazati glavne rezultate i dati smjernice, odnosno način na koji ćemo te rezultate dokazati. U Poglavlju 2 dokazat ćemo pomoćni teorem koji je važan korak u dokazu naše tvrdnje, ali i kao samostalan rezultat. Jako važan, ako ne i najvažniji korak u tom dokazu je korištenje Halaszeve nejednakosti. U Poglavlju 3 dokazat ćemo glavni teorem uz pomoć nekoliko lema za koje ćemo takoder pokazati da vrijede u istom poglavlju. Osim spomenutih lema, još jedan bitan korak u dokazu glavnog teorema je konstrukcija potprostora kojima ćemo pokriti sve vektore iz \(\mathbb{Z} ^n\). Naposljetku, u posljednjem poglavlju iznijet ćemo poboljšanja našeg rezultata. Takoder ćemo spomenuti neke primjene i posljedice naše tvrdnje na razna područja.

Sažetak (engleski)

In this work we observe random \(n \times n\pm 1\) matrices, where randomness is defined by the uniform distribution, that is we choose 1 or -1 for each element of the matrix independently of each other in a random (uniform) way. For such random matrices, we are interested in how \(P_n=\mathbb{P} \)( \M_n\) is singular) behaves when n grows to infinity. It has already been shown that da \(P_n \to 0\) and that \(P_n= O \left( \frac{1}{\sqrt{n}} \right) \). In this paper, we give an exponential upper bound, i.e. we show that there exists an \(\epsilon\) such that \(P_n < (1-\epsilon)^n\). In the first chapter, we will pose the problem and present the main results and give guidelines on how to prove these results. In Chapter 2 we will prove an auxiliary theorem which is an important step in proving our claim, but also as an independent result. A very important, if not the most important step in this proof is the use of Halasz’s inequality. In Chapter 3 we will prove the main theorem with the help of several lemmas which we will also prove in the same chapter. In addition to the these lemmas, another important step in the proof of the main theorem is the construction of subspaces by which we will cover all vectors from \(\mathbb{Z} ^n\). Finally, in the last chapter, we will present improvements to our bound. We will also mention some applications and consequences of our claim to various areas.

• Ključne riječi: slučajne matrice; Kahn; Komlos; Szemeredi; Halaszeva nejednakost
• Ključne riječi (engleski): random matrices; Kahn; Komlos; Szemeredi; Halasz’s inequality
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:827529
• Studijski program: Naziv: Financijska i poslovna matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2021-03-10 10:52:44