spectral radius
≈ 11 min read
Names in other languages
- Italianoraggio spettrale
- Englishspectral radius
- eospektra radiuso
- Españolradio espectral
- DeutschSpektralradius
- Françaisrayon spectral
- فارسیشعاع طیفی
- 日本語スペクトル半径
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. 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 \rho(\cdot) .
In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. 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 \rho(\cdot) .
Definition
Matrices
Let be the eigenvalues of a matrix . The spectral radius of is defined as \rho(A) = \max \left \{ |\lambda_1|, \dotsc, |\lambda_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 \|\cdot\| ; and on the other hand, Gelfand's formula states that \rho(A) = \lim_{k\to\infty} \|A^k\|^{1/k} . Both of these results are shown below. However, the spectral radius does not necessarily satisfy \|A\mathbf{v}\| \leqslant \rho(A) \|\mathbf{v}\| for arbitrary vectors \mathbf{v} \in \mathbb{C}^n . To see why, let r > 1 be arbitrary and consider the matrix C_r = \begin{pmatrix} 0 & r^{-1} \\ r & 0 \end{pmatrix} . The characteristic polynomial of C_r is \lambda^2 - 1 , so its eigenvalues are \{-1, 1\} and thus \rho(C_r) = 1 . However, C_r \mathbf{e}_1 = r \mathbf{e}_2 . As a result, \| C_r \mathbf{e}_1 \| = r > 1 = \rho(C_r) \|\mathbf{e}_1\|. As an illustration of Gelfand's formula, note that \|C_r^k\|^{1/k} \to 1 as k \to \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 \|A\mathbf{v}\| \leqslant \rho(A) \|\mathbf{v}\| for all \mathbf{v} \in \mathbb{C}^n is when A is a Hermitian matrix and \|\cdot\| 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\mathbf{v}\| = \|U^*DU\mathbf{v}\| = \|DU\mathbf{v}\| \leqslant \rho(A) \|U\mathbf{v}\| = \rho(A) \|\mathbf{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 \lambda for which A - \lambda I is not bijective. We denote the spectrum by \sigma(A) = \left\{ \lambda \in \Complex: A - \lambda I \; \text{is not bijective} \right\} The spectral radius is then defined as the supremum of the magnitudes of the elements of the spectrum: \rho(A) = \sup_{\lambda \in \sigma(A)} |\lambda| Gelfand's formula, also known as the spectral radius formula, also holds for bounded linear operators: letting \|\cdot\| denote the operator norm, we have \rho(A) = \lim_{k \to \infty}\|A^k\|^{\frac{1}{k}}=\inf_{k\in\mathbb{N}^*} \|A^k\|^{\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.
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 \mathbf{R} \ : \ \sum\nolimits_{v \in V(G)} \left \|f(v)^2 \right \| Let be the adjacency operator of : \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 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 sub-multiplicative matrix norm . Then for each integer k \geqslant 1 : \rho(A)\leq \|A^k\|^{\frac{1}{k}}. Proof Let be an eigenvector-eigenvalue pair for a matrix A. By the sub-multiplicativity of the matrix norm, we get: |\lambda|^k\|\mathbf{v}\| = \|\lambda^k \mathbf{v}\| = \|A^k \mathbf{v}\| \leq \|A^k\|\cdot\|\mathbf{v}\|. Since , we have |\lambda|^k \leq \|A^k\| and therefore \rho(A)\leq \|A^k\|^{\frac{1}{k}}. concluding the proof.
Symmetric matrices
For real-valued matrices A the inequality \rho(A) \leq {\|A\|}_{2} holds in particular, where {\|\cdot\|}_{2} denotes the spectral norm. In the case where A is symmetric, this inequality is tight: Theorem. Let A \in \mathbb{R}^{n \times n} be symmetric, i.e., A = A^T. Then it holds that \rho(A) = {\|A\|}_{2}. Proof Let (v_i, \lambda_i)_{i=1}^{n} be the eigenpairs of A. Due to the symmetry of A, all v_i and \lambda_i are real-valued and the eigenvectors v_i are orthonormal. By the definition of the spectral norm, there exists an x \in \mathbb{R}^{n} with {\|x\|}_{2} = 1 such that {\|A\|}_{2} = {\| A x \|}_{2}. Since the eigenvectors v_i form a basis of \mathbb{R}^{n}, there exists factors \delta_{1}, \ldots, \delta_{n} \in \mathbb{R}^{n} such that \textstyle x = \sum_{i = 1}^{n} \delta_{i} v_{i} which implies that A x = \sum_{i = 1}^{n}\delta_{i} A v_{i} = \sum_{i = 1}^{n} \delta_{i} \lambda_{i} v_{i}. From the orthonormality of the eigenvectors v_i it follows that {\| A x\|}_{2} = \| \sum_{i = 1}^{n} \delta_{i} \lambda_{i} v_{i}\|_{2} = \sum_{i = 1}^{n} \cdot \cdot {\| v_{i}\|}_{2} = \sum_{i = 1}^{n} \cdot and {\|x\|}_{2} = \| \sum_{i = 1}^{n} \delta_{i} v_{i} \|_{2} = \sum_{i = 1}^{n} \cdot {\| v_{i} \|}_{2} = \sum_{i = 1}^{n} . Since x is chosen such that it maximizes {\|Ax\|}_{2} while satisfying {\|x\|}_{2} = 1, the values of \delta_{i} must be such that they maximize \textstyle \sum_{i = 1}^{n} \cdot while satisfying \textstyle \sum_{i = 1}^{n} = 1. This is achieved by setting \delta_{k} = 1 for k = \mathrm{arg\,max}_{i=1}^{n} and \delta_{i} = 0 otherwise, yielding a value of {\|Ax\|}_{2} = = \rho(A).
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 \to \infty} A^k = 0. On the other hand, if , \lim_{k \to \infty} \|A^k\| = \infty . 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 \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 by hypothesis, we must have \lim_{k \to \infty}\lambda^k = 0, which implies |\lambda| . Since this must be true for any eigenvalue \lambda , 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}(\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 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 -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) then for all |\lambda_i| . Hence for all 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 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. \rho(A)=\lim_{k \to \infty} \left \|A^k \right \|^{\frac{1}{k}} . Moreover, in the case of a consistent matrix norm \lim_{k \to \infty} \left \|A^k \right \|^{\frac{1}{k}} approaches \rho(A) from above (indeed, in that case \rho(A) \leq \left \|A^k \right \|^{\frac{1}{k}} for all k ).
Proof
For any , let us define the two following matrices: A_{\pm}= \frac{1}{\rho(A) \pm\varepsilon}A. Thus, \rho \left (A_{\pm} \right ) = \frac{\rho(A)}{\rho(A) \pm \varepsilon}, \qquad \rho (A_+) We start by applying the previous theorem on limits of power sequences to : \lim_{k \to \infty} A_+^k=0. This shows the existence of such that, for all , \left\|A_+^k \right \| Therefore, \left \|A^k \right \|^{\frac{1}{k}} Similarly, the theorem on power sequences implies that \|A_-^k\| is not bounded and that there exists such that, for all , \left\|A_-^k \right \| > 1. Therefore, \left\|A^k \right\|^{\frac{1}{k}} > \rho(A)-\varepsilon. Let . Then, \forall \varepsilon>0\quad \exists N\in\mathbf{N} \quad \forall k\geq N \quad \rho(A)-\varepsilon that is, \lim_{k \to \infty} \left \|A^k \right \|^{\frac{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 \cdots A_n) \leq \rho(A_1) \cdots \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\|^{\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 ):
Bibliography
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374766527 under CC BY-SA 4.0; modifications have been made.