Teorema de Perron-Frobenius

En álgebra lineal, el teorema de Perron-Frobenius, probado por Oskar Perron (1907) y Georg Frobenius (1912), afirma que una matriz cuadrada real con entradas positivas tiene un valor propio real único más grande y que el vector propio correspondiente puede elegirse para tener estrictamente componentes positivos, y también afirma una declaración similar para ciertas clases de matrices no negativas. Este teorema tiene importantes aplicaciones a la teoría de la probabilidad (ergodicidad de las cadenas de Markov); a la teoría de sistemas dinámicos (subdesplazamientos de tipo finito); a la economía (teorema de Okishio,[1] condición de Hawkins-Simon[2]); a la demografía (modelo de distribución de edad de la población de Leslie );[3] a las redes sociales (proceso de aprendizaje DeGroot), a los buscadores de Internet e incluso al ranking de equipos de fútbol.[4] El primero en discutir el orden de los jugadores dentro de los torneos usando vectores propios de Perron-Frobenius es Edmund Landau .[5][6]

Declaración

Deje que positivo y no negativo describan respectivamente matrices con números reales exclusivamente positivos como elementos y matrices con números reales exclusivamente no negativos como elementos. Los valores propios de una matriz cuadrada real A son números complejos que componen el espectro de la matriz. La tasa de crecimiento exponencial de la matriz potencia Ak cuando k → ∞ está controlada por el valor propio de A con el valor absoluto más grande (módulo). El teorema de Perron-Frobenius describe las propiedades del valor propio principal y de los vectores propios correspondientes cuando A es una matriz cuadrada real no negativa. Los primeros resultados se debieron a Oskar Perron (1907) y se referían a matrices positivas. Posteriormente, Georg Frobenius (1912) encontró su extensión a ciertas clases de matrices no negativas.[7]

Matrices positivas

Sea una matriz positiva de : × . Entonces las siguientes proposiciones son válidas.

  1. Hay un número real positivo r , llamado raíz de Perron o autovalor de Perron-Frobenius (también llamado autovalor principal o autovalor dominante ), de manera que r es un autovalor de A y cualquier otro autovalor λ (posiblemente complejo ) en valor absoluto es estrictamente menor que r , | λ | < r. Por tanto, el radio espectral AT es igual a r. Si los coeficientes de la matriz son algebraicos, esto implica que el valor propio es un número de Perron.
  2. El valor propio de Perron-Frobenius es simple: r es una raíz del polinomio característico de A. En consecuencia, el espacio propio asociado a r es unidimensional. (Lo mismo es cierto para el espacio propio izquierdo, es decir, el espacio propio para AT , la transposición de A).
  3. Existe un vector propio v=(v1,...,vn) de A con valor propio r tal que todos los componentes de v son positivos: A v = rv, v i> 0 para 1 ≤ i ≤ n . (Respectivamente, existe un vector propio izquierdo positivo w: w T A = rw T, w i > 0.) Se conoce en la literatura bajo muchas variaciones como el vector de Perron , vector propio de Perron, Vector propio de Perron-Frobenius , vector propio principal o vector propio dominante.
  4. No hay otros autovectores positivos (además no negativos) excepto los múltiplos positivos de v (respectivamente, autovectores izquierdos excepto w), es decir, todos los demás autovectores deben tener al menos un componente negativo o no real.
  5. , donde los vectores propios izquierdo y derecho para A están normalizados de modo que w T v = 1. Además, la matriz vw T es la proyección sobre el espacio propio correspondiente a r . Esta proyección se llama proyección Perron.
  6. Fórmula de CollatzWielandt : para todos los vectores x no negativos no nulos, sea f ( x ) el valor mínimo de [Ax] i/xi tomado sobre todos aquellos i tales que x i 0. Entonces f es un valor real función valorada cuyo máximo sobre todos los vectores x no negativos distintos de ceroes el valor propio de Perron-Frobenius.
  7. Una fórmula Collatz-Wielandt "Mín-máx" toma una forma similar a la anterior: para todos los vectores estrictamente positivos x , sea g (x) el valor máximo de [Ax] i/x i tomado sobre i . Entonces g es una función con valor real cuyo mínimo sobre todos los vectores estrictamente positivos x es el valor propio de Perron-Frobenius.
  8. Birkhoff - Varga fórmula:Sean x e y vectores estrictamente positivos. Entonces:[8]
  9. Donsker, Varadhan y S. Friedland fórmulan: Que p sea un vector de probabilidad y x un vector estrictamente positivo. Entonces:[9][10]
  10. Fórmula de Fiedler, [11]
  11. El valor propio de Perron-Frobenius satisface las desigualdades.

Todas estas propiedades se extienden más allá de las matrices estrictamente positivas a las matrices primitivas (ver más abajo). Los hechos 1-7 se pueden encontrar en Meyer, capítulo 8,[12] afirmaciones 8.2.11-15, página 667, y ejercicios 8.2.5, 7,9, páginas 668-669.

Los vectores propios izquierdo y derecho w y v a veces se normalizaron de manera que la suma de sus componentes es igual a 1; en este caso, a veces se denominan autovectores estocásticos . A menudo se normalizan de modo que el vector propio derecho v suma uno, mientras que .

Matrices no negativas

Existe una extensión para matrices con entradas no negativas. Dado que cualquier matriz no negativa puede obtenerse como límite de matrices positivas, se obtiene la existencia de un vector propio con componentes no negativos; el valor propio correspondiente será no negativo y mayor o igual , en valor absoluto, a todos los demás valores propios.[13][14] Sin embargo, para el ejemplo , el valor propio máximo r = 1 tiene el mismo valor absoluto que el otro valor propio −1; mientras que para, el valor propio máximo es r = 0, que no es una raíz simple del polinomio característico, y el vector propio correspondiente (1, 0) no es estrictamente positivo.

