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

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?

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) 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
• Thank you for your answer. But I'm wondering what is $q$ in your proof? – bernard May 14 '20 at 11:39
• @bernard. Oups, $q$ is the quadratic form associated with \$A*. I edit the post. – Denis Serre May 14 '20 at 12:18
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$$.