Spectral radius explained

In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues.^[1] More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectrum. The spectral radius is often denoted by .

Definition

Matrices

Let be the eigenvalues of a matrix . The spectral radius of is defined as

\rho(A) = max \left \{ | λ _{1|,} ... c, | λ _{n|} \right \}.

The spectral radius can be thought of as an infimum of all norms of a matrix. Indeed, on the one hand,

\rho(A) \leqslant \|A\| for every natural matrix norm \| ⋅ \| ; and on the other hand, Gelfand's formula states that \rho(A) = \lim _{k\toinfty} \|A ^{k\|} ^{1/k} . Both of these results are shown below.

However, the spectral radius does not necessarily satisfy

\|A v \| \leqslant \rho(A) \| v \| for arbitrary vectors v \in C ^{n} . To see why, let r > 1 be arbitrary and consider the matrixC _{r} = \begin{pmatrix} 0 & r ^{-1} \ r & 0 \end{pmatrix} . The characteristic polynomial of C _{r} is λ ^{2} - 1 , so its eigenvalues are \{ -1 , 1 \} and thus \rho(C _{r)} = 1 . However, C _{r} e _{1} = r e _{2} . As a result,\| C _{r} e _{1} \| = r > 1 = \rho(C _{r)} \| e _{1\|.} As an illustration of Gelfand's formula, note that \|C ^{k\|} _{r} ^{1/k} \to 1 as k \to inf ty , since C ^{k} _{r} = I if k is even and C ^{k} _{r} = C _{r} if k is odd.

A special case in which

\|A v \| \leqslant \rho(A) \| v \| for all v \in C ^{n} is when A is a Hermitian matrix and \| ⋅ \| is the Euclidean norm. This is because any Hermitian Matrix is diagonalizable by a unitary matrix, and unitary matrices preserve vector length. As a result,\|A v \| = \|U ^{*DUv\|} = \|DU v \| \leqslant \rho(A) \|U v \| = \rho(A) \| v \| .

Bounded linear operators

In the context of a bounded linear operator on a Banach space, the eigenvalues need to be replaced with the elements of the spectrum of the operator, i.e. the values

λ for which A - λ I is not bijective. We denote the spectrum by\sigma(A) = \left\{ λ \in \Complex: A - λ I isnotbijective \right\} The spectral radius is then defined as the supremum of the magnitudes of the elements of the spectrum:\rho(A) = \sup _{λ} | λ | Gelfand's formula, also known as the spectral radius formula, also holds for bounded linear operators: letting \| ⋅ \| denote the operator norm, we have\rho(A) = \lim _{k} \|A ^{k\|} ^{(1)/(k)} =inf _{k\in N ^{*}} \|A ^{k\|} ^{(1)/(k)} .

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

Graphs

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 such that the degree of every vertex of the graph is smaller than). In this case, for the graph define:

\ell ^{2(G)} = \left \{ f : V(G) \to R : \sum\nolimits _{v} \left \|f(v) ^{2} \right \| < inf ty \right \}.

Let be the adjacency operator of :

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

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

Upper bounds

Upper bounds on the spectral radius of a matrix

The following proposition gives simple yet useful upper bounds on the spectral radius of a matrix.

Proposition. Let with spectral radius and a consistent matrix norm . Then for each integer

k \geqslant 1 :\rho(A)\leq \|A ^{k\|} ^{(1)/(k)} .

Proof

Let be an eigenvector-eigenvalue pair for a matrix A. By the sub-multiplicativity of the matrix norm, we get:

| λ | ^{k\|v\|} = \| λ ^{k} v \| = \|A ^{k} v \| \leq \|A ^{k\| ⋅ \|v\|.}

Since, we have

| λ | ^{k} \leq \|A ^{k\|}

and therefore

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

concluding the proof.

Upper bounds for spectral radius of a graph

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

((k -2 )(k -3 ))/(2) \leq m - n \leq (k(k -3 ))/(2)

where

3 \le k \le n is an integer, then^[2] \rho(G) \leq \sqrt{ 2 m - n - k + (5)/(2) + \sqrt{ 2 m -2 n + (9)/(4) }}

Power sequence

The spectral radius is closely related to the behavior of the convergence of the power sequence of a matrix; namely as shown by the following theorem.

Theorem. Let with spectral radius . Then if and only if

\lim _{k} A ^{k} = 0 . On the other hand, if, \lim _{k} \|A ^{k\|} = inf ty . The statement holds for any choice of matrix norm on .

Proof

Assume that

A ^{k} goes to zero as k goes to infinity. We will show that . Let be an eigenvector-eigenvalue pair for A. Since, we have\begin{align} 0 & = \left(\lim _{k} A ^{k} \right) v \\ & = \lim _{k} \left(A ^{kv} \right ) \\ & = \lim _{k} λ ^{kv} \\ & = v \lim _{k} λ ^{k \end{align}}

Since by hypothesis, we must have

\lim _{k} λ ^{k} = 0 ,

which implies

| λ | < 1 . Since this must be true for any eigenvalue λ , we can conclude that .

Now, assume the radius of is less than . From the Jordan normal form theorem, we know that for all, there exist with non-singular and block diagonal such that:

A = VJV ^{-1}

with

J = \begin{bmatrix} J _{m _{1}} ( λ _{1)} & 0 & 0 & … & 0 \\ 0 & J _{m _{2}} ( λ _{2)} & 0 & … & 0 \\ \vdots & … & \ddots & … & \vdots \\ 0 & … & 0 & J _{m _{s-1}} ( λ _{s-1} ) & 0 \\ 0 & … & … & 0 & J _{m _{s}} ( λ _{s) \end{bmatrix}}