Sin embargo, Frobenius encontró una subclase especial de matrices no negativas, matrices irreducibles, para las que es posible una generalización no trivial. Para tal matriz, aunque los valores propios que alcanzan el valor absoluto máximo pueden no ser únicos, su estructura está bajo control: tienen la forma , donde r es realmente estrictamente positivo, y es un valor propio real estrictamente positivo, y rangos sobre las raíces h- ésimas complejas de 1 para algún entero positivo h llamado período de la matriz. El vector propio correspondiente a r tiene componentes estrictamente positivos (en contraste con el caso general de matrices no negativas, donde los componentes son solo no negativos). Además, todos estos valores propios son raíces simples del polinomio característico. A continuación se describen otras propiedades.

Clasificación de matrices

Sea A una matriz cuadrada (no necesariamente positiva o incluso real). La matriz A es irreducible si se cumple alguna de las siguientes propiedades equivalentes.

Definición 1: A no tiene subespacios de coordenadas invariantes no triviales. Aquí, un subespacio vectorial de coordenadas no trivial significa un subespacio lineal abarcado por cualquier subconjunto adecuado de vectores de base estándar de . Más explícitamente, para cualquier subespacio lineal generado por vectores de base estándar ei1 , ..., eik, 0 < k < n, su imagen bajo la acción de A no está contenida en el mismo subespacio vectorial.

De manera equivalente, la representación de grupo de en dada por no tiene subespacios de coordenadas invariantes no triviales. (En comparación, esto sería una representación irreductible si no hubiera subespacios invariantes no triviales en absoluto, no solo considerando los subespacios de coordenadas).

Definición 2: A no se puede conjugar en forma triangular superior de bloque mediante una matriz de permutación P:

donde E y G son matrices cuadradas no triviales (es decir, de tamaño mayor que cero).

Si A no es negativo, se aplica otra definición:

Definición 3: Uno puede asociarse con una matriz A un cierto grafo dirigido G A. Tiene exactamente n vértices, donde n es el tamaño de A , y hay una arista desde el vértice i al vértice j precisamente cuando A ij > 0. Entonces la matriz A es irreducible si y solo si su grafo asociado G A está fuertemente conectado .

Una matriz es reducible si no es irreducible.

Una matriz A es primitiva si no es negativa y su potencia m es positiva para algún número natural m (es decir, todas las entradas de A m son positivas).

Sea A no negativo. Fije un índice i y defina el período del índice i como el máximo común divisor de todos los números naturales m tal que (A m) ii > 0. Cuando A es irreducible, el período de cada índice es el mismo y se llama período de A . De hecho, cuando A es irreductible, el período se puede definir como el máximo común divisor de las longitudes de los caminos cerrados dirigidos en G A (ver Cocinas [15] página 16). El período también se denomina índice de imprimitividad ([12] Meyer página 674) o el orden de ciclicidad. Si el período es 1, A es aperiódico. Se puede demostrar que las matrices primitivas son las mismas que las matrices irreductibles aperiódicas no negativas.

Todos los enunciados del teorema de Perron-Frobenius para matrices positivas siguen siendo verdaderos para matrices primitivas. Las mismas declaraciones también son válidas para una matriz irreductible no negativa, excepto que puede poseer varios valores propios cuyo valor absoluto es igual a su radio espectral, por lo que las declaraciones deben modificarse en consecuencia. De hecho, el número de esos valores propios es igual al período.

Los resultados de las matrices no negativas fueron obtenidos por primera vez por Frobenius en 1912.

Teorema de Perron-Frobenius para matrices no negativas irreducibles

Deje que A sea un irreducible no negativo n × n matriz con período h y espectral radio ρ (A) = r . Entonces las siguientes declaraciones son válidas.

  1. El número r es un número real positivo y es un valor propio de la matriz A, llamado valor propio de Perron-Frobenius.
  2. El valor propio r de Perron-Frobenius es simple. Ambos espacios propios, derecho e izquierdo, asociados con r son unidimensionales.
  3. A tiene un vector propio derecho v con un valor propio r cuyas componentes son todas positivas.
  4. Asimismo, A tiene un autovector izquierdo w con autovalor r cuyos componentes son todos positivos.
  5. Los únicos autovectores cuyos componentes son todos positivos son los asociados con el autovalor r.
  6. La matriz A tiene exactamente h (donde h es el período) valores propios complejos con valor absoluto r. Cada uno de ellos es una raíz simple del polinomio característico y es el producto de r con una h- ésima raíz de la unidad.
  7. Sea ω=2π/h. Entonces la matriz A es similar a e A , en consecuencia, el espectro de A es invariante bajo la multiplicación por e (correspondiente a la rotación del plano complejo por el ángulo ω).
  8. Si h>1 entonces existe una matriz de permutación P tal que
donde los bloques a lo largo de la diagonal principal son matrices cuadradas cero.
9. Fórmula de Collatz –Wielandt: para todos los vectores no negativos no nulos x sea f(x) el valor mínimo de [Ax] i/x i tomado sobre todos aquellos i tales que xi≠0. Entonces f es un función de valor real cuyo máximo es el valor propio de Perron-Frobenius.
10. El valor propio de Perron-Frobenius satisface las desigualdades

El ejemplo muestra que las matrices cero (cuadradas) a lo largo de la diagonal pueden ser de diferentes tamaños, los bloques Aj no necesitan ser cuadrados y h no necesita dividir n.

