Spectral radius

From Wikipedia, the free encyclopedia

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

1 Spectral radius of a matrix
2 Theorem (Gelfand's formula, 1941)
3 Spectral radius of a bounded linear operator
4 Spectral radius of a graph
5 External links

[edit] 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_{1\leq i\leq s}(|\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

ρ(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 = V J V - 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 = V J 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^kV^{-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$

[edit] 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$

$\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$

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

Taking

N : = m a x (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 $\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