[proofplan]
We apply the [Householder-John Theorem](/theorems/1390) with $B = D + L_0$ (the Gauss-Seidel splitting), where $A = D + L_0 + U_0$ with $D$ diagonal, $L_0$ strict lower triangle, and $U_0$ strict upper triangle. The iteration matrix is $H_{GS} = I - B^{-1}A = -(D + L_0)^{-1}U_0$. We need to verify the two hypotheses: (1) $A$ is SPD (given), and (2) $B + B^\top - A$ is SPD. We compute $B + B^\top - A = (D + L_0) + (D + U_0) - (D + L_0 + U_0) = D$, and show that $D$ is SPD because $A$ is SPD.
[/proofplan]
[step:Identify the Gauss-Seidel splitting and compute $B + B^\top - A$]
Write $A = D + L_0 + U_0$, where $D = \operatorname{diag}(a_{11}, \ldots, a_{nn})$, $L_0$ is the strict lower triangle of $A$, and $U_0$ is the strict upper triangle. Since $A$ is symmetric, $U_0 = L_0^\top$.
The Gauss-Seidel splitting takes $B = D + L_0$. Its transpose is $B^\top = D + L_0^\top = D + U_0$.
Compute:
\begin{align*}
B + B^\top - A &= (D + L_0) + (D + U_0) - (D + L_0 + U_0) = D.
\end{align*}
[guided]
The computation simplifies beautifully for the Gauss-Seidel splitting. The matrix $B = D + L_0$ contains the diagonal and lower triangle of $A$, while $B^\top = D + U_0$ contains the diagonal and upper triangle. Their sum is $2D + L_0 + U_0 = D + A$, so $B + B^\top - A = D$.
This means the Householder-John hypothesis "$B + B^\top - A$ is SPD" reduces to the single condition "$D$ is SPD," i.e., all diagonal entries $a_{ii}$ are positive. The condition on $B + B^\top - A$ does not introduce any additional constraint beyond what $A$ being SPD already provides.
[/guided]
[/step]
[step:Verify that $D$ is symmetric positive definite]
We show that $D = \operatorname{diag}(a_{11}, \ldots, a_{nn})$ is SPD. $D$ is symmetric (it is diagonal). For positive definiteness, we need $a_{ii} > 0$ for all $i$.
Let $e_i \in \mathbb{R}^n$ denote the $i$-th standard basis vector. Since $A$ is symmetric positive definite:
\begin{align*}
a_{ii} = e_i^\top Ae_i > 0 \quad \text{for each } i = 1, \ldots, n.
\end{align*}
Therefore $D$ is positive definite: for any $x = (x_1, \ldots, x_n)^\top \neq 0$,
\begin{align*}
x^\top Dx = \sum_{i=1}^n a_{ii} x_i^2 > 0,
\end{align*}
since all $a_{ii} > 0$ and at least one $x_i \neq 0$.
[/step]
[step:Apply the Householder-John Theorem to conclude convergence]
We have verified the two hypotheses of the [Householder-John Theorem](/theorems/1390):
1. $A$ is symmetric positive definite (given by hypothesis).
2. $B + B^\top - A = D$ is symmetric positive definite (established in the previous step).
The Householder-John Theorem gives $\rho(H_{GS}) < 1$, where $H_{GS} = I - B^{-1}A = I - (D + L_0)^{-1}A$ is the Gauss-Seidel iteration matrix.
By the [Spectral Radius Criterion](/theorems/1387), $H_{GS}^k z \to 0$ for every $z \in \mathbb{R}^n$, and hence the Gauss-Seidel method converges by the [Error Propagation](/theorems/1386) theorem.
[guided]
The entire proof reduces to a one-line computation: $B + B^\top - A = D$, followed by the observation that $A$ SPD implies $D$ SPD. The Householder-John theorem does all the heavy lifting.
Why is $D$ automatically SPD when $A$ is SPD? The diagonal entries of $A$ are $a_{ii} = e_i^\top A e_i$. Since $A$ is SPD, every such quadratic form with a nonzero vector is strictly positive. The diagonal of any SPD matrix is therefore strictly positive, which is exactly what it means for a diagonal matrix to be SPD.
It is worth noting that the Gauss-Seidel convergence result for SPD matrices is *stronger* than the diagonal dominance result ([Convergence for Diagonally Dominant Matrices](/theorems/1389)): there exist SPD matrices that are not diagonally dominant, yet the Gauss-Seidel method still converges for them. The SPD condition is a spectral/energy condition, while diagonal dominance is an entrywise condition — the former is more general for this class of problems.
[/guided]
[/step]
