Given $A$ non-singular, find $E$ with minimal $\sigma_{\mathrm{max}}(E)$ such that $A+E$ is singular

Question

As given in the title, there is a matrix given, namely:

$A = \begin{bmatrix}-1 & 0& 0& 0\\1& -1& 0& 0\\1& 1& -1& 0\\1& 1& 1& -1\end{bmatrix}$

Obviously non-singular. The question is to find a matrix $E$ with the smallest value of $\bar{\sigma}(E)$ (smallest maximum singular value) such that $A+E$ is singular.

Intuitively, I would suggest a zero matrix with a $1$ somewhere on the diagonal, thus $\bar{\sigma}(E)=1$. However, I cannot prove this or cannot find a method to show this is true except for somewhat trivial solutions. Can you help me with this problem?

Answer 1

Let $A=U\Sigma V^T$ be the singular value decomposition of $A.$

Let $\sigma$ be the smallest singular value of $A$ and $E=-UV^T\sigma .$ Then $\sigma$ is the maximum singular value of $E$ and $$ A+E = U\Sigma V^T - UV^T\sigma = U(\Sigma - \sigma I)V^T $$ which is obviously singular, because one of the diagonal elements of the diagonal matrix $(\Sigma - \sigma I)$ is $0.$

This is no proof that this is the best choice, but it yields the same results as Robert Israel's numerical approach.

Answer 2

Suppose we try to minimize $t$ subject to $\det(A+E) = 0$ and $E^\top E = t I$ (thus $E$ will be $\sqrt{t}$ times an orthogonal matrix, and its singular values will be $\sqrt{t}$). Using numerical optimization in Maple, I found $$ \left[ \begin {array}{cccc} 0.0766944544642310516& 0.110934687964761858& 0.0515196928978350066& 0.111875492607389368 \\ - 0.125748167833764246&- 0.0412084249991368223& 0.00261449456708803037& 0.125862533565759133\\ 0.100687117836105927&- 0.138912309777921100& 0.0309392042662888223& 0.0544719108832984883\\ - 0.0390693253668941698&- 0.00759472509780651731& 0.172454632419852177&- 0.0451027345603461291 \end {array} \right] $$

which has singular values approximately $0.182644323596164$.