6
$\begingroup$

Suppose I have a matrix $S$ having a one-dimensional nullspace $\{ e \}$ 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 Answers 1

7

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

  • 0
    Slick solution! :D2010-08-20
  • 0
    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.2010-08-20
  • 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$.2010-08-20
  • 0
    Il-Bhima: CG is *always* unstable if the symmetric matrix is not positive definite. :)2010-08-20
  • 0
    @Agusti -- yes, thanks. That's what I meant. I made the edit.2010-08-20
  • 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.2010-08-20