Battles of El Bruch

In mathematics, the spectral radius of a matrix or a bounded linear operator is the supremum among the absolute values of the elements in its spectrum, which is sometimes denoted by ρ(·).

Spectral radius of a matrix

Let λ₁, …, λ_s be the (real or complex) eigenvalues of a matrix A ∈ C^{n × n}. Then its spectral radius ρ(A) is defined as:

$\rho (A):=\max _{i}(|\lambda _{i}|)$

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

Lemma: Let A ∈ C^{n × n} be a complex-valued matrix, ρ(A) its spectral radius and ||·|| a consistent matrix norm; then, for each k ∈ N:

$\rho (A)\leq \|A^{k}\|^{1/k},\ \forall k\in \mathbb {N} .$

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

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

and since v ≠ 0 for each λ we have

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

and therefore

$\rho (A)\leq \|A^{k}\|^{1/k}\,\,\square$

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} be a complex-valued matrix and ρ(A) its spectral radius; then

$\lim _{k\to \infty }A^{k}=0$ if and only if $\rho (A)<1.$

Moreover, if ρ(A)>1, $\|A^{k}\|$ is not bounded for increasing k values.

Proof:

($\lim _{k\to \infty }A^{k}=0\Rightarrow \rho (A)<1$)

Let (v, λ) be an eigenvector-eigenvalue pair for matrix A. Since

$A^{k}\mathbf {v} =\lambda ^{k}\mathbf {v} ,$

we have:

$0\,$	$=(\lim _{k\to \infty }A^{k})\mathbf {v}$
	$=\lim _{k\to \infty }A^{k}\mathbf {v}$
	$=\lim _{k\to \infty }\lambda ^{k}\mathbf {v}$
	$=\mathbf {v} \lim _{k\to \infty }\lambda ^{k}$

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

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

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

($\rho (A)<1\Rightarrow \lim _{k\to \infty }A^{k}=0$)

From the Jordan Normal Form Theorem, we know that for any complex valued matrix A ∈ C^{n × n}, a non-singular matrix V ∈ C^{n × n} and a block-diagonal matrix J ∈ C^{n × n} exist such that:

$A=VJV^{-1}$

with

$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

$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 \mathbb {C} ^{m_{i},m_{i}},1\leq i\leq s.$

It is easy to see that

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

and, since J is block-diagonal,

$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 m_i × m_i Jordan block states that, for k ≥ m_{i − 1}:

$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 ρ(A) < 1 then |λ_i| < 1 ∀ i, so that

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

which implies

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

Therefore,

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

