I am trying to get a lower bound (or even the exact value) of


$$
\min\_{X \in \mathbb{R}^{n\times n}} \|X - I\_n\|\_{\infty} \enspace \text{s.t.} \enspace \mbox{Rank}(X) = m
$$


where $m \leq n$, and the infinity norm is


$$ \| X \|\_{\infty} := \max\_{ij}|X\_{ij}| $$


I have a very simple lower bound, obtained with norm equivalence:


$$\|X - I\_n\|\_{\infty} \geq \frac{1}{n} \|X - I\_n\|\_F\geq \frac{\sqrt{n - m}}{n}$$


but this is obviously not tight, and experiments suggest that the scaling is wrong.


Thanks a lot ! :)



Distance of low-rank matrices to the identity for the $\infty$-norm
Theorem 1.1 from Alon's paper ["Perturbed identity matrices have high rank: proof and applications"](https://www.tau.ac.il/%7Enogaa/PDFS/identity1.pdf) says that if $\|X-I\_n\|\_\infty<c$ with $1/(2\sqrt n)<c<1/4$, then $m\gg \log n/(c^2\log(1/c))$ with an absolute implicit constant. This is exactly what you need: if $X$ is close to the identity matrix in the infinity norm, then the rank of $X$ is large. Incidentally, ALon's bound is sharp up to a logarithmic factor; therefore, you cannot expect to get much better estimates.


