Is the matrix positive definite given the Gauss-Seidel method converges?

Question

I know that the Gauss-Seidel method converges given that the matrix you want to solve is symmetric positive definite. However, I'm wondering if the "converse" of the statement is true. Namely, if $A$ is a symmetric matrix with positive diagonals and the Gauss-Seidel method converges for all initial guess $x_0$, is $A$ guaranteed to be positive definite?

Answer 1

There is an interesting though partial answer to your question:

Under your assumptions, it is not possible that the signature of $A$ be $(n-1,1)$ (exactly one negative eigenvalue).

Proof: With standard notations, $A=D-E-E^T$ where $E$ is strictly triangular and $D$ diagonal. By assumption, $D>0_n$. Notice that the assumption of convergence implies that $A$ is invertible.

The iteration matrix is $G=(D-E)^{-1}E^T$. The quadratic form $q(x):=x^TAx$ satisfies the identity $$q(Gx)+y^TDy=q(x),\qquad y:=x-Gx=(D-E)^{-1}Ax.$$ This implies that $G$ preserves the set $q<0$. If the signature of $A$ is $(n-1,1)$, this set is the union of two opposite convex cones $\pm K$. Thus $\pm G$ preserves $K$. One deduces from Brouwer fixed point theorem that $G$ admits an eigenvector $x\in K$, $Gx=\mu x$. Then $\mu^2q(x)<q(x)<0$ gives $|\mu|>1$, which contradicts the convergence of the Gauss-Seidel method.

Nota. The identity about $q$ is the one used to prove the convergence of the method when $A$ is positive definite. More generally, it is used to prove that any method with iteration matrix $L:=M^{-1}N$ where $A=M-N$, such that both $A$ and $M^T+N$ are positive definite, is convergent

Answer 2

Note that, as Prof. Serre's answer, $q(x)=x^TAx$ decreases as the iterations go on. In particular, consider $Ax=b$ with $b=0$, we have $x_0^TAx>x_1^TAx_1>\cdots>x^T_nAx_n>\cdots$ and $\lim\limits_{n\to \infty} x_n=0$. If $A$ is not positive definite, there exists $x_*$ such that ${x_*}^{T}Ax_*<0$. Take $x_0=x_*$ then we have $0>x_0^TAx_0>\cdots$, thus $\lim\limits_{n\to \infty} x_n^TAx_n<0$, which contradicts to $\lim\limits_{n\to \infty} x_n=0$.