Teorema de Perron-Frobenius

En àlgebra llineal, la teorema de Perron-Frobenius, provat per Oskar Perron (1907) i Georg Frobenius (1912), afirma que una matriu quadrada real en entrades positives té un valor propi real únic més gran i que el vector propi corresponent pot elegir-se per a tindre estrictament components positius, i també afirma una declaració similar per a certes classes de matrius no negatives. Esta teorema té importants aplicacions a la teoria de la provabilitat (ergodicidad de les cadenes de Markov); a la teoria de sistemes dinàmics (subdesplazamientos de tipo finito); a l'economia (teorema de Okishio, condició de Hawkins-Simon); a la demografia (model de distribució d'edat de la població de Leslie ); a les rets socials (procés d'aprenentage DeGroot), als buscadors d'Internet i inclús al rànquing d'equips de fútbol. El primer en discutir l'orde dels jugadors dins dels tornejos usant vectores propis de Perron-Frobenius és Edmund Landau .

Declaració

Definim una matriu positiva com una matriu en entrades reals tal que tots els seus elements són positius, i una matriu negativa de la mateixa manera. Els valors propis d'una matriu quadrada real A són número complejo que componen l'espectre de la matriu. La taxa de creiximent exponencial de la matriu potencia A^k quan k → ∞ està controlada pel valor propi de A en el valor absolut més gran (mòdul). La teorema de Perron-Frobenius descriu les propietats del valor propi principal i dels vectores propis corresponents quan A és una matriu quadrada real no negativa. Els primers resultats es varen deure a Oskar Perron (1907) i es referien a matrius positives. Posteriorment, Georg Frobenius (1912) va trobar la seua extensió a certes classes de matrius no negatives.

Matrius positives

Siga $A=(a_{ij})$ una matriu positiva de $n\times n$: $a_{ij}>0$ per a $1\le i,j\le n$. Llavors les següents proposicions són vàlides.

1. Hi ha un número real positiu r , cridat raïl de Perron o autovalor de Perron-Frobenius (també cridat autovalor principal o autovalor dominant ), de manera que r és un autovalor de A i qualsevol un atre autovalor λ (possiblement complex ) en valor absolut és estrictament menor que r , | λ | < r. Per tant, el radi espectral A^T és igual a r. Si els coeficients de la matriu són algebraics, açò implica que el valor propi és un número de Perron.
2. El valor propi de Perron-Frobenius és simple: r és una raïl del polinomi característic de A. En conseqüència, l'espai propi associat a r és unidimensional. (Lo mateix és cert per a l'espai propi esquerre, és dir, l'espai propi para A^T , la transposició de A).
3. Existix un vector propi v=(v₁,...,v_n) de A en valor propi r tal que tots els components de v són positius: A v = rv, v _i> 0 per a 1 ≤ i ≤ n . (Respectivament, existix un vector propi esquerre positiu w: w ^T A = rw ^T, w _i > 0.) Es coneix en la lliteratura baix moltes variacions com el vector de Perron , vector propi de Perron, Vector propi de Perron-Frobenius , vector propi principal o vector propi dominant.
4. No hi ha atres autovectores positius (ademés no negatius) llevat els múltiples positius de v (respectivament, autovectores esquerres llevat w), és dir, tots els demés autovectores deuen tindre a lo manco un component negatiu o no real.
5. $\underset{k\to \mathrm{\infty }}{\lim }{A}^k/r^k=v{w}^T$, a on els vectores propis esquerre i dret para A estan normalisats de modo que w ^T v = 1. Ademés, la matriu vw ^T és la proyecció sobre l'espai propi corresponent a r . Esta proyecció es diu proyecció Perron.
6. Fòrmula de Collatz –Wielandt : per a tots els vectores x no negatius no nuls, siga f ( x ) el valor mínim de [Ax] _i/x_i pres sobre tots aquells i tals que x _i ≠ 0. Llavors f és un valor real funció valorada que el seu màxim sobre tots els vectores x no negatius distints de ceroes el valor propi de Perron-Frobenius.
7. Una fòrmula Collatz-Wielandt "Mín-máx" pren una forma similar a l'anterior: per a tots els vectores estrictament positius x , siga g (x) el valor màxim de [Ax] i/x _i pres sobre i . Llavors g és una funció en valor real que el seu mínim sobre tots els vectores estrictament positius x és el valor propi de Perron-Frobenius.

1. Birkhoff - Varga fòrmula:Siguen x i i vectores estrictament positius. Llavors:$r=\underset{x>0}{\sup }\underset{y>0}{\inf }\frac{y^{\mathrm{\top }}Ax}{y^{\mathrm{\top }}x}=\underset{x>0}{\inf }\underset{y>0}{\sup }\frac{y^{\mathrm{\top }}Ax}{y^{\mathrm{\top }}x}=\underset{x>0}{\inf }\underset{y>0}{\sup }\sum _{i,j=1}^n{x}_i{A}_{ij}{y}_j/\sum _{i=1}^n{y}_i{x}_i.$
2. Donsker, Varadhan i S. Friedland fórmulan: Que p siga un vector de provabilitat i x un vector estrictament positiu. Llavors:$r=\underset{p}{\sup }\underset{x>0}{\inf }\sum _{i=1}^n{p}_i[Ax{]}_i/x_i.$
3. Fòrmula de Fiedler, $r=\underset{z>0}{\sup }\underset{x>0,y>0,x\circ y=z}{\inf }\frac{y^{\mathrm{\top }}Ax}{y^{\mathrm{\top }}x}=\underset{z>0}{\sup }\underset{x>0,y>0,x\circ y=z}{\inf }\sum _{i,j=1}^n{x}_i{A}_{ij}{y}_j/\sum _{i=1}^n{y}_i{x}_i.$
4. El valor propi de Perron-Frobenius satisfà les desigualtats.

$\underset{i}{\min }\sum _j{a}_{ij}\le r\le \underset{i}{\max }\sum _j{a}_{ij}.$

Totes estes propietats s'estenen més allà de les matrius estrictament positives a les matrius primitives (vore més avall). Els fets 1-7 es poden trobar en Meyer, capítul 8, afirmacions 8.2.11-15, pàgina 667, i eixercicis 8.2.5, 7,9, pàgines 668-669.

Els vectores propis esquerre i dret w i v a voltes es varen normalisar de manera que la suma dels seus components és igual a 1; en este cas, a voltes es denominen autovectores estocàstics . A sovint es normalisen de modo que el vector propi dret v suma un, mentres que $w^{T}v=1$.

Matrius no negatives

Existix una extensió per a matrius en entrades no negatives. Ya que qualsevol matriu no negativa pot obtindre's com a llímit de matrius positives, s'obté l'existència d'un vector propi en components no negatius; el valor propi corresponent serà no negatiu i major o igual , en valor absolut, a tots els demés valors propis. No obstant, per a l'eixemple $A=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, el valor propi màxim r = 1 té el mateix valor absolut que l'atre valor propi −1; mentres que per a$A=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right)$, el valor propi màxim és r = 0, que no és una raïl simple del polinomi característic, i el vector propi corresponent (1, 0) no és estrictament positiu.

