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 absolute values of the elements in its spectrum, which is sometimes denoted by ρ(·).

[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:

ρ(A): = max i ( | λ 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$

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 : = 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 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

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

A bounded operator (on a complex Hilbert space) called a spectraloid operator if its spectral radius coincides with its numerical radius. An example of such an operator is a normal operator.

[edit] Spectral radius of a graph

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

This definition extends to the case of infinite graphs with bounded degrees of vertices (i.e. there exists some real number C such that the degree of every vertex of the graph is smaller than C). In this case, for the graph $G$ let $l 2 (G)$ denote the space of functions $f \colon V(G) \to {\mathbb R}$ with $\sum_{v \in V(G)} \|f(v)^2\| < \infty$ . Let $\gamma \colon l^2(G) \to l^2(G)$ be the adjacency operator of $G$ , i.e., $(\gamma f)(v) = \sum_{(u,v) \in E(G)} f(u)$ . The spectral radius of G is defined to be the spectral radius of the bounded linear operator $γ$ .