Spectral radius of matrix from SOR method Suppose we write a matrix $A = L + D + U$  with lower triangular, diagonal and upper triangular parts. When trying to solve the equation $Ax=b$, we use a successive overrelaxation technique such that $x^{k+1}=\left(-\omega U+(1-\omega)D\right)(D+\omega L)^{-1}x^k + \omega (D+\omega L)^{-1}b$. Start with a guess for $x^0$ and eventually it will converge to the right $x$
It turns out that the spectral radius of $\left(-\omega U+(1-\omega)D\right)(D+\omega L)^{-1}$ is greater than or equal to $|\omega - 1|$. 
Can someone help me prove this lower bound result for the spectral radius? I know the spectral radius is the largest eigenvalue but I'm not sure how to start getting the eigenvalues of the matrix I need. 
 A: For the definition of $L, U$ such that $A = D \color{red} - \color{\black} L  \color{red} - \color{\black} U$ the scheme turns out to be
$$x^{k+1} = (D-\omega L)^{-1} \big(\omega U + (1-\omega)D \big) x^{k} + \omega (D-\omega L)^{-1}b$$
This can be reformulated into regular Matrix splitting form from which one obtains the iteration matrix $$G = I - (D/\omega - L)^{-1} A.$$ For the SOR method the matrix $B$ from the Wikipedia article is given by $B=D/\omega - L$ and the iteration / error propagation matrix by $G = I - B^{-1} A.$
Recall some basic properties for invertible matrices $A,B$:

*

*$(AB)^{-1} = B^{-1} A^{-1}$

*$AC = A I C = A B^{-1} B C$

*$A = \big(A^{-1}\big)^{-1}$
Now come back to
\begin{align} 
G &= I - (D/\omega - L)^{-1} A \\
&= I - (D/\omega - L)^{-1} IA \\
&= I - (D/\omega - L)^{-1} ( D/\omega) (D/\omega)^{-1} A \\
&= I - (D/\omega - L)^{-1} \Big(( D/\omega)^{-1}\big)^{-1} (D/\omega)^{-1} A \\
&= I - \big( \omega D^{-1} \big(D/\omega - L) \big)^{-1} \omega D^{-1} A \\
&= I - (I - w D^{-1}L)^{-1} \omega D^{-1} A
\end{align}
Recall $A = D - L - U$ to obtain
\begin{align} 
G &= I - (I - w D^{-1}L)^{-1} \omega D^{-1} (D - L - U) \\
&=I - (I - w D^{-1}L)^{-1} \omega  (I - D^{-1}L - D^{-1}U)
\end{align}
To shorten things, define $\hat L := D^{-1} L, \hat U := D^{-1} U$. Then:
\begin{align} G &= I - (I - w \hat L)^{-1} \omega  (I - \hat L - \hat U) \\
&= I - (I-\omega \hat L)^{-1} \Big[ -\omega \hat L + \omega(I - \hat U) \Big] \\
&= I + (I-\omega \hat L)^{-1} \omega \hat L - (I-\omega \hat L)^{-1} \omega(I - \hat U) \\
&= (I-\omega \hat L)^{-1} (I-\omega \hat L) + (I-\omega \hat L)^{-1} \omega \hat L + (I-\omega \hat L)^{-1} \omega(I - \hat U) \\
&=(I-\omega \hat L)^{-1} \big[ (I-\omega \hat L) + \omega \hat L \big] - (I-\omega \hat L)^{-1} \omega(I - \hat U) \\
&=(I-\omega \hat L)^{-1} I - (I-\omega \hat L)^{-1} \omega(I - \hat U) \\
&= (I-\omega \hat L)^{-1} \big((1-\omega)I + \hat U \big)
\end{align}
Now recall that $\det(AB) = \det(A) \det(B)$. Since $L, U$ are strictly lower/upper triagonal matrices, same holds for $\hat L, \hat U$. As a consequence, $\det \Big((I-\omega \hat L)^{-1} \Big) = 1 $ since triangular matrices preserve their structure under inversion (still triangular) and for triangular matrices, the determinant is equal to the product of the diagonal elements. Consequently, $\det \Big(\big((1-\omega)I + \hat U \big) \Big) = (1-\omega)^n$.
Finally, you know that the determinant equals the product of the eigenvalues: $$ \prod_i \lambda_i = (1-\omega)^n \Rightarrow \bigg \vert \prod_i \lambda_i \bigg \vert = \bigg \vert(1-\omega)^n \bigg \vert \Rightarrow \prod_i \vert \lambda_i \vert = \vert1-\omega  \vert^n $$
Thus, there has to be at least one eigenvalue with modulus $ \vert \lambda_i \vert \geq \vert 1 - \omega \vert$ (assume the opposite: If every eigenvalue would be smaller in absolute value, how would you reach the $\vert 1-\omega  \vert^n$?) Thus, you see that for $\omega \notin (0,2)$ the spectral radius of the error propagation matrix is larger than $1$.
