¿Cómo se demuestra que una matriz es irreducible y reducible?

Question

¿Cómo se demuestra que una matriz es irreducible y reducible? Un ejemplo también sería genial.

Sé que una matriz es reducible si y sólo si puede colocarse en forma triangular superior de bloque. ¿Cómo se encuentra la forma triangular superior en bloque?

Answer 1

Una matriz cuadrada es reducible si el grafo dirigido asociado tiene menor componentes fuertemente conectados . Así que puede utilizar un algoritmo de componentes fuertes para resolver su problema.

Answer 2

Existe otro criterio sencillo para la irreducibilidad de una matriz con entradas no negativas. Tal $n\times n$ -matriz $A$ es irreducible si y sólo si todas las entradas de $$\sum\limits_{i=0}^{n}A^i$$ son mayores que $0$ .

Como no tengo una referencia, voy a esbozar brevemente una prueba, utilizando la definición que $A$ es irreducible si para todos los índices $i,j$ hay un exponente $e_{i,j}$ , de tal manera que la entrada $[A^{e_{i,j}}]_{ij}$ es positivo (donde $[C]_{ij}$ denota la entrada en $i,j$ de una matriz $C$ ).

Dejemos que $B$ sea la matriz obtenida de $A$ sustituyendo todas las entradas no nulas por $1$ .

1. Demuestra que $A$ es irreducible si B es irreducible.

2. Demuestra que $\sum\limits_{i=0}^{n}A^i$ sólo tiene entradas positivas si esto es cierto para $\sum\limits_{i=0}^{n}B^i$ .

3. Dejemos que $G$ sea el grafo dirigido con vértices $\{1,2,\ldots,n\}$ donde hay una arista desde $i$ a $j$ si $b_{ij}>0$ . Demuestre, por inducción en $m$ que la entrada de $[B^m]_{ij}$ corresponde al número de caminos dirigidos desde $i$ a $j$ .

Según 3., para $m\in\mathbb{N}$ el número de caminos dirigidos desde $i$ a $j$ de una longitud máxima de $m$ es $\left[\sum\limits_{k=0}^mB^k\right]_{ij}$ . Ahora la afirmación se deduce de las siguientes equivalencias: $$\begin{array}{rl} &\text{$B$ is an irreducible matrix.}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$, there is a directed path in $G$ from $i$ to $j$.}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$, there is a directed path in $G$ from $i$ to $j$ of length at most $n$}\\ &\text{(note that this graph has exactly $n$ vertices).}\\ \Leftrightarrow&\text{For all $i,j\in\{1,2,\ldots,n\}$ holds $\left[\sum\limits_{k=0}^{n}B^k\right]_{ij}>0$.} \end{array}$$

Answer 3

Un teorema puede ayudarte:

Dejemos que $A M_n$ . Los siguientes son equivalentes:
(a) A es irreducible.
(b) $(I + |A|)^{n-1} > 0$ .
(c) $(I + M(A))^{n1} > 0$ .
(d) $\Gamma(A)$ está fuertemente conectada.

Es el Teorema 6.2.24 en Análisis matricial, 2ª edición . Ve a comprobarlo si necesitas una prueba completa.

Answer 4

Dejemos que $A=[a_{i,j}]\in M_n(\mathbb{R})$ y $|A|=[|a_{i,j}|]$ . $A$ es irreducible IFF $|A|$ también lo es. Entonces podemos suponer que el $a_{i,j}$ son $\geq 0$ . Tenemos una mirada a la complejidad del problema: "decidir si $A$ es irreducible o no".

Por supuesto, no buscamos una permutación de los vectores base que triangularice $A$ (la complejidad es $O(n!)$ ).

Podemos utilizar la prueba (cf. Renko Usami) $(I+A)^{n-1}>0$ . Sin embargo, la complejidad es $O(n^3\log(n))$ .

Lo mejor es utilizar el "algoritmo de componentes fuertes" (cf. usuario1551). Su complejidad es $O(n)$ (esto es extraordinariamente rápido, incluso para un $10^6\times 10^6$ matriz).

Answer 5

El mejor lugar para buscar es este enlace wiki . Para añadir a la otra respuesta, otra condición equivalente es que para cada índice $[i,j]$ debería haber un $m$ tal que $(A^m)_{ij}>0$ que se satisface naturalmente si las entradas de la matriz son todas positivas. Si es no negativo, hay que comprobar otras cosas.