Spectral radius

The following proposition shows a simple yet useful upper bound for the spectral radius of a matrix:

Proposition. Let A ∈ C^n×n with spectral radius ρ(A) and a consistent matrix norm ||⋅||. Then for each integer ${\displaystyle k\geqslant 1}$:

${\displaystyle \rho (A)\leq \|A^{k}\|^{\frac {1}{k}}.}$

Proof

Let (v, λ) be an eigenvector-eigenvalue pair for a matrix A. By the sub-multiplicative property of the matrix norm, we get:

${\displaystyle |\lambda |^{k}\|\mathbf {v} \|=\|\lambda ^{k}\mathbf {v} \|=\|A^{k}\mathbf {v} \|\leq \|A^{k}\|\cdot \|\mathbf {v} \|}$

and since v ≠ 0 we have

${\displaystyle |\lambda |^{k}\leq \|A^{k}\|}$

and therefore

${\displaystyle \rho (A)\leq \|A^{k}\|^{\frac {1}{k}}.}$

There are many upper bounds for the spectral radius of a graph in terms of its number n of vertices and its number m of edges. For instance, if

${\displaystyle {\frac {(k-2)(k-3)}{2}}\leq m-n\leq {\frac {k(k-3)}{2}}}$

where ${\displaystyle 3\leq k\leq n}$ is an integer, then[1]

${\displaystyle \rho (G)\leq {\sqrt {2m-n-k+{\frac {5}{2}}+{\sqrt {2m-2n+{\frac {9}{4}}}}}}}$

The spectral radius is closely related to the behaviour of the convergence of the power sequence of a matrix; namely, the following theorem holds:

Theorem. Let A ∈ C^n×n with spectral radius ρ(A). Then ρ(A) < 1 if and only if

${\displaystyle \lim _{k\to \infty }A^{k}=0.}$

On the other hand, if ρ(A) > 1, ${\displaystyle \lim _{k\to \infty }\|A^{k}\|=\infty }$. The statement holds for any choice of matrix norm on C^n×n.

Assume the limit in question is zero, we will show that ρ(A) < 1. Let (v, λ) be an eigenvector-eigenvalue pair for A. Since A^kv = λ^kv we have:

${\displaystyle {\begin{aligned}0&=\left(\lim _{k\to \infty }A^{k}\right)\mathbf {v} \\&=\lim _{k\to \infty }\left(A^{k}\mathbf {v} \right)\\&=\lim _{k\to \infty }\lambda ^{k}\mathbf {v} \\&=\mathbf {v} \lim _{k\to \infty }\lambda ^{k}\end{aligned}}}$

and, since by hypothesis v ≠ 0, we must have

${\displaystyle \lim _{k\to \infty }\lambda ^{k}=0}$

which implies |λ| < 1. Since this must be true for any eigenvalue λ, we can conclude ρ(A) < 1.

Now assume the radius of A is less than 1. From the Jordan normal form theorem, we know that for all A ∈ C^n×n, there exist V, J ∈ C^n×n with V non-singular and J block diagonal such that:

${\displaystyle A=VJV^{-1}}$

with

${\displaystyle J={\begin{bmatrix}J_{m_{1}}(\lambda _{1})&0&0&\cdots &0\\0&J_{m_{2}}(\lambda _{2})&0&\cdots &0\\\vdots &\cdots &\ddots &\cdots &\vdots \\0&\cdots &0&J_{m_{s-1}}(\lambda _{s-1})&0\\0&\cdots &\cdots &0&J_{m_{s}}(\lambda _{s})\end{bmatrix}}}$

where

${\displaystyle J_{m_{i}}(\lambda _{i})={\begin{bmatrix}\lambda _{i}&1&0&\cdots &0\\0&\lambda _{i}&1&\cdots &0\\\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&\cdots &\lambda _{i}&1\\0&0&\cdots &0&\lambda _{i}\end{bmatrix}}\in \mathbf {C} ^{m_{i}\times m_{i}},1\leq i\leq s.}$

It is easy to see that

${\displaystyle A^{k}=VJ^{k}V^{-1}}$

and, since J is block-diagonal,

