<s>[INST] 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.
 [/INST] 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.
</s>