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 λ₁, …, λ_"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 ρ("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, λ) be an eigenvector-eigenvalue pair for matrix "A". Since

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

:we have:

:and, since by hypothesis v ≠ 0, we must have

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

:which implies |λ| < 1. Since this must be true for any eigenvalue λ, we can conclude ρ("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" ∈ C^{"n" × "n"}, a non-singular matrix "V" ∈ C^{"n" × "n"} and a block-diagonal matrix "J" ∈ C^{"n" × "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" × "m"_"i" Jordan block states that, for "k" ≥ "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 ρ("A") < 1 then |λ_"i"| < 1 ∀ "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 ρ("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 ||·||, 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 ε > 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 "N₁" ∈ 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 "N₂" ∈ 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 ρ("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 ||·||, 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
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
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
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

Academic Dictionaries and Encyclopedias

Spectral radius

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Spectral radius

Look at other dictionaries:

Share the article and excerpts

Direct link