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.

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

3 Answers 3

Reset to default
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

Improve this answer
$\endgroup$
1
  • $\begingroup$ The link is broken, the last indexed version can be found on the archive. $\endgroup$
    – user114668
    Commented 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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you very much for your time to code this! It was very helpful! $\endgroup$
    – Kostas
    Commented 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$
    – Emilio Pisanty
    Commented 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$
    – Kevin P. Costello
    Commented 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$
    – Kevin P. Costello
    Commented 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$
    – Kevin P. Costello
    Commented 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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ A comment on Gil's blog notes this earlier claim of the same result: arxiv.org/pdf/1511.05283.pdf . Any reason to discount that? $\endgroup$
    – Brendan McKay
    Commented Apr 12, 2019 at 14:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .