Spectral radius

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

Matrices[edit]

Let λ1, ..., λn be the (real or complex) eigenvalues of a matrix ACn×n. Then its spectral radius ρ(A) is defined as:

\rho(A) = \max \left \{ |\lambda_1|, \cdots, |\lambda_n| \right \}.

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

Lemma. Let ACn×n with spectral radius ρ(A) and a consistent matrix norm ||⋅||; then, for each kN:
\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:

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

and since v ≠ 0 we have

|\lambda|^k \leq \|A^k\|

and therefore

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

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 ACn×n with spectral radius ρ(A); then ρ(A) < 1 if and only if
\lim_{k \to \infty} A^k = 0.
Moreover, if ρ(A) > 1, ||Ak|| is not bounded for increasing values of k.

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

\begin{align}
  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{align}

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.

Now assume the radius of A is less than 1. From the Jordan normal form theorem, we know that for all ACn×n, there exist V, JCn×n with V non-singular and J block diagonal 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 \mathbf{C}^{m_i \times m_i}, 1\leq i\leq s.

It is easy to see that

A^k=VJ^kV^{-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 \times m_i Jordan block states that, for k \geq 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 \rho(A) < 1 then for all i |\lambda_i| < 1. Hence for all i we have:

\lim_{k \to \infty}J_{m_i}^k=0

which implies

\lim_{k \to \infty} J^k = 0.

Therefore,

\lim_{k \to \infty}A^k=\lim_{k \to \infty}VJ^kV^{-1}=V \left (\lim_{k \to \infty}J^k \right )V^{-1}=0

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

Gelfand's Formula[edit]

Theorem (Gelfand's Formula; 1941). For any matrix norm ||⋅||, we have
\rho(A)=\lim_{k \to \infty} \left \|A^k \right \|^{\frac{1}{k}}.

In other words the spectral radius of A gives the asymptotic growth rate of the norm of Ak, as k → ∞: ||Ak|| ~ ρ(A)k .

Proof[edit]

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

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

Then:

\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+:

\lim_{k \to \infty} A_+^k=0.

That means, by the sequence limit definition, there exists N+N such that

\begin{align}
\forall k\geq N_+ \quad \left \|A_+^k \right \| < 1 \qquad &\Rightarrow \qquad \forall k\geq N_+ \quad \left \|A^k \right \| < (\rho(A)+\varepsilon)^k \\  &\Rightarrow \qquad \forall k\geq N_+ \quad  \left \|A^k \right \|^{\frac{1}{k}} < \rho(A)+\varepsilon.
\end{align}

Applying the previous theorem to A implies \|A_-^k\| is not bounded and there exists NN such that

\begin{align}
\forall k\geq N_- \quad \left\|A_-^k \right \| > 1 \qquad &\Rightarrow \qquad \forall k\geq N_- \quad \left \|A^k \right \| > (\rho(A)-\varepsilon)^k \\
&\Rightarrow \qquad \forall k\geq N_2 \quad \left \|A^k \right\|^{\frac{1}{k}} > \rho(A)-\varepsilon. 
\end{align}

Let N = max{N+, N}, then we have:

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

which, by definition, is

\lim_{k \to \infty} \left \|A^k \right \|^{\frac{1}{k}} = \rho(A).

Corollaries[edit]

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 \cdots A_n) \leq \rho(A_1) \cdots \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 \varepsilon>0, \exists N\in\mathbf{N}, \forall k\geq N \quad \rho(A) \leq \|A^k\|^{\frac{1}{k}} < \rho(A)+\varepsilon

which, by definition, is

\lim_{k \to \infty} \left \|A^k \right \|^{\frac{1}{k}} = \rho(A)^+.

Example[edit]

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, ρ(A) = 10. In the following table, the values of \|A^k\|^{\frac{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

Bounded Linear Operators[edit]

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

\rho(A) = \lim_{k \to \infty}\|A^k\|^{\frac{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.

Graphs[edit]

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

 \ell^2(G) = \left \{ f : V(G) \to \mathbf{R} \ : \ \sum\nolimits_{v \in V(G)} \left \|f(v)^2 \right \| < \infty \right \}.

Let γ be the adjacency operator of G:

 \begin{cases} \gamma : \ell^2(G) \to \ell^2(G) \\ (\gamma f)(v) = \sum_{(u,v) \in E(G)} f(u) \end{cases}

The spectral radius of G is defined to be the spectral radius of the bounded linear operator γ.

See also[edit]