On the other side, if ρ(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.

$\square$

Theorem (Gelfand's formula, 1941)

For any matrix norm ||·||, we have

$\rho (A)=\lim _{k\to \infty }||A^{k}||^{1/k}.$

In other words, the Gelfand's formula shows how the spectral radius of A gives the asymptotic growth rate of the norm of A^k:

$\|A^{k}\|\sim \rho (A)^{k}$ for $k\rightarrow \infty .\,$

Proof: For any ε > 0, consider the matrix

${\tilde {A}}=(\rho (A)+\epsilon )^{-1}A.$

Then, obviously,

$\rho ({\tilde {A}})={\frac {\rho (A)}{\rho (A)+\epsilon }}<1$

and, by the previous theorem,

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

That means, by the sequence limit definition, a natural number N₁ ∈ N exists such that

$\forall k\geq N_{1}\Rightarrow \|{\tilde {A}}^{k}\|<1$

which in turn means:

$\forall k\geq N_{1}\Rightarrow \|A^{k}\|<(\rho (A)+\epsilon )^{k}$

or

$\forall k\geq N_{1}\Rightarrow \|A^{k}\|^{1/k}<(\rho (A)+\epsilon ).$

Let's now consider the matrix

${\check {A}}=(\rho (A)-\epsilon )^{-1}A.$

Then, obviously,

$\rho ({\check {A}})={\frac {\rho (A)}{\rho (A)-\epsilon }}>1$

and so, by the previous theorem,$\|{\check {A}}^{k}\|$ is not bounded.

This means a natural number N₂ ∈ N exists such that

$\forall k\geq N_{2}\Rightarrow \|{\check {A}}^{k}\|>1$

which in turn means:

$\forall k\geq N_{2}\Rightarrow \|A^{k}\|>(\rho (A)-\epsilon )^{k}$

or

$\forall k\geq N_{2}\Rightarrow \|A^{k}\|^{1/k}>(\rho (A)-\epsilon ).$

Taking

$N:=max(N_{1},N_{2})$

and putting it all together, we obtain:

$\forall \epsilon >0,\exists N\in \mathbb {N} :\forall k\geq N\Rightarrow \rho (A)-\epsilon <\|A^{k}\|^{1/k}<\rho (A)+\epsilon$

which, by definition, is

$\lim _{k\to \infty }\|A^{k}\|^{1/k}=\rho (A).\,\,\square$

Gelfand's formula leads directly to a bound on the spectral radius of a product of finitely many matrices, namely assuming that they all commute we obtain $\rho (A_{1}A_{2}\ldots A_{n})\leq \rho (A_{1})\rho (A_{2})\ldots \rho (A_{n}).$

Actually, in case the norm is consistent, the proof shows more than the thesis; in fact, using the previous lemma, we can replace in the limit definition the left lower bound with the spectral radius itself and write more precisely:

$\forall \epsilon >0,\exists N\in \mathbb {N} :\forall k\geq N\Rightarrow \rho (A)\leq \|A^{k}\|^{1/k}<\rho (A)+\epsilon$

which, by definition, is

$\lim _{k\to \infty }\|A^{k}\|^{1/k}=\rho (A)^{+}.$

Example: Let's consider the matrix

$A={\begin{bmatrix}9&-1&2\\-2&8&4\\1&1&8\end{bmatrix}}$

whose eigenvalues are 5, 10, 10; by definition, its spectral radius is ρ(A)=10. In the following table, the values of $\|A^{k}\|^{1/k}$ for the four most used norms are listed versus several increasing values of k (note that, due to the particular form of this matrix,$\|.\|_{1}=\|.\|_{\infty }$):

k	$\|.\|_{1}=\|.\|_{\infty }$	$\|.\|_{F}$	$\|.\|_{2}$
1	14	15.362291496	10.681145748
2	12.649110641	12.328294348	10.595665162
3	11.934831919	11.532450664	10.500980846
4	11.501633169	11.151002986	10.418165779
5	11.216043151	10.921242235	10.351918183
$\vdots$	$\vdots$	$\vdots$	$\vdots$
10	10.604944422	10.455910430	10.183690042
11	10.548677680	10.413702213	10.166990229
12	10.501921835	10.378620930	10.153031596
$\vdots$	$\vdots$	$\vdots$	$\vdots$
20	10.298254399	10.225504447	10.091577411
30	10.197860892	10.149776921	10.060958900
40	10.148031640	10.112123681	10.045684426
50	10.118251035	10.089598820	10.036530875
$\vdots$	$\vdots$	$\vdots$	$\vdots$
100	10.058951752	10.044699508	10.018248786
200	10.029432562	10.022324834	10.009120234
300	10.019612095	10.014877690	10.006079232
400	10.014705469	10.011156194	10.004559078
$\vdots$	$\vdots$	$\vdots$	$\vdots$
1000	10.005879594	10.004460985	10.001823382
2000	10.002939365	10.002230244	10.000911649
3000	10.001959481	10.001486774	10.000607757
$\vdots$	$\vdots$	$\vdots$	$\vdots$
10000	10.000587804	10.000446009	10.000182323
20000	10.000293898	10.000223002	10.000091161
30000	10.000195931	10.000148667	10.000060774
$\vdots$	$\vdots$	$\vdots$	$\vdots$
100000	10.000058779	10.000044600	10.000018232

Spectral radius of a bounded linear operator

For a bounded linear operator A and the operator norm ||·||, again we have

$\rho (A)=\lim _{k\to \infty }\|A^{k}\|^{1/k}.$

Spectral radius of a graph

The spectral radius of a graph is defined to be the spectral radius of its adjacency matrix.

See also

• Spectral gap

External links

• Spectral Radius of Planar Graphs