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](https://terrytao.wordpress.com/2009/03/04/random-matrices-the-distribution-of-the-smallest-singular-values), 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.



Existence of a matrix with bounded entries and large smallest singular value
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](https://en.wikipedia.org/wiki/Discrete_sine_transform). 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](https://arxiv.org/abs/2207.07523). Thanks to Aleksei Kulikov for making me aware of this paper.


