Unitary perturbation of any matrix is well invertible with high probability

You need to know: Square matrix with complex entries, eigenvalue of a square matrix, identity matrix I, conjugate transpose $U^*$ of matrix $U$ , unitary matrix (matrix $U$ such that $U^*U=UU^*=I$ ), group, unitary group $U(n)$ (group of all unitary matrices with matrix multiplication as group operation), notation ${\mathbb P}$ for probability, uniform distribution in the unitary group.

Background: For any $n \times n$ matrix A, the eigenvalues of $A^*A$ are real and non-negative. The square roots of these eigenvalues are called singular values of A. Let $s_{\text{min}}(A)$ be the smallest singular value.

The Theorem: On 22nd June 2012, Mark Rudelson and Roman Vershynin submitted to arxiv and the Journal of the AMS a paper in which they proved the following result. Let D be an arbitrary fixed $n \times n$ matrix, $n\geq 2$ . Let U be a random matrix uniformly distributed in the unitary group $U(n)$ . Then ${\mathbb P}\left(s_{\text{min}}(D+U)\leq t\right) \leq t^c n^C$ for all $t>0$ and some positive constants $C,c$ .

Short context: The smallest singular value of a square matrix A is inverse proportional to the norm of $A^{-1}$ , and therefore provides a quantitative measure of invertibility of A. In earlier works (see here and here), Rudelson and Vershynin analyse invertibility of random matrices with independent entries. The Theorem did the same for random unitary perturbation of a fixed matrix D. It is important that the estimate in the Theorem does not depend on D.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Random n by n matrix (with 4 moments of entries Gaussian) has (2n/pi)^(1/2)+o(n^(1/2)) real eigenvalues

You need to know: Know: $n \times n$ matrix with real entries, eigenvalues, probability, random variable, jointly independent random variables, standard normal distribution, notation $E$ for expectation, almost sure convergence, small o notation.

Background: For positive integer n, let $M_n$ be $n \times n$ matrix whose entries $\xi_{ij}$ are jointly independent real random variables which (i) have exponential decay, i.e., $P(|\xi_{ij}|\geq t) \leq C \exp(-t^c)$ for some constants $C,c>0$ (independent of n) and all $i,j$ , and (ii) $E[\xi_{ij}^k]=E[Z^k]$ for $k=1,2,3,4$ and all $i,j$ , where Z is the random variable having standard normal distribution.

The Theorem: On 9th June 2012, Terence Tao and Van Vu submitted to arxiv a paper in which they proved that $M_n$ has $\sqrt{\frac{2n}{\pi}}+o(\sqrt{n})$ real eigenvalues asymptotically almost surely.

Short context: The study of eigenvalues of large random matrices is one of the central themes in probability theory. The Theorem estimates how many of the eigenvalues are real. Earlier, this result was known to hold only for the special case when all $\xi_{ij}$ has standard normal distribution. In fact, the Theorem is just one out of many corollaries of a much more general theorem, which, very roughly speaking, states that many properties of the eigenvalues of a random matrix with independent entries depend only on the first four moments of the entries. Unlike previous results in the literature, this theorem does not require matrix $M_n$ to be symmetric. It also does not require entries $\xi_{ij}$ to be identically distributed.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

The probability that the random walk in a bounded degree planar graph avoids its initial location for T steps is at most C/log T

You need to know: Graph, finite graph, planar graph, degree of a vertex in a graph, probability, selection uniformly at random.

Background: A simple random walk on graph G is the process which starts at some vertex $v_0$ at time $t=0$ , and then at times $t=1,2,\dots$ moves to an adjacent vertex selected uniformly at random. Assuming that initial vertex $v_0$ is selected uniformly at random from vertices of G, denote $\phi(T,G)$ the probability that the walk does not return to $v_0$ for T steps. Let ${\cal G}(D)$ be the set of all finite planar graphs with degrees of all vertices bounded by D, and let $\phi_D(T)=\sup\limits_{G \in {\cal G}(D)} \phi(T,G)$ .