No obstant, Frobenius va trobar una subclasse especial de matrius no negatives, matrius irreducibles, per a les que és possible una generalisació no trivial. Per a tal matriu, encara que els valors propis que alcancen el valor absolut màxim poden no ser únics, la seua estructura està baix control: tenen la forma $\omega r$, a on r és realment estrictament positiu, i $\omega$ és un valor propi real estrictament positiu, i $\omega$ rancs sobre les raïls h- ésimas complexes d'1 per a algun sancer positiu h cridat periodo de la matriu. El vector propi corresponent a r té components estrictament positius (en contrast en el cas general de matrius no negatives, a on els components són solament no negatius). Ademés, tots estos valors propis són raïls simples del polinomi característic. A continuació es descriuen atres propietats.

Classificació de matrius

Siga A una matriu quadrada (no necessàriament positiva o inclús real). La matriu A és irreducible si es complix alguna de les següents propietats equivalents.

Definició 1: A no té subespacios de coordenades invariantes no trivials. Ací, un subespacio vectorial de coordenades no trivial significa un subespacio llineal comprés per qualsevol subconjunt adequat de vectores de base estàndar de ${ℝ}^n$. Més explícitament, per a qualsevol subespacio llineal generat per vectores de base estàndar i_i1 , ..., i_ik, 0 < k < n, la seua image baixe l'acció de A no està continguda en el mateix subespacio vectorial.

