12
$\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$ Commented May 1, 2012 at 4:04
  • 1
    $\begingroup$ Maybe the standard $\sqrt{m}+\sqrt{n}$ bound applies here too. $\endgroup$ 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$ Commented May 1, 2012 at 7:16

3 Answers 3

Reset to default
6
$\begingroup$

https://web.archive.org/web/20180721063651/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$
0
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$ 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$ 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$ 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$ 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$ Commented May 3, 2012 at 18:49
4
$\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$ Commented Apr 12, 2019 at 14:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.