Skip to main content
5 of 6
improved clarity

Existence of a matrix with bounded entries with large smallest singular value

Is the following statement true?

For all $n$ large enough, there exists an $M_n \in [-1,1]^{n \times n}$ such that the smallest singular value of $M_n$, $\sigma_n(M_n) \gtrsim \sqrt{n}$.

If $n$ is such that there exists a Hadamard matrix of order $n$, we can take $M_n$ to be that.

On Terry Tao's blog, it says that:

To oversimplify somewhat, the conclusion of this work is that the least singular value $\sigma_n(M_n)$ has size comparable to $1/\sqrt{n}$ with high probability.

This does not rule out the possibility that for all $n$ large enough, the random signed matrix $M_n$ satisfies $\sigma_n(M_n) \gtrsim \sqrt{n}$ with a tiny non-zero probability.