De manera equivalent, la representació de grup de $(ℝ,+)$ en ${ℝ}^n$ donada per $t\mapsto \exp (tA)$ no té subespacios de coordenades invariantes no trivials. (En comparació, açò seria una representació irreductible si no hi haguera subespacios invariantes no trivials en absolut, no solament considerant els subespacios de coordenades).

Definició 2: A no es pot conjugar en forma triangular superior de bloc per mig d'una matriu de permutació P:

$PA{P}^{-1}\ne \left(\begin{array}{cc}E& F\\ 0& G\end{array}\right),$

a on I i G són matrius quadrades no trivials (és dir, de tamany major que zero).

Si A no és negatiu, s'aplica una atra definició:

Definició 3: Un pot associar-se en una matriu A un cert grafo dirigit G A. Té exactament n vèrtiços, a on n és el tamany de A , i hi ha una aresta des del vèrtiç i al vèrtiç j precisament quan A _ij > 0. Llavors la matriu A és irreducible si i solament si la seua grafo associat G _A està fortament conectat .

Una matriu és reducible si no és irreducible.

Una matriu A és primitiva si no és negativa i la seua potència m és positiva per a algun número natural m (és dir, totes les entrades de A ^m són positives).

Siga A no negatiu. Fixe un índex i i definixca el periodo de l'índex i com el màxim comú divisor de tots els número natural m tal que (A ^m) _ii > 0. Quan A és irreducible, el periodo de cada índex és el mateix i es diu periodo de A . De fet, quan A és irreductible, el periodo es pot definir com el màxim comú divisor de les llongituts dels camins tancats dirigits en G _A (vore Cuines pàgina 16). El periodo també es denomina índex de imprimitividad ( Meyer pàgina 674) o l'orde de ciclicidad. Si el periodo és 1, A és aperiódico. Es pot demostrar que les matrius primitives són les mateixes que les matrius irreductibles aperiódicas no negatives.

Tots els enunciats de la teorema de Perron-Frobenius per a matrius positives seguixen sent verdaders per a matrius primitives. Les mateixes declaracions també són vàlides per a una matriu irreductible no negativa, excepto que pot posseir varis valors propis el valor absolut dels quals és igual a la seua ràdio espectral, per lo que les declaracions deuen modificar-se en conseqüència. De fet, el número d'eixos valors propis és igual al periodo.

Els resultats de les matrius no negatives varen ser obtinguts per primera volta per Frobenius en 1912.

Teorema de Perron-Frobenius per a matrius no negatives irreducibles

Deixe que A siga un irreducible no negatiu n × n matriu en periodo h i espectral ràdio ρ (A) = r . Llavors les següents declaracions són vàlides.

1. El número r és un número real positiu i és un valor propi de la matriu A, cridat valor propi de Perron-Frobenius.
2. El valor propi r de Perron-Frobenius és simple. Abdós espais propis, dret i esquerre, associats en r són unidimensionals.
3. A té un vector propi dret v en un valor propi r les components de la qual són totes positives.
4. Aixina mateix, A té un autovector esquerre w en autovalor r els components de la qual són tots positius.
5. Els únics autovectores els components dels quals són tots positius són els associats en el autovalor r.
6. La matriu A té exactament h (a on h és el periodo) valors propis complexos en valor absolut r. Cada u d'ells és una raïl simple del polinomi característic i és el producte de r en una h- ésima raïl de l'unitat.
7. Siga ω=2π/h. Llavors la matriu A és similar a i ^iωA , en conseqüència, l'espectre de A és invariante baix la multiplicació per i^iω (corresponent a la rotació del pla complex per l'àngul ω).
8. Si h>1 llavors existix una matriu de permutació P tal que

$PA{P}^{-1}=\left(\begin{array}{cccccc}0& A_1& 0& 0& \dots & 0\\ 0& 0& A_2& 0& \dots & 0\\ ⋮& ⋮& ⋮& ⋮& & ⋮\\ 0& 0& 0& 0& \dots & A_{h-1}\\ A_h& 0& 0& 0& \dots & 0\end{array}\right),$

a on els blocs a lo llarc de la diagonal principal són matrius quadrades zero.

