Singular values of rounding matrix

Question

I have a matrix $A \in \mathbb{R}^{n\times n}$ with $\text{rank}(A)=n$. I do a rounding operation (rounding to nearest integer) on each element of $A$. So new rounded matrix $B$ is actually $B=A+E$ where $E \in \mathbb{R}^{n\times n}$ is the matrix of fractional values that rounds $A$ to $B$. For any such $E$, can we say anything about its singular values ? Also can we find, lowest possible value of $\alpha$ such that $\|E\| \leq \alpha$ ?

Answer 1

Notably, all we can say about the entries of $E$ is that they all have magnitude at most $5$. Of course, this means that the Frobenius norm satisfies $\|E\| \leq (0.5) \cdot n = \frac n2$ (and $\alpha = \frac n2$ is indeed the lowest possible upper bound). We easily get the result that all singular values of $E$ are at most $\frac n2$. Moreover, we could note that in general, $$ \|E\| = \sqrt{\sigma_1^2(E) + \cdots + \sigma_n^2(E)} \leq \frac n2 $$ we can't say much more about the singular values of $E$ directly.

Bhatia's Matrix Analysis provides a useful result:

(using problem III.6.5) For any two operators $A, E$ and any two indices $i, j$ such that $i + j = n +1$, we have $$ \sigma_{i+j-1}(A + E) \leq \sigma_i(A)+ \sigma_j(E)\\ \sigma_{i}(A + E) \geq |\sigma_{i + j-1}(A) - \sigma_j(E)| $$