Qué condiciones de la matriz $A$ tal que existe un $k$ tal que $A^k$ es una matriz estrictamente positiva

Question

Tienes la matriz a de tamaño $n×n$ .

Matriz $A$ cumple las dos condiciones siguientes:

1. para cualquier número $i,j, a_{ij}\geq0$

2. Matriz $b$ es estrictamente positivo, si para cualquier número $i,j$ $(1\leqi,j\leqn)$ la desigualdad $b_{ij}>0$ se mantiene.

¿Cuál es la condición para que exista un $k$ tal que $A^k$ es una matriz estrictamente positiva?

Tiene algo que ver con la alcanzabilidad de los elementos, pero no veo cómo y por qué se considera esto.

Answer 1

Sólo la primera es una condición para $A$ La segunda frase es una definición.

Asignar un gráfico dirigido $D$ a $A$ de la siguiente manera. Los vértices son $\{1,2,\ldots,n\}$ . Hay una egda dirigida desde $i$ a $j$ si $a_{ij}>0$ .

Tenga en cuenta que el $ij$ -entrada de $A^k$ es positivo si existe un paseo de longitud $k$ de $i$ a $j$ en el dígrafo asignado $D$ . Así que el requisito de que $A^k$ sea positivo para algunos $k\in \mathbb N$ se traduce en la siguiente propiedad combinatoria: existe un $k\in \mathbb N$ tal que existe un paseo de longitud $k$ entre cualquier par (ordenado) de vértices en $D$ . Así que, obviamente, el gráfico $D$ tiene que estar fuertemente conectado, pero eso no es suficiente.

Consideremos el ciclo 3 orientado: $1 \rightarrow 2 \rightarrow 3\rightarrow 1$ : entonces, partiendo de 1, sólo se reintroduce 1 en cada paso cuyo residuo módulo 3 sea 0, sólo se introduce 2 en cada paso cuyo residuo módulo 3 sea 1, y sólo se introduce 3 en cada paso cuyo residuo módulo 3 sea 2. Por tanto, no hay un $k$ que resuelve los tres a la vez. Esto sugiere la idea de aperiodicidad. El periodo de un vértice en un dígrafo es el máximo común divisor de todos los enteros positivos que se dan como longitud de un paseo cerrado que empieza y termina en ese vértice. Por ejemplo, en el ciclo orientado de 3, todos los vértices tienen periodo 3, y eso es un claro obstáculo.

No es difícil demostrar que en un grafo fuertemente conectado, todos los vértices tienen el mismo período. Claramente, si este período común no es 1, entonces la condición que se investiga falla. Es fácil demostrar que si el período común es 1, entonces la condición se cumple.

En resumen, la condición equivalente es la siguiente: el dígrafo asignado $D$ está fuertemente conectado y es aperiódico (es decir, el período común de los vértices es 1).