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.



  • 1
    $\begingroup$ How small are $m$ and $n$? Less than 10? Less than 100? $\endgroup$ – Yemon Choi May 1 '12 at 4:04
  • 1
    $\begingroup$ Maybe the standard $\sqrt{m}+\sqrt{n}$ bound applies here too. $\endgroup$ – Suvrit May 1 '12 at 4:36
  • $\begingroup$ 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 $\endgroup$ – 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 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.

  • $\begingroup$ Thank you very much for your time to code this! It was very helpful! $\endgroup$ – Kostas May 1 '12 at 20:53
  • $\begingroup$ 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. $\endgroup$ – Emilio Pisanty May 2 '12 at 0:12
  • $\begingroup$ 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. $\endgroup$ – Kevin P. Costello May 2 '12 at 16:59
  • 1
    $\begingroup$ 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. $\endgroup$ – Kevin P. Costello May 3 '12 at 18:40
  • 1
    $\begingroup$ (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" ) $\endgroup$ – Kevin P. Costello May 3 '12 at 18:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.