9. Fòrmula de Collatz –Wielandt: per a tots els vectores no negatius no nuls x siga f(x) el valor mínim de [Ax] _i/x _i pres sobre tots aquells i tals que x_i≠0. Llavors f és un funció de valor real que el seu màxim és el valor propi de Perron-Frobenius.

10. El valor propi de Perron-Frobenius satisfà les desigualtats

$\underset{i}{\min }\sum _j{a}_{ij}\le r\le \underset{i}{\max }\sum _j{a}_{ij}.$

L'eixemple $A=\left(\begin{array}{ccc}0& 0& 1\\ 0& 0& 1\\ 1& 1& 0\end{array}\right)$ mostra que les matrius zero (quadrades) a lo llarc de la diagonal poden ser de diferents tamanys, els blocs A_j no necessiten ser quadrats i h no necessita dividir n.

Més propietats

Siga A una matriu no negativa irreducible, llavors:

1. (I+ A) ^{n −1} és una matriu positiva. (Meyer reclamació 8.3.5 p. 672 ).
2. Teorema de Wielandt.^{cita requerida}Si |B|< A, llavors ρ (B)≤ρ (A). Si es complix l'igualtat (és dir, si μ = ρ (A) i ^iφ és el valor propi de B), llavors B=i^iφ D AD ⁻¹ per a alguna matriu unitària diagonal D (és dir, els elements diagonals de D són iguals a i ^iΘ l, no diagonals són zero).
3. Si alguna potència Aq és reducible, llavors és completament reducible, és dir, per a alguna matriu de permutació P , és cert que:$P{A}^q{P}^{-1}=\left(\begin{array}{ccccc}{A}_1& 0& 0& \dots & 0\\ 0& A_2& 0& \dots & 0\\ ⋮& ⋮& ⋮& & ⋮\\ 0& 0& 0& \dots & A_d\end{array}\right)$, a on A_i són matrius irreducibles que tenen el mateix valor propi màxim. El número d'estes matrius d és el màxim comú divisor de q i h, a on h és el periodo de A.
4. Si c (x)=xⁿ+c_k1 x ^n-k ₁ + c _k 2 x _n-k 2 + ... + c _ks x _n-k s és el polinomi característic d'en el que solament s'enumeren els térmens distints de zero, llavors el periodo de A és igual al màxim comú divisor de k ₁, k ₂ , ..., k _s.

1. Promijos Cesàro:$\underset{k\to \mathrm{\infty }}{\lim }1/k\sum _{i=0,\mathrm{...},k}{A}^i/r^i=(v{w}^T),$ a on els vectores propis esquerre i dret para A estan normalisats de modo que w ^T v= 1. Ademés, la matriu vw^T és la proyecció espectral corresponent ar, la proyecció de Perron.
2. Siga r el valor propi de Perron-Frobenius, llavors la matriu adjunta para (r-A) és positiva.
3. Si A té a lo manco un element diagonal distint de zero, llavors A és primitiu.
4. Si 0 ≤ A < B, llavors r _A ≤ r _B. Per una atra part, si B és irreducible, llavors la desigualtat és estricta: r _A <r _B.

Una matriu A és primitiva sempre que no siga negativa i A ^m siga positiva per a alguns m, i per lo tant A ^k siga positiva per a tot k ≥ m. Per a verificar la primitividad, es necessita un llímit de cuán gran pot ser el mínim de tal m, depenent del tamany de A:

Si A és una matriu primitiva no negativa de tamany n, llavors A^{n2 − 2n + 2} és positiva. Ademés, est és el millor resultat possible, ya que per a la matriu M següent, la potència M ^k no és positiva per a cada k < n² − 2n + 2, ya que (M^{n2 − 2n+1})₁₁ = 0.

$M=\left(\begin{array}{cccccc}0& 1& 0& 0& \cdots & 0\\ 0& 0& 1& 0& \cdots & 0\\ 0& 0& 0& 1& \cdots & 0\\ ⋮& ⋮& ⋮& ⋮& & ⋮\\ 0& 0& 0& 0& \cdots & 1\\ 1& 1& 0& 0& \cdots & 0\end{array}\right)$

Aplicacions

S'han escrit numerosos llibres sobre el tema de les matrius no negatives, i la teoria de Perron-Frobenius és invariablement una característica central. Els següents eixemples que es donen a continuació solament mostren la superfície del seu vast domini d'aplicació.

