Finding Matrix of Minimum 2-norm to obtain singular matrix

Let $$A,X \in \mathbb{R}^{m \times m}$$ with rank$$(A) = m$$. Find $$X$$ of minimum 2-norm for $$A + X$$ to be singular.

My thoughts:

Since we want $$A + X$$ to be singular, we want to show that it has a zero determinant (or show that it has a zero eigenvalue). Now, since rank$$(A) = m$$, this means $$A$$ is full rank, hence it is invertible (non-singular).

My first thought was to take $$X$$ and look at its singular value decomposition (SVD): Let $$X = U\Sigma V^T,$$ where $$U$$ and $$V$$ are orthogonal real $$m\times m$$ matrices and $$\Sigma$$ is a diagonal matrix with $$\Sigma = \begin{pmatrix} \sigma_1 \\ & \sigma_2 \\ & & \ddots \\ & & & \sigma_m\end{pmatrix},$$ where $$\sigma_1 \geq \dots \sigma_m \geq 0$$ are the singular values of $$X$$. We want to minimize $$||X||_2$$, where $$||X||_2 = \sigma_1$$, the largest singular value of $$X$$. So, we want to minimize $$\sigma_1$$.

Beyond this, I'm not sure what to do. Might this be a "rank 1 approximation"- type problem?

• Your intuition is correct. Write the SVD as a sum of rank-1 matrices and you should get there Aug 13, 2023 at 18:52

1 Answer

Some hints:

Let $$\underline{\sigma}$$ be the smallest singular value of $$A$$.

Show that $$\|Ax-Bx\| \ge (\underline{\sigma}-\|B\|) \|x\|$$, that is $$\|A-B\| \ge \underline{\sigma}-\|B\|$$. In particular, if $$\|B\| < \underline{\sigma}$$ then $$A-B$$ is non singular.

Now use the SVD of $$A$$ to construct a matrix $$B$$ of norm $$\underline{\sigma}$$ such that $$A-B$$ is singular.