The Theorem: On 4th June 2012, Ori Gurel-Gurevich and Asaf Nachmias submitted to arxiv and the Annals of Mathematics a paper in which they proved that for any $D\geq 1$ , there exists a constant $C=C(D)<\infty$ such that $\phi_D(T) \leq \frac{C}{\log T}$ for any $T \geq 2$ .

Short context: The study of random walks on graphs is one of the central research directions in probability theory with numerous applications, and walks on bounded-degree planar graphs form an important special case. In 2001, Benjamini and Schramm proved that $\phi_D(T) \to 0$ as $T\to\infty$ , but left the rate of decay of $\phi_D(T)$ as an open question. Because it is known that $\phi_D(T) \geq \frac{c}{\log T}$ for some constant $c>0$ , the Theorem answers this question up to a constant factor.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Internal DLA process converges to a disk with at most logarithmic discrepancy

You need to know: Integer lattice ${\mathbb Z}^2$ , origin $0$ , basic probability theory, simple random walk on ${\mathbb Z}^2$ , notation $\left \lfloor{t}\right \rfloor$ be the largest integer not exceeding t.

Background: The internal diffusion limited aggregation process (internal DLA process for short) is defined as follows. For each integer time $n\geq 1$ , construct a random set $A(n) \subset {\mathbb Z}^2$ such that (i) $A(1) = \{0\}$ , and (ii) for each $n\geq 1$ , let $A(n+1)$ be $A(n)$ plus the first point at which a simple random walk from the origin hits ${\mathbb Z}^2 \setminus A(n)$ . For any real $t\geq 1$ , let $A(t)=A(\left \lfloor{t}\right \rfloor)$ . For $r>0$ , let $B(r)=\{z=(z_1,z_2) \in {\mathbb Z}^2\,|\,z_1^2+z_2^2 < r^2\}$ .

The Theorem: On 12th October 2010, David Jerison, Lionel Levine, and Scott Sheffield submitted to arxiv a paper in which they proved the existence of an absolute constant C such that with probability 1, $B(r-C\log r) \subset A(\pi r^2) \subset B(r+C\log r)$ for all sufficiently large r.

Short context: Internal DLA process was proposed by Meakin and Deutch in 1986 as a model of industrial chemical processes. They found numerically that, for large n, the process becomes close to a disk with at most logarithmic fluctuations. In 1992, Lawler, Bramson and Griffeath proved that the asymptotic shape of the domain $A(n)$ is indeed a disk. The Theorem confirms that the fluctuations are indeed at most logarithmic.

Links: Free arxiv version of the paper is here, journal version is here.

Go to the list of all theorems

The Hoeffding inequality holds for semidefinitely upper bounded matrices

You need to know: Matrix, self-adjoint matrix, eigenvalues $\lambda_1, \dots, \lambda_d$ of $d \times d$ matrix, notation $||A||$ for the norm $||A||=\max\limits_{i}|\lambda_i|$ of self-adjoint matrix A, positive semidefinite matrix (one with all $\lambda_i \geq 0$ ), notation $A \preceq B$ if matrix $B-A$ is positive semidefinite, probability ${\mathbb P}$ , independence, expectation ${\mathbb E}$ .

Background: Consider a finite sequence $A_1, \dots, A_n$ of fixed self-adjoint $d \times d$ matrices. Denote $\sigma^2 = ||\sum\limits_{k=1}^n A_k^2||$ . Let $X_1, \dots, X_n$ be a sequence of independent, random, self-adjoint $d \times d$ matrices satisfying ${\mathbb E}[X_k]=0$ and $X_k \preceq A_k$ almost surely.

The Theorem: On 25th April 2010, Joel Tropp submitted to arxiv a paper in which he proved that, for $X_1, \dots, X_n$ as above, and for all $t \geq 0$ , ${\mathbb P}\left(\lambda_{\text{max}}\left(\sum\limits_{k=1}^n X_k\right)\geq t\right) \leq d \cdot e^{-t^2/8\sigma^2}$ .

