Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose I have a matrix $S$ having a one-dimensional nullspace $\lbrace e \rbrace$ such that $S + ee^\top$ is a positive definite symmetric matrix.

Now let $b \in Range(S)$ and suppose I solve the equation $(S + ee^\top)x = b$ is there anyway I can derive the solution $x'$ of the equation $Sx' = b$? I was trying a Sherman Morrison Woodbury type formula, but this fails since the denominator is 0.

Any help would be appreciated.


1 Answer 1

up vote 5 down vote accepted

Suppose $x$ is the solution to $(S+ee^T)x = b$. Since $b\in Range(S)$, we may write $b = Sz$ for some z. Now compute: $$ e^T(S+ee^T)x = e^Tb = e^TSz $$ Since S is symmetric, and e is in its nullspace, we have $e^TS = 0$. So the above equation simplifies to $e^Tx = 0$. But this implies $$ (S+ee^T)x = Sx $$ So x is a solution to the equation $Sx=b$ as well. As noted above, the solution to $Sx=b$ is not unique; $x + \lambda e$ is also a solution for any real $\lambda$.

Slick solution! :D –  J. M. Aug 20 '10 at 12:37
Yes, thanks for confirming this! Although this is a mathematically trivial result, it's interesting to see that a CG solver will suffer from massive instability when solving Sx = b, but work perfectly well for (S + ee^T)x = b, although the solution is the same. –  Il-Bhima Aug 20 '10 at 13:25
@Laurent. Maybe you wanted to say "$x+\lambda e$ is also a solution for any real $\lambda$"? In fact, these are all the solutions, since $[e]$ is the nullspace of $S$. –  a.r. Aug 20 '10 at 13:53
Il-Bhima: CG is always unstable if the symmetric matrix is not positive definite. :) –  J. M. Aug 20 '10 at 14:01
Notice what is going on here... adding ee^T "fills in" S so that its zero eigenvalues are made to be nonzero. This makes it invertible, and the solution to (S+ee^T)x = b also satisfies Sx=b. A more general result holds: Suppose S is any rank-deficient matrix (even non-symmetric, or non-square!). If T "fills in" the zero singular values of S such that S+T is full-rank, and b is in Range(S), then the solution to (S+T)x=b is also a solution to Sx=b. If you want a proof, let me know. –  Laurent Lessard Aug 20 '10 at 18:37

This site is currently not accepting new answers.

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