# Maximum Singular Value of a random +1/-1 matrix

Hi,

Define a matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ such that each element is independently and randomly chosen with probability 0.5 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 +1/-1.

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

Thank you very much for any pointer or any thoughts.

Best,

Alex

-
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

-

For what it's worth, here's some numerical data in Mathematica CDF format.

Edit: I've been playing around some more 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 - @Alex, 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