Spectral radius

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

pectral radius of a matrix

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

: ho(A) := max_i(|lambda_i|)

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

Lemma: Let "A" ∈ C"n" × "n" be a complex-valued matrix, ρ("A") its spectral radius and ||·|| a consistent matrix norm; then, for each "k" ∈ N:

: ho(A)leq |A^k|^{1/k}, forall k in mathbb{N}.

"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 for each λ we have

:|lambda|^kleq |A^k|

:and therefore

: ho(A)leq |A^k|^{1/k},,square

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 "A" ∈ C"n" × "n" be a complex-valued matrix and ρ("A") its spectral radius; then

:lim_{k o infty}A^k=0 if and only if ho(A)<1.

Moreover, if &rho;("A")>1, |A^k| is not bounded for increasing k values.

"Proof":

(lim_{k o infty}A^k = 0 Rightarrow ho(A) < 1)

:Let (v, &lambda;) be an eigenvector-eigenvalue pair for matrix "A". Since

::A^kmathbf{v} = lambda^kmathbf{v},

:we have:

::

:and, since by hypothesis v &ne; 0, we must have

::lim_{k o infty}lambda^k = 0

:which implies |&lambda;| < 1. Since this must be true for any eigenvalue &lambda;, we can conclude &rho;("A") < 1.

( ho(A)<1 Rightarrow lim_{k o infty}A^k = 0)

:From the Jordan Normal Form Theorem, we know that for any complex valued matrix "A" &isin; C"n" &times; "n", a non-singular matrix "V" &isin; C"n" &times; "n" and a block-diagonal matrix "J" &isin; C"n" &times; "n" exist such that:

::A = VJV^{-1}

:with

::J=egin{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)=egin{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_iend{bmatrix}in mathbb{C}^{m_i,m_i}, 1leq ileq s.

:It is easy to see that

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

:and, since "J" is block-diagonal,

::J^k=egin{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" &ge; "m""i" − 1:

::J_{m_i}^k(lambda_i)=egin{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^kend{bmatrix}

:Thus, if &rho;("A") < 1 then |&lambda;"i"| < 1 &forall; "i", so that

::lim_{k o infty}J_{m_i}^k=0 forall i

:which implies

::lim_{k o infty}J^k = 0.

:Therefore,

::lim_{k o infty}A^k=lim_{k o infty}VJ^kV^{-1}=V(lim_{k o infty}J^k)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.

::square

Theorem (Gelfand's formula, 1941)

For any matrix norm ||&middot;||, we have

: ho(A)=lim_{k o infty}||A^k||^{1/k}.

In other words, the Gelfand's formula shows how the spectral radius of "A" gives the asymptotic growth rate of the norm of "A""k":

:|A^k|sim ho(A)^k for k ightarrow infty.,

"Proof": For any &epsilon; > 0, consider the matrix

:: ilde{A}=( ho(A)+epsilon)^{-1}A.

:Then, obviously,

:: ho( ilde{A}) = frac{ ho(A)}{ ho(A)+epsilon} < 1

:and, by the previous theorem,

::lim_{k o infty} ilde{A}^k=0.

:That means, by the sequence limit definition, a natural number "N1" &isin; N exists such that

::forall kgeq N_1 Rightarrow | ilde{A}^k| < 1

:which in turn means:

::forall kgeq N_1 Rightarrow |A^k| < ( ho(A)+epsilon)^k

:or

::forall kgeq N_1 Rightarrow |A^k|^{1/k} < ( ho(A)+epsilon).

:Let's now consider the matrix

::check{A}=( ho(A)-epsilon)^{-1}A.

:Then, obviously,

:: ho(check{A}) = frac{ ho(A)}{ ho(A)-epsilon} > 1

:and so, by the previous theorem,|check{A}^k| is not bounded.

:This means a natural number "N2" &isin; N exists such that

::forall kgeq N_2 Rightarrow |check{A}^k| > 1

:which in turn means:

::forall kgeq N_2 Rightarrow |A^k| > ( ho(A)-epsilon)^k

:or

::forall kgeq N_2 Rightarrow |A^k|^{1/k} > ( ho(A)-epsilon).

:Taking

::N:=max(N_1,N_2)

:and putting it all together, we obtain:

::forall epsilon>0, exists Ninmathbb{N}: forall kgeq N Rightarrow ho(A)-epsilon < |A^k|^{1/k} < ho(A)+epsilon

:which, by definition, is

::lim_{k o infty}|A^k|^{1/k} = ho(A).,,square

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 ho(A_1 A_2 ldots A_n) leq ho(A_1) ho(A_2)ldots ho(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 epsilon>0, exists Ninmathbb{N}: forall kgeq N Rightarrow ho(A) leq |A^k|^{1/k} < ho(A)+epsilon

:which, by definition, is

:lim_{k o infty}|A^k|^{1/k} = ho(A)^+.

Example: Let's consider the matrix:A=egin{bmatrix}9 & -1 & 2\-2 & 8 & 4\1 & 1 & 8end{bmatrix}

whose eigenvalues are 5, 10, 10; by definition, its spectral radius is &rho;("A")=10. 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 |.|_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

pectral radius of a bounded linear operator

For a bounded linear operator "A" and the operator norm ||&middot;||, again we have

: ho(A) = lim_{k o infty}|A^k|^{1/k}.

pectral radius of a graph

The spectral radius of a graph is defined to be the spectral radius of its adjacency matrix.

ee also

* Spectral gap

External links

* [http://people.csse.uwa.edu.au/gordon/planareig.html Spectral Radius of Planar Graphs]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Spectral gap — In mathematics, the spectral gap is the difference between the two largest eigenvalues of a matrix or operator; alternately, it is sometimes taken as the smallest non zero eigenvalue. Various theorems relate this difference to other properties of …   Wikipedia

  • Charge radius — The rms charge radius is a measure of the size of an atomic nucleus, particularly of a proton or a deuteron. It can be measured by the scattering of electrons by the nucleus and also inferred from the effects of finite nuclear size on electron… …   Wikipedia

  • Perron–Frobenius theorem — In linear algebra, the Perron–Frobenius theorem, proved by Oskar Perron (1907) and Georg Frobenius (1912), asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding… …   Wikipedia

  • Matrix norm — In mathematics, a matrix norm is a natural extension of the notion of a vector norm to matrices. Contents 1 Definition 2 Induced norm 3 Entrywise norms 3.1 Frobenius norm …   Wikipedia

  • Spectrum (functional analysis) — In functional analysis, the concept of the spectrum of a bounded operator is a generalisation of the concept of eigenvalues for matrices. Specifically, a complex number λ is said to be in the spectrum of a bounded linear operator T if… …   Wikipedia

  • Banach algebra — In mathematics, especially functional analysis, a Banach algebra, named after Stefan Banach, is an associative algebra A over the real or complex numbers which at the same time is also a Banach space. The algebra multiplication and the Banach… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • Numerical range — In the mathematical field of linear algebra and convex analysis, the numerical range of a square matrix with complex entries is a subset of the complex plane associated to the matrix. If A is an n × n matrix with complex entries, then… …   Wikipedia

  • Normal operator — In mathematics, especially functional analysis, a normal operator on a complex Hilbert space H (or equivalently in a C* algebra) is a continuous linear operator that commutes with its hermitian adjoint N*: Normal operators are important because… …   Wikipedia

  • Operator norm — In mathematics, the operator norm is a means to measure the size of certain linear operators. Formally, it is a norm defined on the space of bounded linear operators between two given normed vector spaces. Contents 1 Introduction and definition 2 …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.