Let $ L= \left[ \begin{matrix} 0 & \ldots & & & &0 \\ a & 0 & \ldots & & &0 \\ 0 & a & 0 & \ldots & &0\\ 0 & 0& a & 0 & \ldots & 0 \\ \vdots \end{matrix} \right] $

that is $L$ has its sub-diagonal equal to $a$, the other elements are zero.

Show that

$$ \rho(L+L^T)^2 = \rho((\text{Id}+L)^{-1} L^T) $$

where $\rho(M)$ is the spectral radius of the matrix $M$.


I can only remember the following proof. So there might be an easier way.

Definiton 1: Let $A∈ℝ^{n×n}$ be a matrix with $$A=L+D+R,$$ with $D$ invertible. If the eigenvalues of the matrix $$J(α)=-D^{-1}\{αL+α^{-1}R\}, α∈ℂ\setminus\{0\}$$ are independent of $α$, then we call $A$ consistently ordered.

Theorem 1: Tri-diagonal matrices of the following form are consistently ordered. $$\begin{pmatrix} d_1 & a_{12} & \\ a_{21}& d_2 & \ddots \\ & \ddots & \ddots & a_{n-1,n} \\ & & a_{n-1,n} & d_n \end{pmatrix}$$ with $d_i\neq0$. Why? Let $T=\text{diag}(1, α, …, α^{n-1})$, then we can do a similarity transformation: $$-J(α) = αD^{-1}L+α^{-1}D^{-1}R = T(D^{-1}L+D^{-1}R)T^{-1}$$ And we know that eigenvalues are preserved under similarity transformation.

In your case it is $A=L+I+L^\top$, which is a tri-diagonal matrix. Hence your matrix is consistently ordered. And the two matrices where you want to know the spectral radii are simply the Jacobi-matrix $J=D^{-1}(L+R)$ and the Gauß-Seidel-matrix $H=-(D+L)^{-1}L^\top$ of that $A$.

Theorem 2: Let $A∈ℝ^{n×n}$ be a consistently ordered matrix. Then the eigenvalues $μ∈σ(J)$ and $λ∈σ(H_ω)$ fulfil: $$\sqrt{λ}ωμ = λ+ω-1.$$

Probably $ω∈(0,2)$, so that the SOR-method converges. I don't remember the proof. You should be able to find it somewhere in these lecture notes. (I was an exercise group leader to that lecture, that is why I remember this answer.)

The Gauß-Seidel-matrix is the special case of the SOR-matrix $H_ω$ with $ω=1$. Hence: $$ρ(H_1)=ρ(J)^2$$

  • $\begingroup$ What do you mean by "the eigenvalues fulfil"? There is more than one eigenvalue for both matrices. $\endgroup$ – amsmath Oct 16 '17 at 15:38
  • $\begingroup$ Also, in your definition (and in Theorem 1) you should add that $D$ is supposed to be invertible and $\alpha\neq 0$. $\endgroup$ – amsmath Oct 16 '17 at 15:44
  • $\begingroup$ Thx for your comments. I corrected what you mentioned in the second comment. About the first one: Well both matrices have eigenvalues and for each eigenvalue $λ_i$ of $J$ there is an eigenvalue $µ_i$ of $H_ω$ which is related by that equation. $\endgroup$ – P. Siehr Oct 16 '17 at 16:15
  • $\begingroup$ Ok. I think you should correct this, too, because it is very confusing without that explanation. And is it clear that $H_\omega$ has only non-negative real eigenvalues? $\endgroup$ – amsmath Oct 16 '17 at 16:23
  • $\begingroup$ @amsmath - No, in general they are complex. $\endgroup$ – P. Siehr Oct 17 '17 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.