# Maximum singular value of a random $\pm 1$ matrix

Define a matrix $$\mathbf{A} \in \mathbb{R}^{m \times n}$$ such that each element is independently and randomly chosen with probability $$\frac 12$$ to be either $$+1$$, or $$-1$$. Do you know any result in the literature that talks about properties of this kind of matrices?

I have seen that there are some results for other kind of random matrices (for example matrices whose entries are i.i.d. Gaussian.) but not for this simple matrix of $$\pm 1$$.

I would be interested for example on the distribution of the $$\sigma_{\max}(A)$$, but not in an asymptotic regime, as $$m$$, $$n$$ are finite numbers and usually small in my case.

Thank you very much for any pointer or any thoughts.

• How small are $m$ and $n$? Less than 10? Less than 100? – Yemon Choi May 1 '12 at 4:04
• Maybe the standard $\sqrt{m}+\sqrt{n}$ bound applies here too. – Suvrit May 1 '12 at 4:36
• Hi, thank you very much for your comments. $m$ and $n$ are usually less than 10. Do you have a paper in mind that talks about the $\sqrt{m}+\sqrt{n}$ bound? Thank you, best, Alex – Kostas May 1 '12 at 7:16

http://www-personal.umich.edu/~romanv/papers/non-asymptotic-rmt-plain.pdf Theorem 5.39 (page 23) gives a non-asymptotic upper bound on the largest singular value

• The link is broken, the last indexed version can be found on the archive. – student Mar 30 '19 at 21:45

For what it's worth, it's relatively easy to simulate these in Mathematica, via

Manipulate[
Histogram[
N[SingularValueList[ 2 RandomInteger[{0, 1}, {m, n}] - 1, 1][[
1]]] & /@ Range[10^power]], {m, 1, 10, 1}, {n, 1, 10,
1}, {power, 1, 6, 1}]


I've been playing around with it, and this

is a histogram for 1,000,000 tries with $$m=9$$, $$n=5$$ for the five different singular values (each in a different colour). I'm intrigued by the peaks - were you expecting that? There is also a significant portion of matrices with one zero singular value, but I am unsure whether it is due to numerical artifacts.

• Thank you very much for your time to code this! It was very helpful! – Kostas May 1 '12 at 20:53
• You're welcome! Mathematica code is normally deceptively simple but this was quite straightforward. Plus, it helped me crystallize the Random[]&/@Range[] trick which had been annoyingly floating around my mind with a "there has to be a simple way" kind of taunt. – Emilio Pisanty May 2 '12 at 0:12
• Any matrix with two rows which are multiples of each other will automatically have a $0$ singular value. This accounts for most of the peak you see at $0$ (each pair of rows matches for about $3900$ matrices and there's $10$ pairs of rows), but disappears as $\min\{m,n\}$ tends to infinity. – Kevin P. Costello May 2 '12 at 16:59
• In a sense, "local" configurations (those involving only a couple rows) can only get you so close to $0$: If you look at, say, $|| \{1,-1,0,0,0,0,0,0,0,0 \} A||$, it's either going to be $0$ or at least $1$, meaning that this can't be the cause of a positive singular value smaller than $2^{-1/2}$. Intuitively, a $0$ singular value (which requires only $1$ row to go wrong) is much easier than a very small positive singular value (which requires $2$ or more rows to go wrong), though this is far from a rigorous proof. – Kevin P. Costello May 3 '12 at 18:40
• (continued) Even if you let both $m$ and $n$ go to infinity, but at different rates (say $m/n \rightarrow c<1$), the smallest singular value will with high probability grow be within a constant of the largest (Bai and Yin, "Limit of the smallest eigenvalue of a large dimensional covariance matrix", see also Rudelson and Vershynin's "The smallest singular value of a random rectangular matrix" ) – Kevin P. Costello May 3 '12 at 18:49

In relation to the first question, a recent breakthrough result of Konstantin Tikhomirov answers affirmatively an old conjecture attributed to Von Neumann, namely that for $$M_n$$, an $$n\times n$$ random matrix with independent $$\pm 1$$ entries

$$\mathbb{P}(M_{n}\ \text{is singular})=\left(\frac{1}{2}+o(1)\right)^n.$$

Here is the pre-print and a relevant entry in Gil Kalai's blog can be found here.