Skip to main content
1 of 6

Existence of a signed matrix with large smallest singular value

Is the following statement true?

For all $n$ large enough, there exists an $M_n \in \{\pm 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.

It says here on Terry Tao's blog 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.