11
$\begingroup$

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.

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

3 Answers 3

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ The link is broken, the last indexed version can be found on the archive. $\endgroup$
    – user114668
    Mar 30, 2019 at 21:45
5
$\begingroup$

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

histogram

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.

$\endgroup$
7
  • $\begingroup$ Thank you very much for your time to code this! It was very helpful! $\endgroup$
    – Kostas
    May 1, 2012 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$ May 2, 2012 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$ May 2, 2012 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$ May 3, 2012 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$ May 3, 2012 at 18:49
3
$\begingroup$

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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