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.

  • 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

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

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

  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.

  • $\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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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