${\displaystyle J^{k}={\begin{bmatrix}J_{m_{1}}^{k}(\lambda _{1})&0&0&\cdots &0\\0&J_{m_{2}}^{k}(\lambda _{2})&0&\cdots &0\\\vdots &\cdots &\ddots &\cdots &\vdots \\0&\cdots &0&J_{m_{s-1}}^{k}(\lambda _{s-1})&0\\0&\cdots &\cdots &0&J_{m_{s}}^{k}(\lambda _{s})\end{bmatrix}}}$

Now, a standard result on the k-power of an ${\displaystyle m_{i}\times m_{i}}$ Jordan block states that, for ${\displaystyle k\geq m_{i}-1}$:

${\displaystyle J_{m_{i}}^{k}(\lambda _{i})={\begin{bmatrix}\lambda _{i}^{k}&{k \choose 1}\lambda _{i}^{k-1}&{k \choose 2}\lambda _{i}^{k-2}&\cdots &{k \choose m_{i}-1}\lambda _{i}^{k-m_{i}+1}\\0&\lambda _{i}^{k}&{k \choose 1}\lambda _{i}^{k-1}&\cdots &{k \choose m_{i}-2}\lambda _{i}^{k-m_{i}+2}\\\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&\cdots &\lambda _{i}^{k}&{k \choose 1}\lambda _{i}^{k-1}\\0&0&\cdots &0&\lambda _{i}^{k}\end{bmatrix}}}$

Thus, if ${\displaystyle \rho (A)<1}$ then for all i ${\displaystyle |\lambda _{i}|<1}$. Hence for all i we have:

${\displaystyle \lim _{k\to \infty }J_{m_{i}}^{k}=0}$

which implies

${\displaystyle \lim _{k\to \infty }J^{k}=0.}$

Therefore,

${\displaystyle \lim _{k\to \infty }A^{k}=\lim _{k\to \infty }VJ^{k}V^{-1}=V\left(\lim _{k\to \infty }J^{k}\right)V^{-1}=0}$

On the other side, if ${\displaystyle \rho (A)>1}$, there is at least one element in J which doesn't remain bounded as k increases, so proving the second part of the statement.

The next theorem gives the spectral radius as a limit of matrix norms.

Theorem (Gelfand's Formula; 1941). For any matrix norm ||⋅||, we have

${\displaystyle \rho (A)=\lim _{k\to \infty }\left\|A^{k}\right\|^{\frac {1}{k}}.}$.[2]

For any ε > 0, first we construct the following two matrices:

${\displaystyle A_{\pm }={\frac {1}{\rho (A)\pm \varepsilon }}A.}$

Then:

${\displaystyle \rho \left(A_{\pm }\right)={\frac {\rho (A)}{\rho (A)\pm \varepsilon }},\qquad \rho (A_{+})<1<\rho (A_{-}).}$

First we apply the previous theorem to A₊:

${\displaystyle \lim _{k\to \infty }A_{+}^{k}=0.}$

That means, by the sequence limit definition, there exists N₊ ∈ N such that for all k ≥ N₊,

${\displaystyle {\begin{aligned}\left\|A_{+}^{k}\right\|<1\end{aligned}}}$

so

${\displaystyle {\begin{aligned}\left\|A^{k}\right\|^{\frac {1}{k}}<\rho (A)+\varepsilon .\end{aligned}}}$

Applying the previous theorem to A₋ implies ${\displaystyle \|A_{-}^{k}\|}$ is not bounded and there exists N₋ ∈ N such that for all k ≥ N₋,

${\displaystyle {\begin{aligned}\left\|A_{-}^{k}\right\|>1\end{aligned}}}$

so

${\displaystyle {\begin{aligned}\left\|A^{k}\right\|^{\frac {1}{k}}>\rho (A)-\varepsilon .\end{aligned}}}$

Let N = max{N₊, N₋}, then we have:

${\displaystyle \forall \varepsilon >0\quad \exists N\in \mathbf {N} \quad \forall k\geq N\quad \rho (A)-\varepsilon <\left\|A^{k}\right\|^{\frac {1}{k}}<\rho (A)+\varepsilon }$

which, by definition, is

${\displaystyle \lim _{k\to \infty }\left\|A^{k}\right\|^{\frac {1}{k}}=\rho (A).}$