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.

share|improve this question
add comment

1 Answer

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$.

share|improve this answer
    
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
1  
@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
1  
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
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.