Short context: There are many classical inequalities which allows to bound the probability that the sum of independent random variables exceeds some threshold. For many applications, it is important to have a similar result for sum of matrices, where we bound the size of maximal eigenvalue $\lambda_{\text{max}}$ of the sum. The Theorem provides a matrix version of the classical Hoeffding inequality. In the same paper, many other classical inequalities are extended to the matrix setting as well.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

For any connected graph, the blanket and cover times are within an O(1) factor

You need to know: Graph, finite graph, connected graph, notation $G=(V,E)$ for graph with vertex set V and edge set E, notation $|E|$ for the number of edges in G, degree $\text{deg}(v)$ of vertex $v\in V$ , probability, selection uniformly at random, expectation, $O(1)$ notation.

Background: Let $G=(V,E)$ be a connected graph. A simple random walk on G is the process which starts at some vertex v at time $t=0$ , and then at times $t=1,2,\dots$ moves to an adjacent vertex selected uniformly at random. Let $\tau_\text{cov}$ be the first time at which every vertex of G has been visited, and let ${\mathbb E}_v[\tau_\text{cov}]$ be the expectation of $\tau_\text{cov}$ (which depend on the initial vertex v). Number $t_\text{cov}(G) = \max\limits_{v \in V}{\mathbb E}_v[\tau_\text{cov}]$ is called the cover time of G.

For any $v\in V$ , let $N_v(t)$ be a (random) number of times the random walk has visited v up to time t. For $\delta\in(0,1)$ , let $\tau_{\text{bl}}(\delta)$ be the first time $t\geq 1$ at which $N_v(t) \geq \delta t \frac{\text{deg}(v)}{2|E|}$ holds for all $v\in V$ . Number $t_\text{bl}(G,\delta) = \max\limits_{v \in V}{\mathbb E}_v[\tau_{\text{bl}}(\delta)]$ is called the $\delta$ –blanket time of G.

The Theorem: On 25th April 2010, Jian Ding, James Lee, and Yuval Peres submitted to arxiv a paper in which they proved that for every $\delta\in(0,1)$ , there exists a $C=C(\delta)$ such that for every connected graph G, one has $t_\text{bl}(G,\delta) \leq C t_\text{cov}(G)$ .

Short context: It is known that as $t\to\infty$ , the proportion of time a random walk spend at any vertex v converges to $\frac{\text{deg}(v)}{2|E|}$ . Hence, $\tau_{\text{bl}}(\delta)$ is the first time at which all nodes have been visited at least a $\delta$ fraction as much as we expect. Because $t_\text{cov}(G) \leq t_\text{bl}(G,\delta)$ by definition, the Theorem states that the blanket and cover times are within an O(1) factor. It confirms conjecture of Winkler and Zuckerman made in 1996.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

For d>=19, the one-arm exponent for critical bond percolation in Z^d is 1/2

You need to know: Set ${\mathbb Z}^d$ of vectors $x=(x_1,\dots, x_d)$ with integer components, $||x||=\sqrt{\sum_{i=1}^d x_i^2}$ , origin $O=(0,0,\dots,0)\in {\mathbb Z}^d$ , graph, path in a graph, infinite graph, probability, independence.

Background: Let G be an infinite graph with vertex set ${\mathbb Z}^d$ such that $x,y \in{\mathbb Z}^d$ are connected by an edge if and only if $||x-y||=1$ . Given $p\in[0,1]$ , a bond percolation $G_p$ in ${\mathbb Z}^d$ is a subgraph of G to which each edge of G is included independently with probability p. Given $r>0$ , let $P_d(p,r)$ be the probability that there exists a path in $G_p$ from origin O to some vertex $x \in {\mathbb Z}^d$ with $||x||>r$ . It is known that for every $d\geq 2$ there exists a $p_d \in [0,1]$ such that $L_d(p)=\lim\limits_{r\to \infty}P_d(p,r)=0$ for $p<p_d$ but $L_d(p)=1$ for $p>p_d$ .

