Consider a random $m\times n$ matrix $M$ with elements from $\{-1,1\}$ and $m<n$.
What is known about the expected value of the smallest eigenvalue of $MM^T$?
The following picture shows numerical results for the expected value of the smallest eigenvalue of $MM^T$ for $n=120$ and $m=1 \dots 60$.
- How can you prove that the expected value is monotonically decreasing?
- Is it possible to get an estimate for the expected value?
Best Answer
Let $\sigma_1\geq\cdots \geq\sigma_n$ b the singular values of $M$. The case $m=n$ is studied by Terrific Tao and Vu in
https://arxiv.org/abs/0903.0614
If the $(m_{ij})$ are iid and satisfy $\operatorname{E}(m_{ij})=0,\operatorname{Var}(m_{ij})=1$, then, roughly speaking, $\sigma_1^2\approx 4n$ (with probability $1$) and $\operatorname{E}(\sigma_n^2)=O(\frac{1}{n})$.
Here, you assume that $m<n$. According to the paper above, the result concerning $\sigma_m^2$ is the same if $m$ is close to $n$, else see the edit below.
When $m$ is fixed and $n$ increases, $||M||$ and $||MM^T||$ increase; yet $\sigma_m^2$ increases much faster than the two previous ones, that is astonishing.
EDIT. The case $m<n$ is solved by Bai,Yin; cf. Theorem 2.1 in
https://arxiv.org/abs/1003.2990
Assume that the $(m_{ij})$ are iid, satisfy $\operatorname{E}(m_{ij})=0,\operatorname{Var}(m_{ij})=1$ and have a finite fourth moment. If $n\rightarrow \infty$ where $\frac{m}{n}$ is a constant number, then $\frac{\sigma_m}{\sqrt{n}}\rightarrow 1-\sqrt{\frac{m}{n}}$ and $\frac{\sigma_1}{\sqrt{n}}\rightarrow 1+\sqrt{\frac{m}{n}}$ almost surely. In other words, for $n$ great enough, $\sigma_m^2\approx (\sqrt{n}-\sqrt{m})^2$ and $\sigma_1^2\approx (\sqrt{n}+\sqrt{m})^2$ (cf. Theorem 2.3). Note that to estimate $\sigma_m$ when $m=n$ is more difficult than when $m<n$.