The spectral radius 
For Hermitian matrices (or more generally normal matrices, those satisfying 
Two classes of matrices for which the spectral radius is known are as follows.
- Unitary matrices (
): these have all their eigenvalues on the unit circle and so
.
- Nilpotent matrices (
for some positive integer
): such matrices have only zero eigenvalues, so
, even though
can be arbitrarily large.
The spectral radius of
Bounds
The spectral radius is bounded above by any consistent matrix norm (one satisfying 
Theorem 1. For any
However, the spectral radius is not a norm and it can be zero when the 
Limit of Norms of Powers
The spectral radius can be expressed as a limit of norms of matrix powers.
Theorem 2 (Gelfand). For
.
The theorem implies that for large enough 
Spectral Radius of a Product
Little can be said about the spectral radius of a product of two matrices. The example
shows that we can have 
we have 
Condition Number Lower Bound
For a nonsingular matrix 
This bound can be very weak for nonnormal matrices.
Power Boundedness
In many situations we wish to know whether the powers of a matrix converge to zero. The spectral radius gives a necessary and sufficient condition for convergence.
Theorem 3. For
as
if and only if
.
The proof of Theorem 3 is straightforward if
Computing the Spectral Radius
Suppose 
In this pseudocode, norm(x) denotes the x.
Choose n-vector q_0 such that norm(q_0) = 1.
for k=1,2,...
z_k = A q_{k-1} % Apply A.
q_k = z_k / norm(z_k) % Normalize.
mu_k = q_k^*Aq_k % Rayleigh quotient.
end
The normalization is to avoid overflow and underflow and the 
If 
Here is an example where the power method converges quickly, thanks to the substantial ratio of 
>> rng(1); A = rand(4); eig_abs = abs(eig(A)), q = rand(4,1);
>> for k = 1:5, q = A*q; q = q/norm(q); mu = q'*A*q;
>> fprintf('%1.0f %7.4e\n',k,mu)
>> end
eig_abs =
1.3567e+00
2.0898e-01
2.5642e-01
1.9492e-01
1 1.4068e+00
2 1.3559e+00
3 1.3580e+00
4 1.3567e+00
5 1.3567e+00
Nonnegative Matrices
For real matrices with nonnegative elements, much more is known about the spectral radius. Perron–Frobenius theory says that if 
rand function, which produces random matrices with elements on 
>> rng(1); A = rand(4); e = sort(eig(A)) e = -2.0898e-01 1.9492e-01 2.5642e-01 1.3567e+00
If 
![e = [1,1,\dots,1]^T](https://s0.wp.com/latex.php?latex=e+%3D+%5B1%2C1%2C%5Cdots%2C1%5D%5ET&bg=ffffff&fg=222222&s=0&c=20201002)
References
- Shmuel Friedland, Revisiting Matrix Squaring, Linear Algebra Appl., 154–156, 59-63, 1991.
- J. H. Wilkinson, The Algebraic Eigenvalue Problem, Oxford University Press, 1965, pp.~615–617.
Related Blog Posts
This article is part of the “What Is” series, available from https://nhigham.com/index-of-what-is-articles/ and in PDF form from the GitHub repository https://github.com/higham/what-is.
upper Hessenberg matrix 
has the property that 
for 
. For 
, the structure is 
flops. For example, the first stage of LU factorization needs to eliminate just one element, by adding a multiple of row 
): 
for all 
, then 
for any 
, which means that there is one linearly independent eigenvector associated with each eigenvalue of 
real parameters (the Schur parametrization), which are essentially the angles in the Givens QR factorization (note that in the QR factorization 
, 
is triangular and unitary and hence diagonal). The MATLAB function 
. For 
: 
of 
is an invariant subspace for 
if 
, that is, if 
implies 
. 
and 
is an invariant subspace of 
implies 
.
is a 
, where 
and a two-dimensional invariant subspace 
, where 
denotes the 
be linearly independent vectors. Then 
is an invariant subspace of 
for 
. Writing ![X = [x_1,x_2,\dots,x_p]\in\mathbb{C}^{n \times p}](https://s0.wp.com/latex.php?latex=X+%3D+%5Bx_1%2Cx_2%2C%5Cdots%2Cx_p%5D%5Cin%5Cmathbb%7BC%7D%5E%7Bn+%5Ctimes+p%7D&bg=ffffff&fg=222222&s=0&c=20201002)
, this condition can be expressed as 
. 
in (1) then 
with 
square and nonsingular, so 
, that is, 
the spectrum (set of eigenvalues) of 
the pseudoinverse of 
and 
. Then 
. Furthermore, if 
is an eigenpair of 
then 
is an eigenpair of 
is an eigenpair of 
, and 
since the columns of 
is an eigenpair of 
for some 
, and 
, since 
. Hence 
gives 
, so 
so that ![W = [X,\,Y]](https://s0.wp.com/latex.php?latex=W+%3D+%5BX%2C%5C%2CY%5D&bg=ffffff&fg=222222&s=0&c=20201002)
is nonsingular. Let ![W^{-1} = \left[\begin{smallmatrix} G \\ H \end{smallmatrix}\right]](https://s0.wp.com/latex.php?latex=W%5E%7B-1%7D+%3D+%5Cleft%5B%5Cbegin%7Bsmallmatrix%7D+G+%5C%5C+H++++++++++++++++%5Cend%7Bsmallmatrix%7D%5Cright%5D&bg=ffffff&fg=222222&s=0&c=20201002)
and note that 
implies 
and 
. We have ![\notag W^{-1}AW = \begin{bmatrix} G \\H \end{bmatrix} [AX,\, AY] = \begin{bmatrix} G \\H \end{bmatrix} [XB,\, AY] = \begin{bmatrix} B & GAY\\ 0 & HAY \end{bmatrix}, \qquad (2)](https://s0.wp.com/latex.php?latex=%5Cnotag++W%5E%7B-1%7DAW+%3D++%5Cbegin%7Bbmatrix%7D++++G+%5C%5CH++%5Cend%7Bbmatrix%7D+%5BAX%2C%5C%2C+AY%5D++%3D+%5Cbegin%7Bbmatrix%7D++++G+%5C%5CH++%5Cend%7Bbmatrix%7D+++%5BXB%2C%5C%2C+AY%5D++++%3D++%5Cbegin%7Bbmatrix%7D++++B+%26+GAY%5C%5C++++0+%26+HAY++%5Cend%7Bbmatrix%7D%2C+%5Cqquad+%282%29+&bg=ffffff&fg=222222&s=0&c=20201002)
, 
chosen to be unitary. 
, where 
is unitary and 
and writing ![Q = [Q_1,\,Q_2]](https://s0.wp.com/latex.php?latex=Q+%3D+%5BQ_1%2C%5C%2CQ_2%5D&bg=ffffff&fg=222222&s=0&c=20201002)
, where 
is 
, and 
is 
, we have 
. Hence 
, the Schur decomposition provides a nested sequence of invariant subspaces of 
matrix and let 
and 
. Then the 
matrix 
is the submatrix of 
and the columns indexed by 
. For example, for the matrix ![\notag \begin{bmatrix} ~\fbox{1} & \fbox{2} & 3\mskip2mu \\ ~~4 & 5 & 6\mskip2mu~ \\ ~\fbox{7} & \fbox{8} & 9~\mskip2mu \end{bmatrix} = \begin{bmatrix} ~\fbox{1} & \fbox{2} & 3\mskip2mu~ \\[1pt] ~\fbox{4} & 5 & 6\mskip2mu~ \\ 7 & \fbox{8} & 9\mskip2mu \end{bmatrix},](https://s0.wp.com/latex.php?latex=%5Cnotag+++++%5Cbegin%7Bbmatrix%7D+%7E%5Cfbox%7B1%7D+%26+%5Cfbox%7B2%7D+%26+3%5Cmskip2mu+%5C%5C++++++++++++++++++++++++%7E%7E4+%26+5+%26+6%5Cmskip2mu%7E+%5C%5C++++++++++++++++++++++++%7E%5Cfbox%7B7%7D+%26+%5Cfbox%7B8%7D+%26+9%7E%5Cmskip2mu++++++++%5Cend%7Bbmatrix%7D+%3D+++++%5Cbegin%7Bbmatrix%7D+%7E%5Cfbox%7B1%7D+%26+%5Cfbox%7B2%7D+%26+3%5Cmskip2mu%7E+%5C%5C%5B1pt%5D++++++++++++++++++++++++%7E%5Cfbox%7B4%7D+%26+5+%26+6%5Cmskip2mu%7E+%5C%5C++++++++++++++++++++++++7+%26+%5Cfbox%7B8%7D+%26+9%5Cmskip2mu++++++++%5Cend%7Bbmatrix%7D%2C+&bg=ffffff&fg=222222&s=0&c=20201002)
and columns 
matrix elements and the matrix itself, but there are many of intermediate size: an 
submatrices in total (counting both square and nonsquare submatrices). 
and 
, 
, then 
, 
, then 
we denote by 
the sequence 
. Thus 
is another way of writing 
. 
for the submatrix of 
to 
, that is, 
denotes the 
the 
matrix 
matrix, where each element is a ![\notag A = \left[\begin{array}{cc|cc} a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\\hline a_{31} & a_{32} & a_{33} & a_{34}\\ a_{41} & a_{42} & a_{43} & a_{44}\\ \end{array}\right] = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix},](https://s0.wp.com/latex.php?latex=%5Cnotag+++A+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7Ccc%7D+++++++++a_%7B11%7D+%26+a_%7B12%7D+%26+a_%7B13%7D+%26+a_%7B14%7D%5C%5C+++++++++a_%7B21%7D+%26+a_%7B22%7D+%26+a_%7B23%7D+%26+a_%7B24%7D%5C%5C%5Chline+++++++++a_%7B31%7D+%26+a_%7B32%7D+%26+a_%7B33%7D+%26+a_%7B34%7D%5C%5C+++++++++a_%7B41%7D+%26+a_%7B42%7D+%26+a_%7B43%7D+%26+a_%7B44%7D%5C%5C+++++++++%5Cend%7Barray%7D%5Cright%5D++++%3D++%5Cbegin%7Bbmatrix%7D+++++++++A_%7B11%7D+%26+A_%7B12%7D+%5C%5C+++++++++A_%7B21%7D+%26+A_%7B22%7D++++++++%5Cend%7Bbmatrix%7D%2C+&bg=ffffff&fg=222222&s=0&c=20201002)
, 
, 
, 
carried out on floating-point numbers. For example, evaluating the expression 
takes three flops. A square root, which occurs infrequently in numerical computation, is also counted as one flop. 
of two 
can be written 
additions, or 
of two 
inner products, costing 
flops. As we are usually interested in flop counts for large dimensions we retain only the highest order terms, so we regard 
flops. 
is a scalar, 
are 
are 
flops
flops
flops or less, so the interest is in the exponent (
and comparing competing algorithms is more complicated. 
floating-point operations per second) for 
is an 
matrix 
.
(overdetermined or underdetermined) 
minimizes 
and has the minimum 
is an SVD, where the 
matrix 
and 
are unitary and 
with 
(so that 
) with 
, then
. This formula gives an easy way to prove many identities satisfied by the pseudoinverse. In MATLAB, the function 
and 
.
is 
.
, 
and if 
.
is the transpose:
for 
. A sufficient condition for this equality to hold is that 
.
as 
. The convergence is at an asymptotically quadratic rate. However, about 
iterations are required to reach the asymptotic phase, where 
, so the iteration is slow to converge when 
is compact and convex (a nontrivial property proved by Toeplitz and Hausdorff), and it contains all the eigenvalues of 
matrices, with the eigenvalues shown as black dots. They were plotted using the function 
,
lies between the largest and smallest eigenvalues of the Hermitian matrix 
, which define a vertical strip in which the numerical range lies. Since 
, we can apply the same reasoning to the rotated matrix 
, and taking a range of ![\theta\in[0,\pi]](https://s0.wp.com/latex.php?latex=%5Ctheta%5Cin%5B0%2C%5Cpi%5D&bg=ffffff&fg=222222&s=0&c=20201002)
we obtain an approximation the boundary of the numerical range.
is the largest eigenvalue of the Hermitian matrix 
for small positive 
.
. Also, 
, where 
is the spectral radius (the largest absolute value of any eigenvalue), since 
.
does not hold in general). However, it is it true that
then we can bound 
for all 
block 
the Schur complement is 
. It is denoted by 
. The block with respect to which the Schur complement is taken need not be the 
is nonsingular, the Schur complement of 
.![\alpha = [i_1,i_2,\dots,i_k]](https://s0.wp.com/latex.php?latex=%5Calpha+%3D+%5Bi_1%2Ci_2%2C%5Cdots%2Ci_k%5D&bg=ffffff&fg=222222&s=0&c=20201002)
, where 
, the Schur complement of 
in 
, where 
is the complement of 
:
and 
blocks in this equation gives 
and 
. Hence 
, which is the Schur complement of 
) element of 
-matrices,
is the 
.
, and since congruences preserve inertia (the number of positive, zero, and negative eigenvalues), 
, where “+” denotes the Moore-Penrose pseudo-inverse. The generalized Schur complement is useful in the context of Hermitian positive semidefinite matrices, as the following result shows.
and 
are both positive semidefinite.
for all 
at 
). The polynomial 
.
, a degree 
, but 
of lowest degree such that 
is the minimal polynomial of 
, and in particular it divides the characteristic polynomial. Indeed by polynomial long division we can write 
, where the degree of 
then we have a contradiction to the minimality of the degree of 
and so 
and 
are two different monic polynomials of minimum degree 
such that 
, 
, then 
is a polynomial of degree less than 
, and we can scale 
to be monic, so by the minimality of 
, or 
.
, since 
. On the other hand, for the Jordan block
.
are the distinct eigenvalues of 
is the dimension of the largest Jordan block in which 
appears. This expression is composed of linear factors (that is, 
for all ![\notag A = \left[\begin{array}{cc|c|c|c} \lambda & 1 & & & \\ & \lambda & & & \\\hline & & \lambda & & \\\hline & & & \mu & \\\hline & & & & \mu \end{array}\right]](https://s0.wp.com/latex.php?latex=%5Cnotag++A+%3D+%5Cleft%5B%5Cbegin%7Barray%7D%7Bcc%7Cc%7Cc%7Cc%7D++++++%5Clambda+%26++1++++++%26+++++++++%26+++++%26+++%5C%5C++++++++++++++%26+%5Clambda+%26+++++++++%26+++++%26+++%5C%5C%5Chline++++++++++++++%26+++++++++%26+%5Clambda+%26+++++%26+++%5C%5C%5Chline++++++++++++++%26+++++++++%26+++++++++%26+%5Cmu+%26++++%5C%5C%5Chline++++++++++++++%26+++++++++%26+++++++++%26+++++%26+%5Cmu+++%5Cend%7Barray%7D%5Cright%5D+&bg=ffffff&fg=222222&s=0&c=20201002)
, while the characteristic polynomial is 
.
? Since 
, we have 
for 
. For any linear polynomial 
, 
, which is nonzero since 
has rank 
has rank 
to a linear system of equations 
.
.
.
(where we include the permutations in 
). Most of the work is in the LU factorization, which costs 
, which total only 
satisfies (omitting constants)
is the matrix condition number in the 
-norm. We would like refinement to produce a solution accurate to precision 
.
to the level of 
, the unit roundoff for IEEE single precision arithmetic.
is no larger than 
and can be much smaller, especially if 
by substitution in single precision, obtaining 
in single precision.
entirely in double precision arithmetic. The algorithm achieves the same limiting accuracy (4) and limiting residual (3) provided that 
.
is not formed but is applied to a vector as a multiplication with 
Nick Higham 