1
$\begingroup$

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?

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

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .