Matriz de irreducibilidad. Grafica fuertemente conectada

Question

Tengo este teorema de la Combinatoria, la Teoría de la Matriz escrito por Richard A. Brualdi y otros.

Deje $A$ ser una matriz de orden $n$. A continuación, $A$ es irreducible si y sólo si su dígrafo $D$ está fuertemente conectado.

Sin embargo, un amigo me mostró el siguiente ejemplo

$\left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right] $ y su gráfico asociado va como sigue:

$1\to2\to3\to1$

el cual está fuertemente conectado. Sin embargo, la matriz resulta ser reducible (en particular, no puedo tener una estrictamente positivo de la matriz de energía)

Alguna idea de lo que pasa de malo aquí?

Answer 1

Deje que $$A = \left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right],$$ entonces $$ A^1 = \left[\begin{array}{ccc} 0 &1& 0\\ 0 &0 &1\\ 1 &0& 0 \end{array}\right]\quad A^2 = \left[\begin{array}{ccc} 0 &0& 1\\ 1 &0 &0\\ 0 &1& 0 \end{array}\right]\quad A^3 = \left[\begin{array}{ccc} 1 &0& 0\\ 0 &1 &0\\ 0 &0& 1 \end{array}\right], $$ así que para cada par de $\langle i,j \rangle$ hay un poder $m$ tal que $(A^m)_{i,j} > 0$ y la matriz es irreductible. Sin embargo, esto no es un mágico declaración, redactada en el gráfico de la teoría de la forma que hemos

para cada par $\langle i,j \rangle$ hay una longitud de $m$ tal que existe una trayectoria de longitud $m$ $i$ $j$

y esto es cierto sólo si el grafo es fuertemente conectados. Por otra parte, tomar un reducible matriz $B$:

$$B = \left[\begin{array}{ccc} B_1 &B_2\\ 0 &B_3 \end{array}\right]$$

y de considerar su gráfico correspondiente. Observar que no hay ningún borde de los vértices de bloque de $B_3$ a los vértices de bloque de $B_2$. En otras palabras, una vez que llegue a $B_2$, no hay manera de salir, en particular, el gráfico no puede ser fuertemente conectados.

Espero que esto ayude a $\ddot\smile$

Answer 2

Como decía correctamente la respuesta anterior, la matriz es irreducible. Quizás no haya notado que no todas las matrices irreductibles son aperiódicas. Algunos de ellos (como tu ejemplo) son cíclicos. Por favor, vea aquí para un ejemplo

Gracias.