# 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

Edit: I've been playing around some more and this histogram http://quicc.net/other_files/randomsvdhistogram.png 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.
• 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