Random symmetric matrices are almost surely non-singular Duke Math. J. 135 (2006), 395-413 (with T. Tao and V. Vu)
Consider a symmetric matrix whose entries on or above the main diagonal are equally likely to be 1 or -1. By adapting an argument of Komlós, we show that the probability that this matrix is singular is O(n-⅛+ε) for any positive ε. The key difficulty arises due to the fact that the determinant of a symmetric matrix is a quadratic function in the entries (as opposed to a linear one) due to the symmetry condition. To overcome this, we develop a quadratic extension of the Littlewood-Offord inequality to show that this form is unlikely to be 0. (An improved version of this lemma is one subject of the "Bilinear and quadratic variants..." paper below).
The rank of random graphs. Random Structures and Algorithms 33 (2008), 269-285 (with V. Vu)
One corollary of the results in the previous paper is that for any fixed p the adjacency matrix of the Erdős-Rényi graph G(n,p) is almost surely nonsingular. Here we consider the case where p=o(1). The main result is the following behavior: If p>c ln n⁄n, where c>½, then the non-zero rows of the adjacency matrix are almost surely independent. This is tight, since if p is at most c ln n⁄n where c<½, then the adjacency matrix almost surely has pairs of equal nonzero rows. In particular, ln n⁄n is a threshold for the entire matrix being non-singular.
The rank of sparse random matrices. Submitted. (with V. Vu)
As mentioned above, we know that for p less than ln n/n that the adjacency matrix of G(n,p) is almost surely singular. In this paper we are able to exactly quantify the extent of singularity as p drops below ln n⁄n. To be more precise, we consider the following model: Given a fixed (symmetric) matrix W which is nonzero off of the main diagonal, we "sparsify" W by independently replacing each entry by 0 with probability 1-p. As p approaches 0, the sparsified matrix will begin to develop collections of s rows which between them have fewer than s nonzero columns. Such collections will be dependent regardless of the initial matrix W.
One main result of this paper is that such "local" structures of the sparsification process are almost surely the only source of singularity for p not too small. If p is at least ln n⁄sn (with s fixed), then with high probability the only dependencies in the rows of the sparsified matrix will come from collections of at most s-1 rows that fail to contain enough nonzero columns.
Balancing gaussian vectors. Accepted, Israel J. Math.
Here we consider the following question: Given a (fixed) norm ||.|| on Rd and vectors x1, x2, ... , xn, what can be said about
min || ± x1 ± x2 ± x3, ... , ± xn ||,
where the minimum is taken over all 2n possible sign sequences? Although in the worst case this minimum may be as large as d (as shown by Barány and Grinberg), the bound turns out to be much smaller (actually exponentially small in n) most of the time when the xi are independent Gaussians.
Bilinear and quadratic variants on the Littlewood-Offord problem. Submitted
Let f(x1, x2, ..., xn) be a polynomial dependent on a large number of independent random variables. A natural question to ask is how dispersed such f become as the number of variables increases. To be more concrete, if we independently set each xi equal to ± 1, what is the maximum concentration of f on a single value, and what polynomials come close to achieving this concentration?
If f is a linear form, we get a rescaled version of a problem originally asked by Littlewood and Offord and answered by Erdős: The largest concentration is of order n-1/2 and occurs when all of the nonzero coefficients of f are equal. Here we consider the case where f is instead a bilinear or quadratic form.
In the bilinear case, we show that every form with concentration significantly larger than n-1 must differ in only a few coefficients from a form which factors as f(x,y)=g(x)h(y) (such degenerate forms can have concentration as large as n-½). In the quadratic case, we show that no form has concentration significantly larger than n-½. In both cases these results are nearly tight.
A weaker version of the bound for quadratic forms was used in the random matrix papers above, where it was used to bound the probability that the determinant of a random symmetric matrix (which is a quadratic form in the entries in any particular row or column) was equal to 0. An immediate corollary of the results here is a slight improvement in the singularity bounds in those papers.
Concentration of random determinants and permanent estimators. Accepted, Siam J. Discrete Math (joint with Van Vu)
Let A be a matrix whose entries are independent random variables having variances bounded above and below by a constant. Here we are interested in the following question: How closely does |det(A)| typically lie to its expectation? There are two natural ways to bound this. One approach (used by Girko and Tao-Vu) is to use the determinant's definition as an oriented volume to write
|det(A)|=d1d2...dn,
where di is the distance from row i to the span of the prior i-1 rows, then use probabilistic techniques (e.g. Talagrand's inequality) to show that most of the d_i lie close to their expectation. While this works well when the entries are iid (or even just have equal variances), in the general case this becomes more difficult since the distribution of di depends heavily on the structure of the subspace spanned by the first i-1 rows.
Instead we follow the ideas of Friedland, Rider and Zeitouni by considering the determinant as a product of singular values,
|det(A)|=σ1σ2...σn,
and using results of Guionnet and Zeitouni stating that each σi is concentrated. The catch is that the determinant is very sensitive to perturbations in the smallest singular values, which need to be handled separately. Our key improvement over the Friedland-Rider-Zeitouni result lies in our handling of these small singular values (adapting recent results of Tao-Vu and Rudelson-Vershynin along with some geometric arguments), which enables both an improved bound on the concentration and the possibility of entries having non-Gaussian (e.g. discrete) probability distributions.