The Theorem: On 4th November 2009, Gady Kozma and Asaf Nachmias submitted to arxiv and the Journal of the AMS a paper in which they proved that $P_d(p_d,r) \approx r^{-2}$ for every $d\geq 19$ , where $f(r) \approx g(r)$ means that $C^{-1}f(r) \leq g(r) \leq Cf(r)$ for some constant $C>0$ which might depend on d but not on r.

Short context: The study of percolations is motivated by physical applications and mathematical beauty, and is especially challenging for $p=p_d$ . It is believed that $L_d(p_d)=0$ for all $d\geq 2$ , and this is considered to be one of the most challenging open problems in probability theory. Intuition from physics suggest that not only $L_d(p_d)=0$ , but in fact $P_d(p_d,r) \approx r^{-1/\rho}$ for some $\rho=\rho(d)>0$ , which is called the one-arm exponent for critical bond percolation in ${\mathbb Z}^d$ . The Theorem proved that for all $d\geq 19$ this one-arm exponent indeed exists and is equal to $1/2$ .

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Replica predictions hold for the minimum matching problem in the pseudo-dimension d mean field model for d>=1.

You need to know: Graph, complete graph, matching in a graph, minimum matching, limits, notation $P$ for probability, random variable, independent random variables, distribution, density.

Background: Let $d>0$ be a real number, and let $n>0$ be an even integer. In a complete graph $G_n$ on n vertices, let each edge $e$ be assigned independent random cost $C_e$ from a fixed distribution on the non-negative real numbers with density $\rho(t)$ , such that $\lim\limits_{t \to 0^+} \frac{\rho(t)}{dt^{d-1}} = 1$ . Let $M(n,d)$ be the (random) cost of a minimum matching in $G_n$ .

The Theorem: On 1st July 2009, Johan Wästlund submitted to the Annals of Mathematics a paper in which he proved that for any $d \geq 1$ there exists a number $\beta(d)$ such that for any $\epsilon>0$ , $\lim\limits_{n\to \infty}P\left[\left|M(n,d) - \beta(d)\right|>\epsilon\right] = 0.$

Short context: Minimum matching problem in a graph is one of the fundamental problems in graph theory. A model in which the edge costs are randomly chosen as described above is known as the mean field model of pseudo-dimension d. In 1985, Mézard and Parisi introduced non-rigorous analysis with physical origin (called replica analysis) which allowed them to predict that the statement of the Theorem holds for any $d>0$ , write down a conjectured analytic formula for $\beta(d)$ , and compute it numerically. However, before 2009, these predictions were rigorously confirmed only for $d=1$ . The Theorem did this for all $d\geq 1$ .

Links: The original paper is available here.

Go to the list of all theorems

The Khorunzhiy conjecture on the norms of random band matrices is true

You need to know: Eucledean space ${\mathbb R}^n$ , norm $||x||=\sqrt{\sum_{i=1}^n x_i^2}$ of vector $x=(x_1, \dots, x_n)\in{\mathbb R}^n$ , matrix, multiplication of matrix by a vector, norm $\|A\| = \sup\limits_{||x||=1}||Ax||$ of $n\times n$ matrix A, basic probability theory, independence, convergence in distribution.

Background: Fix a sequence $w_1, w_2, \dots, w_n, \dots$ of positive numbers. For every positive integer n, let $A_n$ be a random $n \times n$ matrix whose entries $a_{ij}$ are such that (i) $a_{ij}=a_{ji}$ for all i and j; (ii) $a_{ij}=0$ if either $i=j$ or $\min(|i-j|, n-|i-j|)>w_n$ ; and (iii) all $a_{ij}$ such that $0<\min((i-j), n-(i-j)) \leq w_n$ are selected independently at random, each equal to $1$ or $-1$ with equal probabilities. Random matrices $A_n$ selected in accordance to these rules are called random band matrices.

The Theorem: On 22nd June 2009, Sasha Sodin submitted to arxiv a paper in which he proved that if $\lim\limits_{n\to\infty}\frac{w_n}{\log n}= +\infty$ then $\|A_n/2\sqrt{2w_n}\|$ converges in distribution to $1$ .

