Spectral radius#Matrices

Let {{math|λ₁, ..., λ_n}} be the eigenvalues of a matrix {{math|A ∈ C^n×n}}. The spectral radius of {{math|A}} is defined as

:$\backslash rho(A)\; =\; \backslash max\; \backslash left\; \backslash \{\; |\backslash lambda\_1|,\; \backslash dotsc,\; |\backslash lambda\_n|\; \backslash right\; \backslash \}.$

The spectral radius can be thought of as an infimum of all norms of a matrix. Indeed, on the one hand, $\backslash rho(A)\; \backslash leqslant\; \backslash |A\backslash |$ for every natural matrix norm $\backslash |\backslash cdot\backslash |$; and on the other hand, Gelfand's formula states that $\backslash rho(A)\; =\; \backslash lim\_\{k\backslash to\backslash infty\}\; \backslash |A^k\backslash |^\{1/k\}$. Both of these results are shown below.

However, the spectral radius does not necessarily satisfy $\backslash |A\backslash mathbf\{v\}\backslash |\; \backslash leqslant\; \backslash rho(A)\; \backslash |\backslash mathbf\{v\}\backslash |$ for arbitrary vectors $\backslash mathbf\{v\}\; \backslash in\; \backslash mathbb\{C\}^n$. To see why, let $r\; >\; 1$ be arbitrary and consider the matrix

:.

The characteristic polynomial of $C\_r$ is $\backslash lambda^2\; -\; 1$, so its eigenvalues are $\backslash \{-1,\; 1\backslash \}$ and thus $\backslash rho(C\_r)\; =\; 1$. However, $C\_r\; \backslash mathbf\{e\}\_1\; =\; r\; \backslash mathbf\{e\}\_2$. As a result,

:$\backslash |\; C\_r\; \backslash mathbf\{e\}\_1\; \backslash |\; =\; r\; >\; 1\; =\; \backslash rho(C\_r)\; \backslash |\backslash mathbf\{e\}\_1\backslash |.$

As an illustration of Gelfand's formula, note that $\backslash |C\_r^k\backslash |^\{1/k\}\; \backslash to\; 1$ as $k\; \backslash to\; \backslash infty$, since $C\_r^k\; =\; I$ if $k$ is even and $C\_r^k\; =\; C\_r$ if $k$ is odd.

A special case in which $\backslash |A\backslash mathbf\{v\}\backslash |\; \backslash leqslant\; \backslash rho(A)\; \backslash |\backslash mathbf\{v\}\backslash |$ for all $\backslash mathbf\{v\}\; \backslash in\; \backslash mathbb\{C\}^n$ is when $A$ is a Hermitian matrix and $\backslash |\backslash cdot\backslash |$ 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,

: $\backslash |A\backslash mathbf\{v\}\backslash |\; =\; \backslash |U^*DU\backslash mathbf\{v\}\backslash |\; =\; \backslash |DU\backslash mathbf\{v\}\backslash |\; \backslash leqslant\; \backslash rho(A)\; \backslash |U\backslash mathbf\{v\}\backslash |\; =\; \backslash rho(A)\; \backslash |\backslash mathbf\{v\}\backslash |\; .$

In the context of a bounded linear operator {{mvar|A}} on a Banach space, the eigenvalues need to be replaced with the elements of the spectrum of the operator, i.e. the values $\backslash lambda$ for which $A\; -\; \backslash lambda\; I$ is not bijective. We denote the spectrum by

:$\backslash sigma(A)\; =\; \backslash left\backslash \{\; \backslash lambda\; \backslash in\; \backslash Complex:\; A\; -\; \backslash lambda\; I\; \backslash ;\; \backslash text\{is\; not\; bijective\}\; \backslash right\backslash \}$

The spectral radius is then defined as the supremum of the magnitudes of the elements of the spectrum:

:$\backslash rho(A)\; =\; \backslash sup\_\{\backslash lambda\; \backslash in\; \backslash sigma(A)\}\; |\backslash lambda|$

Gelfand's formula, also known as the spectral radius formula, also holds for bounded linear operators: letting $\backslash |\backslash cdot\backslash |$ denote the operator norm, we have

:$\backslash rho(A)\; =\; \backslash lim\_\{k\; \backslash to\; \backslash infty\}\backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}=\backslash inf\_\{k\backslash in\backslash mathbb\{N\}^*\}\; \backslash |A^k\backslash |^\{\backslash frac\{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.

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

:

Let {{mvar|γ}} be the adjacency operator of {{mvar|G}}:

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

The spectral radius of {{mvar|G}} is defined to be the spectral radius of the bounded linear operator {{mvar|γ}}.

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

Proposition. Let {{math|A ∈ C^n×n}} with spectral radius {{math|ρ(A)}} and a sub-multiplicative matrix norm {{math|{{!!}}⋅{{!!}}}}. Then for each integer $k\; \backslash geqslant\; 1$:

::$\backslash rho(A)\backslash leq\; \backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}.$

Proof

Let {{math|(v, λ)}} be an eigenvector-eigenvalue pair for a matrix A. By the sub-multiplicativity of the matrix norm, we get:

:$|\backslash lambda|^k\backslash |\backslash mathbf\{v\}\backslash |\; =\; \backslash |\backslash lambda^k\; \backslash mathbf\{v\}\backslash |\; =\; \backslash |A^k\; \backslash mathbf\{v\}\backslash |\; \backslash leq\; \backslash |A^k\backslash |\backslash cdot\backslash |\backslash mathbf\{v\}\backslash |.$

Since {{math|v ≠ 0}}, we have

:$|\backslash lambda|^k\; \backslash leq\; \backslash |A^k\backslash |$

and therefore

:$\backslash rho(A)\backslash leq\; \backslash |A^k\backslash |^\{\backslash frac\{1\}\{k\}\}.$

concluding the proof.

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

:$\backslash frac\{(k-2)(k-3)\}\{2\}\; \backslash leq\; m-n\; \backslash leq\; \backslash frac\{k(k-3)\}\{2\}$

where $3\; \backslash le\; k\; \backslash le\; n$ is an integer, then{{Cite journal|last1=Guo|first1=Ji-Ming|last2=Wang|first2=Zhi-Wen|last3=Li|first3=Xin|date=2019|title=Sharp upper bounds of the spectral radius of a graph|journal=Discrete Mathematics|language=en|volume=342|issue=9|pages=2559–2563|doi=10.1016/j.disc.2019.05.017|s2cid=198169497|doi-access=free}}

:$\backslash rho(G)\; \backslash leq\; \backslash sqrt\{2\; m-n-k+\backslash frac\{5\}\{2\}+\backslash sqrt\{2\; m-2\; n+\backslash frac\{9\}\{4\}\}\}$

For real-valued matrices $A$ the inequality $\backslash rho(A)\; \backslash leq\; \{\backslash |A\backslash |\}\_\{2\}$ holds in particular, where $\{\backslash |\backslash cdot\backslash |\}\_\{2\}$ denotes the spectral norm. In the case

where $A$ is symmetric, this inequality is tight:

Theorem. Let $A\; \backslash in\; \backslash mathbb\{R\}^\{n\; \backslash times\; n\}$ be symmetric, i.e., $A\; =\; A^T.$ Then it holds that $\backslash rho(A)\; =\; \{\backslash |A\backslash |\}\_\{2\}.$

Proof

Let $(v\_i,\; \backslash lambda\_i)\_\{i=1\}^\{n\}$ be the eigenpairs of A. Due to the symmetry of A,

all $v\_i$ and $\backslash lambda\_i$ are real-valued and the eigenvectors $v\_i$ are orthonormal.

By the definition of the spectral norm, there exists an $x\; \backslash in\; \backslash mathbb\{R\}^\{n\}$ with

$\{\backslash |x\backslash |\}\_\{2\}\; =\; 1$ such that $\{\backslash |A\backslash |\}\_\{2\}\; =\; \{\backslash |\; A\; x\; \backslash |\}\_\{2\}.$ Since the eigenvectors $v\_i$ form a basis

of $\backslash mathbb\{R\}^\{n\},$ there exists

factors $\backslash delta\_\{1\},\; \backslash ldots,\; \backslash delta\_\{n\}\; \backslash in\; \backslash mathbb\{R\}^\{n\}$ such that $\backslash textstyle\; x\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; v\_\{i\}$ which implies that

:$A\; x\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}\backslash delta\_\{i\}\; A\; v\_\{i\}\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; \backslash lambda\_\{i\}\; v\_\{i\}.$

From the orthonormality of the eigenvectors $v\_i$ it follows that

:$\{\backslash |\; A\; x\backslash |\}\_\{2\}\; =\; \backslash |\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; \backslash lambda\_\{i\}\; v\_\{i\}\backslash |\_\{2\}\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}$

and

:$\{\backslash |x\backslash |\}\_\{2\}\; =\; \backslash |\; \backslash sum\_\{i\; =\; 1\}^\{n\}\; \backslash delta\_\{i\}\; v\_\{i\}\; \backslash |\_\{2\}\; =\; \backslash sum\_\{i\; =\; 1\}^\{n\}$

Since $x$ is chosen such that it maximizes $\{\backslash |Ax\backslash |\}\_\{2\}$ while satisfying $\{\backslash |x\backslash |\}\_\{2\}\; =\; 1,$ the values of $\backslash delta\_\{i\}$ must be such that they maximize $\backslash textstyle\; \backslash sum\_\{i\; =\; 1\}^\{n\}$

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 {{math|A ∈ C^n×n}} with spectral radius {{math|ρ(A)}}. Then {{math|ρ(A) < 1}} if and only if

:$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; A^k\; =\; 0.$

On the other hand, if {{math|ρ(A) > 1}}, $\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash |A^k\backslash |\; =\; \backslash infty$. The statement holds for any choice of matrix norm on {{math|C^n×n}}.

Proof

Assume that $A^k$ goes to zero as $k$ goes to infinity. We will show that {{math|ρ(A) < 1}}. Let {{math|(v, λ)}} be an eigenvector-eigenvalue pair for A. Since {{math|A^kv {{=}} λ^kv}}, we have

:$\backslash 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}

Since {{math|v ≠ 0}} by hypothesis, we must have

:$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\backslash lambda^k\; =\; 0,$

which implies . Since this must be true for any eigenvalue $\backslash lambda$, we can conclude that {{math|ρ(A) < 1}}.

Now, assume the radius of {{mvar|A}} is less than {{math|1}}. From the Jordan normal form theorem, we know that for all {{math|A ∈ C^n×n}}, there exist {{math|V, J ∈ C^n×n}} with {{mvar|V}} non-singular and {{mvar|J}} block diagonal such that:

:$A\; =\; VJV^\{-1\}$

with

:$J=\backslash 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\}(\backslash lambda\_i)=\backslash 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 {{mvar|J}} is block-diagonal,

:$J^k=\backslash 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 {{mvar|k}}-power of an $m\_i\; \backslash times\; m\_i$ Jordan block states that, for $k\; \backslash geq\; m\_i-1$:

:$J\_\{m\_i\}^k(\backslash lambda\_i)=\backslash 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 then for all {{mvar|i}} . Hence for all {{mvar|i}} we have:

:$\backslash lim\_\{k\; \backslash to\; \backslash infty\}J\_\{m\_i\}^k=0$

which implies

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

Therefore,

:$\backslash lim\_\{k\; \backslash to\; \backslash infty\}A^k=\backslash lim\_\{k\; \backslash to\; \backslash infty\}VJ^kV^\{-1\}=V\; \backslash left\; (\backslash lim\_\{k\; \backslash to\; \backslash infty\}J^k\; \backslash right\; )V^\{-1\}=0$

On the other side, if $\backslash rho(A)>1$, there is at least one element in {{mvar|J}} that does not remain bounded as {{mvar|k}} increases, thereby proving the second part of the statement.

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

For any matrix norm {{math|{{!!}}⋅{{!!}},}} we haveThe formula holds for any Banach algebra; see Lemma IX.1.8 in {{harvnb|Dunford|Schwartz|1963}} and {{harvnb|Lax|2002|pp=195–197}}

:$\backslash rho(A)=\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}$.

Moreover, in the case of a consistent matrix norm $\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}$ approaches $\backslash rho(A)$ from above (indeed, in that case $\backslash rho(A)\; \backslash leq\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}$ for all $k$).

For any {{math|ε > 0}}, let us define the two following matrices:

:$A\_\{\backslash pm\}=\; \backslash frac\{1\}\{\backslash rho(A)\; \backslash pm\backslash varepsilon\}A.$

Thus,

:

We start by applying the previous theorem on limits of power sequences to {{math|A₊}}:

:$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; A\_+^k=0.$

This shows the existence of {{math|N₊ ∈ N}} such that, for all {{math|k ≥ N₊}},

:

Therefore,

:

Similarly, the theorem on power sequences implies that $\backslash |A\_-^k\backslash |$ is not bounded and that there exists {{math|N₋ ∈ N}} such that, for all {{math|k ≥ N₋}},

:$\backslash left\backslash |A\_-^k\; \backslash right\; \backslash |\; >\; 1.$

Therefore,

:$\backslash left\backslash |A^k\; \backslash right\backslash |^\{\backslash frac\{1\}\{k\}\}\; >\; \backslash rho(A)-\backslash varepsilon.$

Let {{math|N {{=}} max{N₊, N₋}}}. Then,

:

that is,

:$\backslash lim\_\{k\; \backslash to\; \backslash infty\}\; \backslash left\; \backslash |A^k\; \backslash right\; \backslash |^\{\backslash frac\{1\}\{k\}\}\; =\; \backslash rho(A).$

This concludes the proof.

Gelfand's formula yields a bound on the spectral radius of a product of commuting matrices: if $A\_1,\; \backslash ldots,\; A\_n$ are matrices that all commute, then

:$\backslash rho(A\_1\; \backslash cdots\; A\_n)\; \backslash leq\; \backslash rho(A\_1)\; \backslash cdots\; \backslash rho(A\_n).$

File:Gelfand's formula for a 3x3 matrix.svg

Consider the matrix

:$A=\backslash begin\{bmatrix\}$

9 & -1 & 2\\

-2 & 8 & 4\\

1 & 1 & 8

\end{bmatrix}

whose eigenvalues are {{math|5, 10, 10}}; by definition, {{math|ρ(A) {{=}} 10}}. In the following table, the values of $\backslash |A^k\backslash |^\{\backslash 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,$\backslash |.\backslash |\_1=\backslash |.\backslash |\_\backslash infty$):

{{reflist}}

• {{citation

| last1=Dunford | first1=Nelson

| last2=Schwartz | first2=Jacob

| title = Linear operators II. Spectral Theory: Self Adjoint Operators in Hilbert Space

| publisher = Interscience Publishers, Inc. | year = 1963

}}

• {{citation | last=Lax| first = Peter D. |author-link=Peter Lax

| title = Functional Analysis | publisher = Wiley-Interscience | year = 2002

| isbn = 0-471-55604-1}}

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

{{Functional Analysis}}

{{SpectralTheory}}

Category:Spectral theory

Category:Articles containing proofs