Matrius no negatives

La teorema de Perron-Frobenius no s'aplica directament a matrius no negatives. No obstant, qualsevol matriu quadrada reducible A pot escriure's en forma de bloc triangular superior (coneguda com la forma normal d'una matriu reducible).

PAP⁻¹ = $\left(\begin{array}{ccccc}{B}_1& *& *& \cdots & *\\ 0& B_2& *& \cdots & *\\ ⋮& ⋮& ⋮& & ⋮\\ 0& 0& 0& \cdots & *\\ 0& 0& 0& \cdots & B_h\end{array}\right)$

a on P és una matriu de permutació i cada B _i és una matriu quadrada que és irreducible o zero. Ara be, si A no és negatiu, també ho és cada bloc de PAP ⁻¹, ademés, l'espectre d'és solament l'unió dels espectres de B _i.

També es pot estudiar la invertibilidad de A. l'inversa de PAP ^-1 (si existix) deu tindre blocs diagonals de la forma B _i ^-1 aixina que si qualsevol B _i no és invertible llavors tampoc és PAP ^-1 o A. Pel contrari, siga D la matriu diagonal de blocs corresponent a PAP ⁻¹, en atres paraules, PAP ⁻¹ en els asteriscs en zero. Si cada B _i és invertible, llavors també ho és D i D ⁻¹ (PAP ⁻¹) és igual a l'identitat més una matriu nilpotent. Pero tal matriu és sempre invertible (si N ^k=0 l'invers d'1-N és 1+N+N² + ... + N ^{k −1}) per lo que PAP ⁻¹ i A sò abdós invertibles.

Per tant, moltes de les propietats espectrals de A poden deduir-se aplicant la teorema al B _i irreducible. Per eixemple, la raïl de Perron és el màxim de ρ (B _i). Si ben encara hi haurà vectores propis en components no negatius, és molt possible que cap d'estos siga positiu.

Matrius estocàstiques

Una matriu estocàstica de files (columnes) és una matriu quadrada, cada una de les files de la qual (columnes) consta d'número real no negatius que la seua suma és l'unitat. El teorema no es pot aplicar directament a tals matrius perque no necessiten ser irreductibles.

Si A és estocàstic per files, llavors el vector de columna en cada entrada 1 és un vector propi corresponent al valor propi 1, que també és ρ (A) segons l'observació anterior. Pot ser que no siga l'únic valor propi en el círcul unitari: i l'espai propi associat pot ser multidimensional. Si A és estocàstic per files i irreductible, llavors la proyecció de Perron també és estocàstica per files i totes les seues files són iguals.

Teoria de grafos algebraics

La teorema té un us particular en la teoria de grafos algebraics . La "gràfica subjacent" d'una matriu n- quadrada no negativa és la gràfica en vèrtiços numerats 1, ..., ny arc ij si i solament si A _ij ≠ 0. Si la gràfica subjacent de dita matriu està fortament conectada, llavors la matriu és irreducible i, per tant, s'aplica la teorema. En particular, la matriu de adyacencia d'un gràfic fortament conectat és irreducible.

Cadenes finitas de Markov

La teorema té una interpretació natural en la teoria de les cadenes de Markov finitas (a on és l'equivalent teòric de matrius de la convergència d'una cadena de Markov finita irreductible a la seua distribució estacionaria, formulada en térmens de la matriu de transició de la cadena.

Operadors compactes

Artícul principal → Teorema de Kerin-Rutman.

De manera més general, es pot estendre al cas dels operadors compactes no negatius, que, en molts sentits, s'assemblen a les matrius de dimensió finita. Estos s'estudien comunament en física, baixe el nom d'operadors de transferència, o en ocasions operadors de Ruelle-Perron-Frobenius (despuix de David Ruelle). En este cas, el valor propi principal correspon a l'equilibri termodinàmic d'un sistema dinàmic, i els valors propis menors als modos de desintegració d'un sistema que no està en equilibri. Per lo tant, la teoria oferix una manera de descobrir la flecha del temps en lo que d'un atre modo semblarien ser processos dinàmics determinista i reversibles, quan s'examina des del punt de vista d'topología de conjunt de punts.