Más propiedades

Sea A una matriz no negativa irreducible, entonces:

  1. (I+ A) n −1 es una matriz positiva. (Meyer reclamación [12] 8.3.5 p. 672 ).
  2. Teorema de Wielandt.[cita requerida]Si |B|< A, entonces ρ (B)≤ρ (A). Si se cumple la igualdad (es decir, si μ = ρ (A) e es el valor propio de B), entonces B=e D AD −1 para alguna matriz unitaria diagonal D (es decir, los elementos diagonales de D son iguales a e l, no diagonales son cero).[16]
  3. Si alguna potencia Aq es reducible, entonces es completamente reducible, es decir, para alguna matriz de permutación P , es cierto que:, donde Ai son matrices irreducibles que tienen el mismo valor propio máximo. El número de estas matrices d es el máximo común divisor de q y h, donde h es el período de A.[17]
  4. Si c (x)=xn+ck1 x n-k 1 + c k 2 x n-k 2 + ... + c ks x n-k s es el polinomio característico de A en el que solo se enumeran los términos distintos de cero, entonces el período de A es igual al máximo común divisor de k 1, k 2 , ..., k s.[18]
  5. Promedios Cesàro: donde los vectores propios izquierdo y derecho para A están normalizados de modo que w T v= 1. Además, la matriz vwT es la proyección espectral correspondiente ar, la proyección de Perron.[19]
  6. Sea r el valor propio de Perron-Frobenius, entonces la matriz adjunta para (r-A) es positiva.[20]
  7. Si A tiene al menos un elemento diagonal distinto de cero, entonces A es primitivo.[21]
  8. Si 0 ≤ A < B, entonces r Ar B. Por otra parte, si B es irreducible, entonces la desigualdad es estricta: r A <r B.

Una matriz A es primitiva siempre que no sea negativa y A m sea positiva para algunos m, y por lo tanto A k sea positiva para todo km. Para verificar la primitividad, se necesita un límite de cuán grande puede ser el mínimo de tal m, dependiendo del tamaño de A:

  • Si A es una matriz primitiva no negativa de tamaño n, entonces An2  2n + 2 es positiva. Además, este es el mejor resultado posible, ya que para la matriz M siguiente, la potencia M k no es positiva para cada k < n2  2n + 2, ya que (Mn2  2n+1)11 = 0.[18]

Aplicaciones

Se han escrito numerosos libros sobre el tema de las matrices no negativas, y la teoría de Perron-Frobenius es invariablemente una característica central. Los siguientes ejemplos que se dan a continuación solo muestran la superficie de su vasto dominio de aplicación.

Matrices no negativas

El teorema de Perron-Frobenius no se aplica directamente a matrices no negativas. Sin embargo, cualquier matriz cuadrada reducible A puede escribirse en forma de bloque triangular superior (conocida como la forma normal de una matriz reducible).[22]

PAP−1 =

donde P es una matriz de permutación y cada B i es una matriz cuadrada que es irreducible o cero. Ahora bien, si A no es negativo, también lo es cada bloque de PAP −1, además, el espectro de A es solo la unión de los espectros de B i.

También se puede estudiar la invertibilidad de A. La inversa de PAP -1 (si existe) debe tener bloques diagonales de la forma B i -1 así que si cualquier B i no es invertible entonces tampoco es PAP -1 o A. Por el contrario, sea D la matriz diagonal de bloques correspondiente a PAP −1, en otras palabras, PAP −1 con los asteriscos en cero. Si cada B i es invertible, entonces también lo es D y D −1 (PAP −1) es igual a la identidad más una matriz nilpotente. Pero tal matriz es siempre invertible (si N k=0 el inverso de 1-N es 1+N+N2 + ... + N k −1) por lo que PAP −1 y A son ambos invertibles.

Por tanto, muchas de las propiedades espectrales de A pueden deducirse aplicando el teorema al B i irreducible. Por ejemplo, la raíz de Perron es el máximo de ρ (B i). Si bien todavía habrá vectores propios con componentes no negativos, es muy posible que ninguno de estos sea positivo.

Matrices estocásticas

Una matriz estocástica de filas (columnas) es una matriz cuadrada, cada una de cuyas filas (columnas) consta de números reales no negativos cuya suma es la unidad. El teorema no se puede aplicar directamente a tales matrices porque no necesitan ser irreductibles.

Si A es estocástico por filas, entonces el vector de columna con cada entrada 1 es un vector propio correspondiente al valor propio 1, que también es ρ (A) según la observación anterior. Puede que no sea el único valor propio en el círculo unitario: y el espacio propio asociado puede ser multidimensional. Si A es estocástico por filas e irreductible, entonces la proyección de Perron también es estocástica por filas y todas sus filas son iguales.

Teoría de grafos algebraicos

El teorema tiene un uso particular en la teoría de grafos algebraicos . La "gráfica subyacente" de una matriz n- cuadrada no negativa es la gráfica con vértices numerados 1, ..., ny arc ij si y solo si A ij ≠ 0. Si la gráfica subyacente de dicha matriz está fuertemente conectada, entonces la matriz es irreducible y, por tanto, se aplica el teorema. En particular, la matriz de adyacencia de un gráfico fuertemente conectado es irreducible.[23][24]

Cadenas finitas de Markov

