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

Question

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.

Answer 1

The OP wrote $[-1, 1]$ but refers to Hadamard matrices, whose entries are more strongly in $\{ -1, 1 \}$. Assuming that the former is meant, we can do this with the sine transform matrix. Take $$M_{ab} = \sin \frac{\pi a b}{n+1} \ \text{for} 1 \leq a,b \leq n.$$ Then $$M M^T = \frac{n+1}{2} \text{Id}_n$$ so the singular values of $M$ are $\sqrt{\tfrac{n+1}{2}}$.

I imagine that other variants on the discrete Fourier transform would work simmilarly.

---

If you do want entries in $\{ -1, 1 \}$, this is also possible; see Theorem 1.2 in Approximately Hadamard matrices and Riesz bases in random frames. Thanks to Aleksei Kulikov for making me aware of this paper.