I know that the Gauss-Seidel method is guaranteed to converge given that the matrix you want to solve is positive definite. I've looked at the proofs of convergence, and it appears that one cannot change the assumption so that the smallest eigenvalue is zero, without coming up with a totally new proof. This makes sense, since of course a PSD matrix is singular. 


However, assuming that $b$, the right hand side of the equation $A \cdot x = b$ is in $A$'s image (and that $A$ is PSD) is Gauss-Seidel guaranteed to converge? 



Is Gauss-Seidel guaranteed to converge on *semi* positive definite matrices?
This is an interesting question, to which the answer is **positive**.


Here is the proof. Of course, for the method to make sense, we must assume that the diagonal $D>0$. The notations below are borrowed from Section 12.3.2 of my book *Matrices* (2nd edition, Springer-Verlag, GTM **216**). Let $G=(D-E)^{-1}E^T$ be the iteration matrix. One checks easily that $\ker A$ is the eigenspace of $G$, associated with the eigenvalue $\lambda=1$. The corresponding eigenspace for $G^T$ is $(D-E)^T\ker A$, for which we find that $G$ has the invariant subspace $(D-E)^{-1}R(A)$. This can be verified directly with the help of the formula $G(D-E)^{-1}A=(D-E)^{-1}AG$. It turns out that $1$ is semi-simple: if $Gw=w+v$ and $Gv=0$, we obtain $v^T(D+A)v=0$, hence $v=0$. Therefore
$${\mathbb R}^n=\ker A\oplus (D-E)^{-1}R(A)$$
is a decomposition into $G$-invariant subspaces.


There remains to prove that for every vector $x^0$, the sequence $x^m:=G^mx^0$ is convergent. Let us decompose $x^m=y^m+z^m$, according to the invariant subspaces above. We have $y^m=y^0$, so this part is obviously convergent. There remains to prove that the spectral radius of the restriction $g$ of $G$ to $(D-E)^{-1}R(A)$ is smaller than $1$. This is proved exactly the same way as in Lemma 20 of the reference. We have to prove that if $x\in(D-E)^{-1}R(A)$, then $(Gx^T)A(Gx)\le x^TAx$, and equality implies $x=0$. With $y=(D-E)^{-1}Ax$, we have
$$(Gx^T)A(Gx)-x^TAx=-y^TDy\le0.$$
If the right-hand side vanishes, then $y=0$, which means $x\in\ker A$, hence $x=0$. Q.E.D