where

J _{m _{i}} ( λ _{i)=\begin{bmatrix} λ} _{i} & 1 & 0 & … & 0 \\ 0 & λ _{i} & 1 & … & 0 \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & … & λ _{i} & 1 \\ 0 & 0 & … & 0 & λ _{i \end{bmatrix}\in} C ^{m _{i} x m _{i}} , 1 \leq i\leq s.

It is easy to see that

A ^{k=VJ} ^{kV} ^{-1}

and, since is block-diagonal,

J ^{k( λ} _{1 )} & 0 & 0 & … & 0 \\ 0 & J ^{k( λ} _{2 )} & 0 & … & 0 \\ \vdots & … & \ddots & … & \vdots \\ 0 & … & 0 & J ^{k( λ} _{s -1} ) & 0 \\ 0 & … & … & 0 & J ^{k( λ} _{s) \end{bmatrix}}

Now, a standard result on the -power of an

m _{i} x m _{i} Jordan block states that, for k \geq m _{i-1} :J ^{k( λ} _{i) = \begin{bmatrix} λ} ^{k} ^{i} & {k \choose 1 } λ ^{k -1} _{i} & {k \choose 2 } λ ^{k -2} _{i} & … & {k \choose m _{i-1}λ} ^{k - m _{i+1}} ^{i} \\ 0 & λ ^{k} _{i} & {k \choose 1 } λ ^{k -1} _{i} & … & {k \choose m _{i-2}λ} ^{k - m _{i+2}} ^{i} \\ \vdots & \vdots & \ddots & \ddots & \vdots \\ 0 & 0 & … & λ ^{k} _{i} & {k \choose 1 } λ ^{k -1} _{i} \\ 0 & 0 & … & 0 & λ ^{k \end{bmatrix}} _{i}

Thus, if

\rho(A) < 1 then for all | λ _{i|} < 1 . Hence for all we have:\lim _{k} J ^{k =0} _{m _{i}}

which implies

\lim _{k} J ^{k} = 0 .

Therefore,

\lim _{k} A ^{k = \lim} _{k \to inf ty} VJ ^{kV} ^{-1} = V \left (\lim _{k} J ^{k} \right )V ^{-1} =0

On the other side, if

\rho(A)> 1 , there is at least one element in that does not remain bounded as increases, thereby proving the second part of the statement.

Gelfand's formula

Gelfand's formula, named after Israel Gelfand, gives the spectral radius as a limit of matrix norms.

Theorem

For any matrix norm we have^[3]

\rho(A) = \lim _{k} \left \|A ^{k} \right \| ^{(1)/(k)} .

Moreover, in the case of a consistent matrix norm

\lim _{k} \left \|A ^{k} \right \| ^{(1)/(k)} approaches \rho(A) from above (indeed, in that case \rho(A) \leq \left \|A ^{k} \right \| ^{(1)/(k)} for all k ).

Proof

For any, let us define the two following matrices:

A _{\pm} = (1)/(\rho(A) \pm\varepsilon) A.

Thus,

\rho \left (A _{\pm} \right ) = (\rho(A))/(\rho(A) \pm \varepsilon) , \rho (A _{+)} < 1 < \rho (A _{-).}

We start by applying the previous theorem on limits of power sequences to :

\lim _{k} A ^{k =0 .} _{+}

This shows the existence of such that, for all,

\left\|A ^{k} _{+} \right \| < 1 . Therefore,\left \|A ^{k} \right \| ^{(1)/(k)} < \rho(A) + \varepsilon.

Similarly, the theorem on power sequences implies that

\|A ^{k\|} _{-} is not bounded and that there exists such that, for all k ≥ N₋,\left\|A ^{k} _{-} \right \| > 1 . Therefore,\left\|A ^{k} \right\| ^{(1)/(k)} > \rho(A) - \varepsilon.

Let . Then,

\forall \varepsilon> 0 \exists N\in N \forall k\geq N \rho(A) - \varepsilon < \left \|A ^{k} \right \| ^{(1)/(k)} < \rho(A) + \varepsilon, that is,\lim _{k} \left \|A ^{k} \right \| ^{(1)/(k)} = \rho(A). This concludes the proof.

Corollary

Gelfand's formula yields a bound on the spectral radius of a product of commuting matrices: if

A _{1,} \ldots, A _{n} are matrices that all commute, then\rho(A _{1} … A _{n)} \leq \rho(A _{1)} … \rho(A _{n).}

Numerical example

Consider the matrix

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

whose eigenvalues are ; by definition, . 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	\	\cdot\	_1=\	\cdot\	_\infty	\	\cdot\	_F	\	\cdot\	_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

See also

• Spectral gap
• The Joint spectral radius is a generalization of the spectral radius to sets of matrices.
• Spectrum of a matrix
• Spectral abscissa

Notes and References

1. Book: Gradshteĭn, I. S. . Table of integrals, series, and products . 1980 . Academic Press . I. M. Ryzhik, Alan Jeffrey . 0-12-294760-6 . Corr. and enl. . New York . 5892996.
2. Guo. Ji-Ming. Wang. Zhi-Wen. Li. Xin. 2019. Sharp upper bounds of the spectral radius of a graph. Discrete Mathematics. en. 342. 9. 2559–2563. 10.1016/j.disc.2019.05.017. 198169497. free.
3. The formula holds for any Banach algebra; see Lemma IX.1.8 in and