Invertibility of a Rank-One Update of a Symmetric Matrix

Question

I want to find a necessary and sufficient condition for $B = A + x \, y^\top$ to be invertible, where $A$ is assumed to be symmetric and $x, \, y \, \in \mathbb{R}^n-\{0\}$. I know that the following holds

Theorem. Let $E = I - \alpha \, u \, v^\top$ be a rank-one modification of the identity $I$, where $\alpha \in \mathbb{R} - \{0\}$ and $u, \, v \, \in \mathbb{R}^n-\{0\}$. Then, $E$ is invertible if and only if $\alpha \, u^\top v -1 \ne 0$. Furthermore, $E^{-1} = I - \beta \, u \, v^\top$ with $\beta = \alpha/(\alpha \, u^\top v - 1) $.

Now, I want to find a necessary and sufficient condition for invertiblity of $B$ by using this theorem. I suspect that it should be the positive definiteness of $A$, but I am having a little bit of difficulty to prove this.

Answer 1

If $A$ is invertible, then $A+xy^\top=A(I+\xi y^\top)$ with $\xi=A^{-1}x$. Therefore, $A+xy^\top$ is invertible iff so is $I+\xi y^\top$, and you can use your general criterion.

If $A$ is not invertible, then $A=a_1b_1^\top+...+a_rb_r^\top$ with $r=\mathrm{rank}\,A$, in particular $r<n$. Then $A+xy^\top=a_1b_1^\top+...+a_rb_r^\top+xy^\top$ has rank $r$ iff either $x$ is in the linear span of the $a_i's$ or $y$ is the the linear span of the $b_i$'s, otherwise it has rank $r+1$. Hence, if $A$ is not invertible, $A+xy^\top$ is invertible iff $A$ has rank $n-1$ and $y^\top$ does not belong to the linear span of the rows of $A$ and $x$ does not belong to the linear span of the columns of $A$.

The condition slightly simplifies if $A$ is symmetric.

Answer 2

If $A$ is invertible, the invertibility of $B$ is equivalent to $1 + y^\top A^{-1} x \ne 1$ and $B^{-1}$ will be given by the Sherman-Morrison formula.

$$B^{-1} = (A + x \, y^\top)^{-1} = A^{-1} - \frac{A^{-1} x \, y^\top A^{-1}}{1 + y^\top A^{-1} x}$$

If $A$ is positive definite, so all of its eigen-values are positive, so $\lambda_i > 0, \quad i=1, \dots, n$. This implies that $\det A = \lambda_1 \dots \lambda_n \ne 0$, which is equivalent to $A$ being invertible. Consequently, the Sherman-Morrison formula also holds when $A$ is positive definite.

Answer 3

The rank-one update formula for determinant is $\det(A+xy^T)=\det(A)+y^T\operatorname{adj}(A)x$. Since $\det(A)+y^T\operatorname{adj}(A)x=\det(A)(1+y^TA^{-1}x)$ when $A$ is invertible, the followings are equivalent:

• $A+xy^T$ is invertible;
• $\det(A)+y^T\operatorname{adj}(A)x\ne0$;
• ($A$ is invertible and $1+y^TA^{-1}x\ne0$) or ($A$ is singular and $y^T\operatorname{adj}(A)x\ne0$).

This equivalence is valid over any field. Whether $A$ is real symmetric is irrelevant.