El teorema tiene una interpretación natural en la teoría de las cadenas de Markov finitas (donde es el equivalente teórico de matrices de la convergencia de una cadena de Markov finita irreductible a su distribución estacionaria, formulada en términos de la matriz de transición de la cadena.[25]

Operadores compactos

De manera más general, se puede extender al caso de los operadores compactos no negativos, que, en muchos sentidos, se parecen a las matrices de dimensión finita. Estos se estudian comúnmente en física, bajo el nombre de operadores de transferencia, o en ocasiones operadores de Ruelle-Perron-Frobenius (después de David Ruelle). En este caso, el valor propio principal corresponde al equilibrio termodinámico de un sistema dinámico, y los valores propios menores a los modos de desintegración de un sistema que no está en equilibrio. Por lo tanto, la teoría ofrece una manera de descubrir la flecha del tiempo en lo que de otro modo parecerían ser procesos dinámicos deterministas y reversibles, cuando se examina desde el punto de vista de topología de conjunto de puntos.[26]

Métodos de prueba

Un hilo común en muchas demostraciones es el teorema del punto fijo de Brouwer. Otro método popular es el de Wielandt (1950). Usó la fórmula de Collatz- Wielandt descrita anteriormente para ampliar y aclarar el trabajo de Frobenius.[27] Otra prueba se basa en la teoría espectral[28] de la que se toman prestados parte de los argumentos.

La raíz de Perron es un valor propio estrictamente máximo para matrices positivas (y primitivas)

Si A es una matriz positiva (o más generalmente primitiva), entonces existe un valor propio positivo real r ( valor propio de Perron-Frobenius o raíz de Perron), que es estrictamente mayor en valor absoluto que todos los demás valores propios, por lo que r es el radio espectral de Una.

Esta declaración no se mantiene para matrices irreducibles no negativos generales, que tienen h valores propios con el mismo valor propio absoluta como r, donde h es el período de A.

Prueba de matrices positivas

Sea A una matriz positiva, suponga que su radio espectral ρ (A)=1 (de lo contrario, considere A/ρ (A)). Por lo tanto, existe un valor propio λ en el círculo unitario, y todos los demás valores propios son menores o iguales a 1 en valor absoluto. Suponga que otro valor propio λ ≠ 1 también cae en el círculo unitario. Entonces existe un entero positivo m tal que A m es una matriz positiva y la parte real de λ m es negativa. Sea εI la mitad de la entrada diagonal más pequeña de A my establezca T=A m-εI, que es otra matriz positiva. Además, si Ax= Λx entonces A mx = λ m x así λ m-ε es un valor propio de T. Debido a la elección de m, este punto se encuentra fuera del disco unitario, por lo tanto, ρ (T)> 1. Por otro lado, todas las entradas en T son positivas y menores o iguales a las de A m, por lo que según la fórmula de Gelfand ρ (T)≤''ρ (A m)≤ ρ (A) m=1. Esta contradicción significa que λ=1 y no puede haber otros valores propios en el círculo unitario.

Absolutamente los mismos argumentos se pueden aplicar al caso de matrices primitivas; solo necesitamos mencionar el siguiente lema simple, que aclara las propiedades de las matrices primitivas.

Lema

Dado un número no negativo A, asumen que m existe, de manera que un m es positivo, entonces Am+1,Am+2, Am+3,... son todos positivos.

Am+1=AAm, por lo que puede tener un elemento cero solo si alguna fila de A es completamente cero, pero en este caso la misma fila de A m será cero.

Aplicando los mismos argumentos anteriores para matrices primitivas, demuestre la afirmación principal.

Método de potencia y el par propio positivo

Para un positivo (o más generalmente irreducible no negativo) de la matriz A la dominante vector propio es real y estrictamente positivo (para no negativo A respectivamente no negativo.)

Esto se puede establecer utilizando el método de la potencia, que establece que para una matriz A suficientemente genérica (en el sentido siguiente), la secuencia de vectores bk+1 = Abk / | Abk | converge al vector propio con el valor propio máximo. (El vector inicial b 0 se puede elegir arbitrariamente, excepto para algún conjunto de medidas de cero). Comenzar con un vector no negativo b 0 produce la secuencia de vectores no negativos b k. Por tanto, el vector limitante tampoco es negativo. Por el método de la potencia, este vector limitante es el autovector dominante para A, lo que demuestra la afirmación. El valor propio correspondiente no es negativo.

La prueba requiere dos argumentos adicionales. Primero, el método de potencia converge para matrices que no tienen varios valores propios del mismo valor absoluto que el máximo. El argumento de la sección anterior lo garantiza.

En segundo lugar, asegurar la positividad estricta de todos los componentes del vector propio para el caso de matrices irreducibles. Esto se deriva del siguiente hecho, que es de interés independiente:

Lema: dado un positivo (o más generalmente irreducible no negativo) de la matriz A y v como cualquier vector propio no negativo para A, entonces es necesariamente estrictamente positivo y el correspondiente valor propio también es estrictamente positivo.

Prueba. Una de las definiciones de irreductibilidad para matrices no negativas es que para todos los índices i, j existe M, de modo que (A m) ij es estrictamente positivo. Dado un vector propio v no negativo, y que al menos uno de sus componentes dice que j -th es estrictamente positivo, el valor propio correspondiente es estrictamente positivo, de hecho, dado n tal que (A n) ii>0, por lo tanto:rnvi = Anvi ≥ (An)iivi >0. Por consiguiente r es estrictamente positivo. El vector propio es positividad estricta. Entonces dado m, tal que (Am)ij >0, de manera que: rmvj = (Amv)j ≥ (Am)ijvi >0, en consecuencia vj es estrictamente positivo, es decir, el vector propio es estrictamente positivo.

Multiplicidad uno

En esta sección se demuestra que el valor propio de Perron-Frobenius es una raíz simple del polinomio característico de la matriz. Por lo tanto, el eigespacio asociado al eigenvalor de Perron-Frobenius r es unidimensional. Los argumentos aquí son cercanos a los de Meyer.[29]

Dado un vector propio estrictamente positivo v correspondiente a r y otro vector propio w con el mismo valor propio. (Los vectores v y w pueden elegirse como reales, porque A y r son ambos reales, por lo que el espacio nulo de A-r tiene una base formada por vectores reales). Suponiendo que al menos una de las componentes de w sea positiva (en caso contrario, multiplicar w por -1). Dado el máximo posible α tal que u=v- α w es no negativo, entonces uno de los componentes de u es cero, en caso contrario α no es máximo. El vector u es un vector propio. Es no negativo, por lo que por el lema descrito en el sección anterior la no negatividad implica positividad estricta para cualquier vector propio. Por otro lado, como en el caso anterior, al menos una componente de u es cero. La contradicción implica que w no existe.

Caso: No hay celdas de Jordan correspondientes al valor propio de Perron-Frobenius r y todos los demás valores propios que tienen el mismo valor absoluto.

Si existe una celda de Jordan, entonces la Norma de infinito (A/r)k tiende a infinito para k → ∞, pero eso contradice la existencia del vector propio positivo.

Dado r = 1, o A/r. Dejando que v sea un eigenvector estrictamente positivo de Perron-Frobenius, por lo que Av=v, entonces:

Así que Ak está acotado para todo k. Esto da otra prueba de que no hay valores propios que tengan mayor valor absoluto que el de Perron-Frobenius. También contradice la existencia de la célula de Jordan para cualquier valor propio que tenga valor absoluto igual a 1 (en particular para el de Perron-Frobenius), porque la existencia de la célula de Jordan implica que Ak no está acotado. Para una matriz de dos por dos:

por lo que Jk = |k + λ| (para |λ| = 1), por lo que tiende a infinito cuando k lo hace. Como Jk = C-1 AkC, entonces AkJk/ (C-1 C ), por lo que también tiende a infinito. La contradicción resultante implica que no hay células de Jordan para los correspondientes valores propios.

La combinación de las dos afirmaciones anteriores revela que el valor propio de Perron-Frobenius r es una raíz simple del polinomio característico. En el caso de las matrices no primitivas, existen otros valores propios que tienen el mismo valor absoluto que r. La misma afirmación es válida para ellos, pero requiere más trabajo.

No hay otros eigenvectores no negativos

Dada una matriz positiva (o más generalmente irreducible no negativa) A, el eigenvector de Perron-Frobenius es el único (hasta la multiplicación por una constante) eigenvector no negativo para A.

Otros eigenvectores deben contener componentes negativas o complejas, ya que los eigenvectores para diferentes valores propios son ortogonales en algún sentido, pero dos eigenvectores positivos no pueden ser ortogonales, por lo que deben corresponder al mismo valor propio, pero el espacio propio para el Perron-Frobenius es unidimensional.

Suponiendo que existe un par propio (λ, y) para A, tal que el vector y es positivo, y dado (r, x), donde x - es el vector propio izquierdo de Perron-Frobenius para A (es decir, el vector propio para AT'), entonces rxTy = (xTA) y = xT (Ay) = λxTy, también xTy > 0, entonces se tiene: r = λ. Dado que el espacio propio para el valor propio de Perron-Frobenius r es unidimensional, el vector propio no negativo y es un múltiplo del de Perron-Frobenius.[30]

Fórmula de Collatz-Wielandt

Dada una matriz positiva (o más generalmente irreducible no negativa) A, se define la función f sobre el conjunto de todos los vectores no negativos distintos de cero x tal que f(x) es el valor mínimo de [Ax]i / xi tomado sobre todos aquellos i tal que xi ≠ 0. Entonces f es una función de valor real, cuyo máximo es el valor propio de Perron-Frobenius r.

Para la demostración denotamos el máximo de f por el valor R. La prueba requiere demostrar que R = r. Insertando el vector propio de Perron-Frobenius v en f, obtenemos f(v) = r y concluimos r ≤ R. Para la desigualdad opuesta, consideramos un vector arbitrario no negativo x y dejamos que ξ=f(x). La definición de f da 0 ≤ ξx ≤ Ax (por componentes). Ahora, utilizamos el vector propio positivo derecho w para A para el valor propio de Perron-Frobenius r, entonces ξ wT x = wT ξx ≤ wT (Ax) = (wT A)x = r wT x . Por tanto, f(x) = ξ ≤ r, lo que implica R ≤ r.[31]

La proyección de Perron como límite: Ak/rk

Sea A una matriz positiva (o más generalmente, primitiva), y sea r su valor propio de Perron-Frobenius.

  1. Existe un límite Ak/rk para k → ∞, denotándolo por P.
  2. P es un proyección: P2 = P, que conmuta con A: AP = PA.
  3. La imagen de P es unidimensional y se extiende por el vector propio de Perron-Frobenius v (respectivamente para PT' - por el vector propio de Perron-Frobenius w para AT').
  4. P = vwT, donde v,w están normalizados de forma que wTv = 1.
  5. Por lo tanto P es un operador positivo.

Por lo tanto P es una proyección espectral para el valor propio de Perron-Frobenius r, y se llama la proyección de Perron. La afirmación anterior no es cierta para matrices irreducibles generales no negativas.

En realidad, las afirmaciones anteriores (excepto la afirmación 5) son válidas para cualquier matriz M tal que existe un valor propio r que es estrictamente mayor que los otros valores propios en valor absoluto y es la raíz simple del polinomio característico. (Estos requisitos son válidos para las matrices primitivas como en el caso anterior).

Dado que M es diagonalizable, M es conjugable a una matriz diagonal con valores propios r 1, ... , rn en la diagonal (denotemos r1 = r). La matriz Mk/rk será conjugada (1, (r2/r)k, ... , (rn/r)k), que tiende a (1,0,0,...,0), para k → ∞, por lo que el límite existe. El mismo método funciona para M general (sin suponer que M es diagonalizable).

Las propiedades de proyección y conmutatividad son corolarios elementales de la definición: MMk/rk = Mk/rk M ; P2 = lim M2k/r2k = P. El tercer hecho es también elemental: M(Pu) = M lim Mk/rk u = lim rMk+1/rk+1u, por lo que al tomar el límite se obtiene que M(Pu) = r(Pu), por lo que la imagen de P se encuentra en el espacio eigénico de r para M, que es unidimensional por las suposiciones.

Denotando por v, el vector propio r para M (por w para MT'). Las columnas de P son múltiplos de v, porque la imagen de P está atravesada por ella. Respectivamente, las filas de w. Así que P toma la forma (a v wT), para algún a. Por lo tanto su traza es igual a (a wT v). La traza del proyector es igual a la dimensión de su imagen. Ya se ha demostrado que no es más que unidimensional. De la definición se ve que P actúa idénticamente sobre el vector propio r para M. Así que es unidimensional. Así que elegir (wTv) = 1, implica que P = vwT.

Cualidades para el valor propio de Perron-Frobenius

Para cualquier matriz no negativa A su valor propio de Perron-Frobenius r satisface la desigualdad:

Esto no es específico de las matrices no negativas: para cualquier matriz A con un valor propio es cierto que . Esto es un corolario inmediato de la teorema del círculo de Gershgorin]]. Sin embargo otra prueba es más directa:

Cualquier Norma inducida por la matriz satisface la desigualdad para cualquier valor propio porque, si es un vector propio correspondiente, . La Norma del infinito de una matriz es el máximo de las sumas de las filas: Por lo tanto, la desigualdad deseada es exactamente aplicada a la matriz no negativa A.

Otra desigualdad es:

Este hecho es específico de las matrices no negativas; para las matrices generales no hay nada parecido. Dado que A es positiva (no sólo no negativa), entonces existe un vector propio positivo w tal que Aw = rw y la componente más pequeña de w (digamos wi') es 1. Entonces r = (Aw)i ≥ la suma de los números de la fila i de A. Así, la suma mínima de filas da una cota inferior para r y esta observación se puede extender a todas las matrices no negativas por continuidad.

Otra forma de argumentarlo es a través de la fórmula Collatz-Wielandt. Se toma el vector x = (1, 1, ..., 1) y se obtiene inmediatamente la desigualdad.

Proyección de Perron

La prueba procede ahora utilizando la descomposición espectral. El truco aquí es separar la raíz de Perron de los otros valores propios. La proyección espectral asociada a la raíz de Perron se llama proyección de Perron y goza de la siguiente propiedad:

La proyección de Perron de una matriz cuadrada irreducible no negativa es una matriz positiva.

Las conclusiones de Perron y también (1)-(5) del teorema son corolarios de este resultado. El punto clave es que una proyección positiva siempre tiene rango uno. Esto significa que si A es una matriz cuadrada irreducible no negativa, entonces las multiplicidades algebraicas y geométricas de su raíz de Perron son ambas uno. Además, si P es su proyección de Perron, entonces AP = PA = ρ(A)P, por lo que cada columna de P es un vector propio derecho positivo de A y cada fila es un vector propio izquierdo positivo. Además, si Ax = λx entonces PAx = λPx = ρ(A)Px que significa que Px = 0 si λ ≠ ρ(A). Así, los únicos vectores propios positivos son los asociados a ρ(A). Si A es una matriz primitiva con ρ(A) = 1 entonces puede descomponerse como P ⊕ (1 - P)A de modo que An = P + (1 - P)An. A medida que n aumenta el segundo de estos términos decae a cero dejando a P como el límite de An' a medida que n   ∞.

El método de la potencia es una forma conveniente de calcular la proyección de Perron de una matriz primitiva. Si v y w son los vectores fila y columna positivos que genera, entonces la proyección de Perron es simplemente wv / vw. Las proyecciones espectrales no están claramente bloqueadas como en la forma de Jordan. Aquí están superpuestas y cada una tiene generalmente entradas complejas que se extienden a las cuatro esquinas de la matriz cuadrada. No obstante, conservan su ortogonalidad mutua, que es lo que facilita la descomposición.

Proyección periférica

El análisis cuando A es irreducible y no negativo es muy similar. La proyección de Perron sigue siendo positiva pero ahora puede haber otros valores propios de módulo ρ(A) que anulan el uso del método de la potencia y evitan que las potencias de (1 - P)A decaigan como en el caso primitivo siempre que ρ(A) = 1. Así que consideramos la proyección periférica, que es la proyección espectral de A correspondiente a todos los valores propios que tienen módulo ρ(A). Se puede demostrar entonces que la proyección periférica de una matriz cuadrada irreducible no negativa es una matriz no negativa con diagonal positiva.

Ciclicidad

Supongamos además que ρ(A) = 1 y que A tiene h valores propios en el círculo unitario. Si P es la proyección periférica entonces la matriz R = AP = PA es no negativa e irreducible, Rh' = P, y el grupo cíclico P, R, R2, ...., Rh-1 representa los armónicos de A. La proyección espectral de A en el valor propio λ sobre el círculo unitario viene dada por la fórmula . Todas estas proyecciones (incluida la de Perron) tienen la misma diagonal positiva, y además, si se elige cualquiera de ellas y se toma el módulo de cada entrada, se obtiene invariablemente la proyección de Perron. Todavía hay que hacer un poco de trabajo de burro para establecer las propiedades cíclicas (6)-(8), pero es esencialmente una cuestión de girar la manivela. La descomposición espectral de A viene dada por A = R  (1 - P)A por lo que la diferencia entre An y Rn es An  -Rn = (1 - P)An representando los transitorios de An que eventualmente decaen a cero. P puede calcularse como el límite de Anh' a medida que n   ∞.

Contraejemplos

Las matrices L = , P = , T = , M = proporcionan ejemplos sencillos de lo que puede salir mal si no se cumplen las condiciones necesarias. Se ve fácilmente que las proyecciones de Perron y periférica de L son ambas iguales a P, por lo que cuando la matriz original es reducible las proyecciones pueden perder la no negatividad y no hay posibilidad de expresarlas como límites de sus potencias. La matriz T es un ejemplo de matriz primitiva con diagonal cero. Si la diagonal de una matriz cuadrada irreducible no negativa es distinta de cero, la matriz debe ser primitiva, pero este ejemplo demuestra que lo contrario es falso. M es un ejemplo de matriz con varios dientes espectrales perdidos. Si ω = eiπ/3 entonces ω6 = 1 y los valores propios de M son {1,ω234} por lo que ω y ω5 están ausentes.[cita requerida]

Terminología

Un problema que causa confusión es la falta de estandarización en las definiciones. Por ejemplo, algunos autores utilizan los términos estrictamente positivo y positivo para significar > 0 y ≥ 0 respectivamente. En este artículo positivo significa > 0 y no negativo significa ≥ 0. Otro aspecto controvertido es el de la descomponibilidad y la reducibilidad: irreducible es un término sobrecargado. Para evitar dudas, a veces se dice que una matriz cuadrada no nula A tal que 1 + A es primitiva es conexa. Entonces las matrices cuadradas no negativas irreducibles y las matrices conexas son sinónimos.[32]

El eigenvector no negativo se normaliza a menudo para que la suma de sus componentes sea igual a la unidad; en este caso, el eigenvector es el vector de una distribución de probabilidad y a veces se llama eigenvector estocástico.

El valor propio de Perron-Frobenius y el valor propio dominante son nombres alternativos para la raíz de Perron. Las proyecciones espectrales también se conocen como proyectores espectrales y idempotentes espectrales. El periodo se denomina a veces índice de imprimibilidad o orden de ciclicidad.

Véase también

Referencias

  1. Google's PageRank and Beyond: The Science of Search Engine Rankings. Langville & Meyer 2006. 10 de julio de 2014. ISBN 978-0691122021. Archivado desde el original el 2 de mayo de 2020. Consultado el 30 de noviembre de 2020.
  2. Perron, Oskar (2000). «Perron–Frobenius Theory of Nonnegative Matrices» (en inglés). SIAM. Archivado desde el original el 7 de marzo de 2010. Consultado el 29 de noviembre de 2020.
  3. Bowles, Samuel (1 de junio de 1981). Technical change and the profit rate: a simple proof of the Okishio theorem (Impreso) (en inglés). Oxford. pp. 183-186.
  4. Kenner, James P. (Marzo 1993). The Perron-Frobenius Theorem and the Ranking of Football Teams (Primera edición). SIAM Review. pp. 80-93. Consultado el 30 de noviembre de 2020.
  5. Technical change and the profit rate: a simple proof of the Okishio theorem. Cambridge Journal of Economics.
  6. Landau, Edmund (1915). «"Über Preisverteilung bei Spielturnieren"» (en inglés). Zeitschrift für Mathematik und Physik. Consultado el 29 de noviembre de 2020.
  7. «DEMOSTRACIÓN DEL TEOREMA DE PERRON-FROBENIUS». matematicasypoesía.com.es. Consultado el 17 de octubre de 2020.
  8. Varga, Richard S.; Birkhoff, Garett (1958). Reactor criticality and nonnegative matrices. (primera edición). Journal of the Society for Industrial and Applied Mathematics. pp. 354-377.
  9. Donsker, M. D.; Varadhan, S. S. (1975). On a variational formula for the principal eigenvalue for operators with maximum principle (primera edición). Proceedings of the National Academy of Sciences. pp. 780—783.
  10. Friedland, S. (1981). Convex spectral functions. Linear and multilinear algebra (Cuarta edición). pp. 299—316.
  11. Miroslav Fiedler, Charles R. Jhonnson; Markham, Thomas L.; Neumann, Michael (1985). «A trace inequality for M-matrices and the symmetrizability of a real matrix by a positive diagonal matrix». 1985 71: 81—94. doi:10.1016/0024-3795(85)90237-X. Consultado el 1 de diciembre de 2020.
  12. Perron, Oskar (2000). «Perron–Frobenius Theory of Nonnegative Matrices pág. 665» (en inglés). SIAM. Archivado desde el original el 7 de marzo de 2010. Consultado el 29 de noviembre de 2020.
  13. Perron, Oskar (2000). «Perron–Frobenius Theory of Nonnegative Matrices pág. 670» (en inglés). SIAM. Archivado desde el original el 7 de marzo de 2010. Consultado el 2 de diciembre de 2020.
  14. Ruvimovich Gantmakher, Feliks (195o). «The Theory of matrices cap. 8» (Ilustrada, reimpresa). The Theory of Matrices (en inglés). Chelsea Publishing Company. p. 66. ISBN 9780821813935. Consultado el 2 de diciembre de 2020.
  15. Cocinas, Bruce (6 de diciembre de 2012). Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts. Springer Science & Business Media. p. 16. ISBN 9783540627388. Consultado el 5 de diciembre de 2020.
  16. Perron, Oskar (2000). «Perron–Frobenius Theory of Nonnegative Matrices pág. 675» (en inglés). SIAM. Archivado desde el original el 7 de marzo de 2010. Consultado el 9 de diciembre de 2020.
  17. K. A, Hirsch (1959). «5» (edición ilustrada, reimpresa). The Theory of Matrices, Volumen 1 (en inglés) (Volumen 1 edición). Chelsea Publishing Company,. p. sección XIII.5 teorema 9. ISBN 9780821813935. Consultado el 9 de diciembre de 2020.
  18. Perron, Oskar (2000). «Perron–Frobenius Theory of Nonnegative Matrices pág. 679» (en inglés). SIAM. Archivado desde el original el 7 de marzo de 2010. Consultado el 29 de noviembre de 2020.
  19. Perron, Oskar (2000). «Perron–Frobenius Theory of Nonnegative Matrices pág. 677» (en inglés). SIAM. Archivado desde el original el 7 de marzo de 2010. Consultado el 29 de noviembre de 2020.
  20. K. A, Hirsch (1959). «5» (edición ilustrada, reimpresa). The Theory of Matrices, Volumen 1 (en inglés) (Volumen 1 edición). Chelsea Publishing Company,. p. sección XIII.5 página 62. ISBN 9780821813935. Consultado el 9 de diciembre de 2020.
  21. Perron, Oskar (2000). «Perron–Frobenius Theory of Nonnegative Matrices pág. 678» (en inglés). SIAM. Archivado desde el original el 7 de marzo de 2010. Consultado el 29 de noviembre de 2020.
  22. Varga, Richard S. (2002). Matrix Iterative Analysis (Segunda edición). Springer-Verlag.
  23. Brualdi, Richard A.; Ryse, Herbert J. (29 de julio de 2019). Combinatorial Matrix Theory (en inglés) (1991 edición). Cambridge:Cambridge University Perss. ISBN 978-0-521-32265-2. Consultado el 29 de diciembre de 2020.
  24. Brualdi, Richard A.; Cvetkovic, Dragos (2009). A Combinatorial Approach to Matrix Theory and Its Applications (en inglés). FL: CRC Press. ISBN 978-1-4200-8223-4.
  25. Valentina Vega, Maria; Fraiman, Ricardo (26 de abril de 2004). Cadenas de Markov de tiempo continuo y aplicaciones (pdf). colibri.udelar.edu.uy. Consultado el 29 de diciembre de 2020.
  26. Mackey, Michael C (1992). Time's Arrow: The origins of thermodynamic behaviour. (en inglés). New York: Springer-Verlag. ISBN 978-0-387-97702-7.
  27. K. A, Hirsch (1959). «5» (edición ilustrada, reimpresa). The Theory of Matrices, Volumen 1 (en inglés) (Volumen 1 edición). Chelsea Publishing Company,. p. sección XIII.5 página 54. ISBN 9780821813935. Consultado el 29 de diciembre de 2020.
  28. Roger, Smith (2006). A Spectral Theoretic Proof of Perron–Frobenius (pdf) (en inglés) 102. Mathematical Proceedings of the Royal Irish Academy. pp. 29-35. doi:10.3318/PRIA.2002.102.1.29. Consultado el 29 de diciembre de 2020.
  29. Meyer, 2000, pp. Capítulo 8 pág 665 «Copia archivada». Archivado desde el original el 7 de marzo de 2010. Consultado el 3 de julio de 2010.
  30. Meyer, 2000, pp. capítulo 8 afirmación 8.2. 10 página 666 «Copia archivada». Archivado desde el original el 7 de marzo de 2010. Consultado el 7 de marzo de 2010.
  31. Meyer, 2000, pp. capítulo 8 página 666 «Copia archivada». Archivado desde el original el 7 de marzo de 2010. Consultado el 3 de marzo de 2010.
  32. Para estudios de resultados sobre la irreducibilidad, véase Olga Taussky-Todd y Richard A. Brualdi.

Bibliografía

Documentos originales

Lecturas adicionales

  • Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, 1994, SIAM. ISBN 0-89871-321-8
  • Chris Godsil y Gordon Royle, Algebraic Graph Theory, Springer, 2001.
  • A. Graham, Nonnegative Matrices and Applicable Topics in Linear Algebra, John Wiley&Sons, New York, 1987.
  • R. A. Horn y C.R. Johnson, Matrix Analysis, Cambridge University Press, 1990.
  • Bas Lemmens y Roger Nussbaum, Nonlinear Perron-Frobenius Theory, Cambridge Tracts in Mathematics 189, Cambridge Univ. Press, 2012.
  • S. P. Meyn y R. L. Tweedie, Markov Chains and Stochastic Stability Londres: Springer-Verlag, 1993. ISBN0-387-19832-6 (2ª edición, Cambridge University Press, 2009)
  • Henryk Minc, Nonnegative matrices, John Wiley&Sons, Nueva York, 1988, ISBN 0-471-83966-3
  • Seneta, E. Matrices no negativas y cadenas de Markov. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Publicado originalmente por Allen & Unwin Ltd., Londres, 1973) ISBN 978-0-387-29765-1
  • Varga, Richard S. (2002). Matrix Iterative Analysis (segunda edición). Springer-Verlag..
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.