Vjerojatnost da je slučajna matrica singularna

master's thesis

• Title (english): The probability that a random matrix is singular
• Author: Jura Jurčević
• Mentor: Rudi Mrazović (mentor)
• Committee member: Rudi Mrazović (predsjednik povjerenstva)
• Committee member: Vanja Wagner (član povjerenstva)
• Committee member: Tomislav Berić (član povjerenstva)
• Committee member: Matija Bašić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-09-10, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: slučajne matrice; Kahn; Komlos; Szemeredi; Halaszeva nejednakost
• Keywords (english): random matrices; Kahn; Komlos; Szemeredi; Halasz’s inequality
• Language: croatian
• URN:NBN: urn:nbn:hr:217:827529
• Study programme: Title: Finance and Business Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2021-03-10 10:52:44