Vector propio de una matriz estructurada dispersa correspondiente al valor propio 1

Question

Tengo una matriz con el siguiente patrón de dispersión:

$M = \begin{bmatrix} \ast &\ast &0 &0 &0 &0 &0 &0\\ 0 & 0 &\ast &\ast &0 &0 &0 &0 \\ 0 &0 &0 &0 &\ast &\ast &0 &0 \\ 0 &0 &0 &0 &0 &0 &\ast &\ast \\ \ast &\ast &0 &0 &0 &0 &0 &0\\ 0 & 0 &\ast &\ast &0 &0 &0 &0 \\ 0 &0 &0 &0 &\ast &\ast &0 &0 \\ 0 &0 &0 &0 &0 &0 &\ast &\ast \end{bmatrix}$

donde $\ast$ indica no-cero entradas. Es un derecho estocástico de la matriz (la matriz de transición de una cadena de Markov; cada fila sumas a uno), así que sé que tiene un autovector izquierdo con autovalor 1, es decir, algunos $x$ para:

$xM = x$

Puedo utilizar la energía de la iteración para encontrar el autovector $x$. Me pregunto si hay una manera más rápida de conseguir la solución para esta estructurado de la matriz. (También, hay un nombre para este patrón de dispersión?)

EDIT: la matriz podría ser más grande: el tamaño de las $2^n \times 2^n$.

EDIT2: tenga en cuenta que $M$ no es de rango completo.

Answer 1

Desea que el espacio nulo. Puesto que usted ya sabe que el autovalor es $1$, ver el $M-I$ . El uso de la factorización QR:

\begin{align} M-I &=QR \\ \Rightarrow Q^\top (M-I) &= R \end{align}

Desde $M - I$ es singular, habrá al menos una fila $v$ $Q^\top$ que da $$v (M - I) = \mathbf{0} \Rightarrow vM = v$$

Si hay sólo una fila $v$, tiene su respuesta. De lo contrario, su respuesta es sólo reducido a un subespacio.

Creo que usted puede tener querían evitar una factorización desde su matriz es dispersa. Usted ha mencionado el poder de la iteración y me perdí que tal una iteración puede ser ventajoso con su matriz dispersa.

Si primero reordenar las filas de $M-I$ como se deduce, entonces la dispersión de la matriz puede ayudar a que el algoritmo QR (que utiliza las rotaciones de Givens para tomar ventaja de la dispersión) Encontrar la fila de permutación $P$ que da $D_2$ un bloque diagonal (ha $2 \times 2$ bloques):

$$PM = D_2 = \pmatrix{* & * & 0 & 0 & \cdots \\* & * & 0 & 0& \cdots \\0 & 0 & * & *& \cdots \\0 & 0 & * & *& \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots }$$

Una vez más, mira a $M - I$, en su ejemplo, esto sería como $$P(M-I) = D_2 - P = \begin{bmatrix} \ast - 1 &\ast &0 &0 &0 &0 &0 &0\\ \ast &\ast &0 &0 &-1 &0 &0 &0\\ 0 & -1 &\ast &\ast &0 &0 &0 &0 \\ 0 & 0 &\ast &\ast &0 &-1 &0 &0 \\ 0 &0 &-1 &0 &\ast &\ast &0 &0 \\ 0 &0 &0 &0 &\ast &\ast &-1 &0 \\ 0 &0 &0 &-1 &0 &0 &\ast &\ast \\ 0 &0 &0 &0 &0 &0 &\ast &\ast - 1 \end{bmatrix}$$ El orden en que se da cierre a la forma triangular que la factorización QR va a terminar. Esto puede dar la velocidad de los cálculos, pero no estoy seguro de que la memoria de almacenamiento puede ser optimizado en gran medida. No se ve como algunos de la dispersión sería permanecen a lo largo de las rotaciones de Givens, aunque.