Short context: The study of random matrices is one of the central topics in probability theory, and random band matrices is an important model having physical applications. In 2008, Khorunzhiy proved the statement of the Theorem under stronger assumption that $\lim\limits_{n\to\infty}\frac{w_n}{\log^{3/2} n} = +\infty$ , and conjectured that weaker assumption $\lim\limits_{n\to\infty}\frac{w_n}{\log n} = +\infty$ suffices. The Theorem proves this conjecture. This result is sharp, because Bogachev, Molchanov, and Pastur proved in 1991 that the conclusion of the Theorem fails if $\lim\limits_{n\to\infty}\frac{w_n}{\log n} = 0$ .

Links: Free arxiv version of the original paper is here, journal version is here. See also Section 10.13 of this book for an accessible description of the Theorem.

Go to the list of all theorems

Wigner Hermitian matrices have universal eigenvalue gap distribution

You need to know: Complex numbers, $n \times n$ matrix with complex entries, eigenvalues, Hermitian matrix, probability, random variable, mean, variance, notation P for probability, E for expectation, i.i.d. for independent identically distributed random variables, notation $|A|$ for the number of elements in finite set A.

Background: A Wigner Hermitian $n \times n$ matrix $M_n$ is a random Hermitian matrix with upper triangular complex entries $\psi_{ij}=\xi_{ij}+\tau_{ij}\sqrt{-1}$ , $1 \leq i < j \leq n$ , and diagonal real entries $\xi_{ii}$ , $1\leq i \leq n$ , where (i) for $1 \leq i < j \leq n$ , $\xi_{ij}$ and $\tau_{ij}$ are i.i.d. copies of a real random variable $\xi$ with mean zero and variance $1/2$ ; (ii) for $1\leq i \leq n$ , $\xi_{ii}$ are i.i.d. copies of a real random variable $\xi'$ with mean zero and variance 1; and (iii) $\xi$ and $\xi'$ have exponential decay, i.e., there exist constants $C$ and $C_0$ such that $P(|\xi|\geq t^C) \leq e^{-t}$ and $P(|\xi'|\geq t^C) \leq e^{-t}$ for all $t > C_0$ . $\xi$ and $\xi'$ are called the atom distributions of $M_n$ . Let $\lambda(M_n\sqrt{n})=(\lambda_1, \dots, \lambda_n)$ be the vector of eigenvalues $\lambda_i$ of matrix $M_n\sqrt{n}$ , arranged in the non-increasing order: $\lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$ . Let $S_n(s; \lambda(M_n\sqrt{n})) = \frac{1}{n}|\{1\leq i \leq n-1: \, \lambda_{i+1}-\lambda_i \leq s\}|$ .

The Theorem: On 2nd June 2009, Terence Tao and Van Vu submitted to arxiv a paper in which they proved the following result. Let $M_n$ be a Wigner Hermitian matrix whose atom distributions $\xi, \xi'$ have support on at least three points, and $s>0$ . The the limit $G(s)=\lim\limits_{n\to\infty}E[S_n(s; \lambda(M_n\sqrt{n}))]$ exists and depends only on s but not on $\xi, \xi'$ .

Short context: The study of eigenvalues of large random matrices (largest eigenvalues, smallest, gaps between them, etc.) is one of the central themes in probability theory. In 1967, Mehta computed the limit $G(s)$ assuming that $\xi$ and $\xi'$ have normal distribution. The Theorem states that $E[S_n(s; \lambda(M_n\sqrt{n}))]$ converges to the same limit $G(s)$ , no matter how $\xi$ and $\xi'$ are distributed. In fact, the Theorem is just one out of many corollaries of a much more general “Four moment theorem” proved by authors, which, informally, states that many properties of the eigenvalues of a random Hermitian matrix are determined by the first four moments of the atom distributions. In a later work, the authors also treated a non-Hermitian case.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems