# Proving that product of general matrices has small spectral radius

In a Jacobi type of iteration for finding solution to a linear system $$Ax=b$$, one writes

$$x_i^{(k+1)} = Gx_i^{(k)}+c,$$

where $$x_i$$ is the $$i$$-th component of vector $$x$$ and $$G=D^{-1}N$$, $$c = D^{-1}b$$.

Here we take $$A=D+N$$, with $$D$$ the diagonal part of $$A$$ and $$N$$ the rest of $$A$$, i.e. $$N = A-D$$, so that

$$x_i^{(k+1)} = -D^{-1}Nx_i^{(k)}+D^{-1}b$$

There is a theorem which says that if the spectral radius $$\rho(A)<1$$ then this scheme converges, so I need to show that $$D^{-1}N$$ has spectral radius less than $$1$$.

In my case, $$A=\begin{bmatrix} -6&1 & 1 & 1 &0 & 0 & 0&\dots& 0 \\ 1 & 1 & -6 & 1 & 1 & 1 &0&\dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots&\ddots&0\\ \vdots & \vdots & \vdots & \vdots & \dots & \dots & \dots&-6 & 1\\ 0 & \dots & 0 & 0 & 0 & 1 & 1 & 1 & -6 \end{bmatrix}$$, so

$$D=diag\{-6,\dots, -6\}$$, $$\implies D^{-1}=diag\{-1/6, \dots, -1/6\}$$,

and $$N=\begin{bmatrix} 0&1 & 1 & 1 &0 & 0 & 0&\dots& 0 \\ 1 & 1 & 0 & 1 & 1 & 1 &0&\dots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots&\ddots&0\\ \vdots & \vdots & \vdots & \vdots & \dots & \dots & \dots&0 & 1\\ 0 & \dots & 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix}$$.

One can evaluate the product $$D^{-1}N$$ to be

$$\begin{bmatrix} 0&-1/6 & -1/6 & -1/6 &-1/6 & -1/6 & -1/6&\dots& -1/6 \\ -1/6 & 0 & -1/6 & -1/6 & -1/6 & -1/6 &-1/6&\dots & -1/6 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots&\ddots&-1/6\\ \vdots & \vdots & \vdots & \vdots & \dots & \dots & \dots&0 & -1/6\\ -1/6 & \dots & -1/6 & -1/6 & -1/6 & -1/6 & -1/6 & -1/6 & 0 \end{bmatrix}$$

It can be shown that the spectral radius of this product is $$1/2$$ (if I'm not mistaken). But is there a more elegant way to show that $$\rho(D^{-1}N)<1$$? I don't really like the direct way of showing this.

The spectral radius of the last shown matrix for $$D^{-1}N$$ is $$(n-1)/6$$, where $$n\times n$$ is the size of the matrix. Thus the spectral radius is larger than $$1$$ for $$n\ge8$$.
However, from the previous parts of the question, $$D^{-1}N=-\frac{1}{6}J$$ where $$J=\begin{pmatrix}0&1&1&1&0&\cdots&0\\1&0&1&1&1&\cdots&0\\&\ddots&0&0&0&\cdots&1\end{pmatrix}$$ i.e., there is a band of 1s on first three off-diagonals on both sides.
For a symmetric matrix, the spectral radius is equal to the largest value of the numerical range, $$\{x^*Ax:\|x\|_2=1\}$$.
The extent of the numerical range of $$J$$ is given by maximizing the following expression for $$x=(a_1,\ldots,a_n)$$ unit, $$\begin{pmatrix}a_1,&\ldots,&a_n\end{pmatrix}\begin{pmatrix}0&1&\cdots&0\cr 1&0&\cdots&1\cr&\ddots\cr0&1&\cdots&0\end{pmatrix}\begin{pmatrix}a_1\cr\vdots\cr a_n\end{pmatrix}=\sum_{|i-j|\le3,i\ne j}a_ia_j$$ Now \begin{align*}\sum_{|i-j|\le3,i\ne j}a_ia_j &=2(\sum_{i=1}^{n-1}a_ia_{i+1}+\sum_{i=1}^{n-2}a_ia_{i+2}+\sum_{i=1}^{n-3}a_ia_{i+3})\\ &\le \sum_{i=1}^{n-1}a_i^2+\sum_{i=2}^na_i^2+\sum_{i=1}^{n-2}a_i^2+\sum_{i=3}^na_i^2+\sum_{i=1}^{n-3}a_i^2+\sum_{i=4}^na_i^2\\ &<6\sum_{i=1}^na_i^2=6\end{align*}
That is, the spectral radius of this $$D^{-1}N$$ is less than 1, as required.
• Thank you. But can you please provide some details for your last expression? I got tangled in notation: where is the $|i-j|\le 3$ coming from? And the rest of the RHS doesn't seem quite clear yet. – sequence Feb 21 at 15:38
• The $|i-j|\le3$ refers to the three off-diagonals; $i\ne j$ to omit the main diagonal. Now the sum is equivalent to three sums along the diagonals, times two (because there are two diagonals each). The first inequality is the usual $ab\le(a^2+b^2)/2$. – Chrystomath Feb 21 at 16:40