Gráfico matricial e irreductibilidad

Question

¿Cómo puedo probar que si $A \in\mathbb C^{n \times n}$ es una matriz, entonces es irreducible si y sólo si su gráfico asociado (definido como en Gráfico de una matriz ) está fuertemente conectada?

Actualización :

Viendo que nadie respondió por más de una semana, traté de hacerlo por mí mismo.

1. Lo primero que hice fue tratar de mostrar que la permutación de columnas o filas no cambiaba la fuerte conexión del gráfico. No lo logré, y de hecho demostré lo contrario. En el camino, sin embargo, me las arreglé para mostrar que la transposición no lo hace. El argumento es que la transposición afecta al gráfico en el sentido de que invierte todas las flechas, pero si hay un bucle a través de todos los nodos, entonces invertir las flechas significa que lo atraviesas al revés, de modo que sigue estando ahí, y el gráfico permanece fuertemente conectado, y si no lo hay, bueno, la transposición no puede hacer que aparezca uno, ya que de lo contrario transponerlo de nuevo lo haría desaparecer, lo cual hemos demostrado que es imposible. Este resultado puede no ser útil, pero ya que lo he hecho pensé que podría escribirlo.

2. Luego traté de pensar en lo que la permeación de filas y columnas hace al gráfico. ¿Por qué eso? Recordemos la noción de matriz irreducible:

   Una matriz $A \in\mathbb {C}^{n \times n}$ se dice que es reducible si existe una matriz de permutación $ \Pi $ para el cual $ \Pi\cdot A \cdot > \Pi ^T$ es un bloque de matriz triangular superior, es decir, tiene un bloque de ceros en la esquina inferior izquierda.

   Así que si esta operación no altera la fuerte conexión del gráfico, entonces puedo trabajar en la matriz reducida para mostrar que su gráfico no está fuertemente conectado y probar una implicación. Ahora bien, tales multiplicaciones como en la definición de una matriz reducible, con $ \Pi $ una matriz que cambia de línea $i$ con línea $j$ - ¿qué le hacen al gráfico? Intercambiar las líneas hace que todas las flechas que salen de $i$ salir de $j$ y viceversa; cambiar las columnas hace lo mismo con las flechas que dejan $i$ (o $j$ ). Así que imagina que tenemos un bucle. Digamos que comienza desde un nodo que no sea $i$ y $j$ . En cierto punto llega, digamos, $i$ . Antes de eso, todo no ha cambiado. Cuando el bucle original alcanza $i$ el nuevo bucle alcanzará $j$ y salir de él al mismo nodo que salió de $i$ a antes de la permutación, si ese nodo no estaba $j$ en cuyo caso irá a $i$ . Cuando el bucle original entra $j$ el nuevo bucle entra $i$ y lo mismo que antes. Así que básicamente el resultado es que $i$ y $j$ intercambio de nombres, y el bucle es el mismo que antes de tener en cuenta el intercambio de nombres. Así que este tipo de operaciones no altera la fuerte conexión del gráfico.

3. Supongamos que $A$ es lo siguiente: $$A= \left ( \begin {array}{c|c} \Huge {A_{11}} & \Huge {A_{12}} \\\hline \Huge {0} & \Huge {A_{22}} \end {array} \right ).$$ Supongamos que el $ \Huge {0}$ es $m \times m$ con $m \geq\frac {n}{2}$ . Entonces tenemos $m$ nodos que no están conectados con otros $m$ nodos, saliendo. Pero no tenemos $2m$ nodos, o tienen exactamente tantos, así que esos $m$ los nodos están cortados de todos los demás $n-m$ saliendo. Así que supongamos que hay un bucle. Si comienza en uno de los $m$ nodos, nunca puede llegar al otro $n-m$ y si comienza en uno de esos, puede llegar a la $m$ nodos pero nunca regresan, así que tal vez tenemos un camino a través de todos los nodos, pero no puede ser un bucle, es decir, un camino cerrado. Así que el gráfico no está fuertemente conectado.

4. Ahora bien, la definición no dice nada sobre el tamaño de esos bloques, así que el problema que todavía tengo es que si $m< \frac {n}{2}$ el argumento anterior falla porque tenemos al menos un nodo además del $m$ y los otros nodos $m$ nodos que no pueden ser alcanzados desde el primer $m$ y ese nodo podría ser el eslabón perdido. Por supuesto, cuando dije "no puede ser alcanzado" hasta ahora, quise decir "ser alcanzado" directamente ", es decir, no pasar por otros nodos.

5. Por supuesto, si se concluye lo anterior, he demostrado que la reductibilidad implica una no fuerte conexión del gráfico, de modo que un gráfico fuertemente conectado implica irreductibilidad. Pero lo contrario, ni siquiera lo he intentado.

Así que las preguntas son: ¿cómo termino lo anterior en los puntos 3-4 y cómo pruebo lo contrario? O tal vez me falta algo en la definición, en cuyo caso, ¿qué es?

Actualización 2: Creo que yo soy que le falte algo, como un $3 \times3 $ matriz con un 0 en la esquina inferior izquierda y ningún otro cero hace tienen un gráfico fuertemente conectado, ya que la única flecha que falta es $3 \to1 $ pero tenemos el bucle $1 \to3\to2\to1 $ . Entonces, ¿cuándo se puede reducir una matriz?

Actualización 3: Navegando por la web, he encontrado algunas cosas. Me encontré primero con este enlace . Ahora bien, si esa es la definición de matriz reducible, entonces o bien entiendo mal la definición de la forma triangular del bloque, o el si y sólo si no se mantiene, ya que una matriz con un bloque cuadrado de ceros de abajo a la izquierda definitivamente no satisfacen la condición de conjunto desarticulado pero definitivamente hace satisfacen la condición de permutación, sin ninguna permutación. Tal vez la primera condición es equivalente a la conexión no fuerte del gráfico. Sí, porque en ese caso hay $ \mu $ nodos desde los que no se puede llegar a los restantes $ \nu $ así que el gráfico no está fuertemente conectado. Así que al menos esa condición implica la no fuerte conexión del gráfico. Lo contrario parece un poco más complicado. Buscando esa definición, me encontré con este enlace . Note que ninguna matriz allí tiene un solitario cero de esquina (que estaría arriba a la derecha ya que el enlace trata de más bajo matrices triangulares), y todas ellas satisfacen la condición de conjunto desarticulado en el enlace anterior. Entonces, ¿cuál es la definición de matriz triangular en bloque? Si es que debe haber bloques cuadrados cuya diagonal coincida con parte de la diagonal de la matriz original y debajo de ellos sólo debe haber ceros, entonces he terminado, ya que el "si" y "sólo si" en el enlace anterior es válido, por lo que la reductibilidad implica una conexión no fuerte del gráfico, y ¡vaya!, aún no he terminado, todavía necesito lo contrario, así que ¿puede alguien finalmente venir a ayudarme en que ? Y si no lo es, entonces qué la señal acústica es y como hago para que esto maldita ¿Pruebas?

Answer 1

En primer lugar, permítanme recordar la definición que me han dado en Uni de matriz reducible:

Una matriz $A \in\mathbb {C}^{n \times n}$ es reducible si existe una matriz de permutación $ \Pi $ de tal manera que $ \Pi\cdot A \cdot\Pi ^T$ está en forma de triángulo superior de bloque. En otras palabras, si se puede colocar en esa forma mediante la permutación simultánea de filas y columnas, para utilizar la fraseología de Wolfram.

Sin embargo, el Wolframio ( Compare aquí ) tiene una opinión diferente. La definición que se da allí es:

Una matriz es reducible si hay dos conjuntos de índices desarticulados $I,J$ con $|I|= \mu $ , $|J|= \nu $ , $ \mu + \nu =n$ de tal manera que por cada $(i,j) \in I \times J$ tenemos $a_{ij}=0$ .

O la misma cosa redactada de forma diferente. Wolfram entonces establece la equivalencia de estas definiciones y la equivalencia de la Condición de Conjunto de Índices Desconectados (la condición en la definición de Wolfram, de aquí en adelante DISC) con el opuesto del gráfico conectado fuerte (de aquí en adelante SCG). Mi definición de matriz reducible, es decir, la Condición de Permutación Triangular Superior, se denominará en adelante UTPC, y sus opuestos como n-SCG, n-UTPC, n-DISC, con n para no . Ahora un problema que tenía era la definición del bloque UT, que definí como:

Una matriz es el bloque UT si tiene un bloque de ceros en la esquina inferior izquierda y bloques no cero en otra parte.

Con tal definición, una matriz completa con un cero solitario en la esquina inferior izquierda sería el bloqueo de UT, pero por supuesto no satisfaría al DISC, así que tuve que revisar mi definición. Llegué a pensar que podría serlo:

Una matriz es el bloque UT si tiene bloques no nulos cuyas diagonales coinciden con trozos de la diagonal de la matriz y lo cubren todo, y debajo de esos bloques sólo hay ceros.

Intentaré añadir una imagen para representar esto visualmente. Ahora mismo no tengo tiempo, espero no olvidarme de esto. Asumiendo que esta es la definición, es bastante evidente que la forma de bloque UT implica el DISCO, y viceversa. Así que si pruebo que las permutaciones como en el UTPC no alteran la satisfacción del DISC, entonces he probado que el DISC y el UTPC son equivalentes, como afirma Wolfram. Este será el primer paso. Posteriormente, tendré que probar la equivalencia del DISC y el SCG. Entonces, por la transitividad de la equivalencia, habré respondido a mi pregunta y probado este teorema.

Ahora, ¿qué pasa cuando aplico una permutación simultánea de filas y columnas? Limitémonos al simple caso de que dos filas y las columnas correspondientes se intercambien, como cualquier matriz $ \Pi $ puede escribirse como el producto de tales matrices de permutación simples ("elementales"), y la transposición es el producto de las transposiciones en orden inverso, por lo que aplicar la matriz de productos es como aplicar las "elementales" una tras otra, y si no se altera el DISC, entonces muchas posteriores claramente no lo harán. Lo que sucede es básicamente un cambio de nombres en los índices. Supongamos que intercambiamos $i,j$ de tal manera que ninguno de los dos está en $I$ . Entonces con los mismos índices satisfago la condición, ya que $a_{ki}=a_{kj}=0$ para todos $k \in I$ implica que después de intercambiar las columnas sigue funcionando y $a_{ik}$ y $a_{jk}$ que no nos importa desde que $i,j \not\in I$ . En cualquier caso $a_{ik}=a_{jk}=0$ para todos $k \in J$ se mantiene después del intercambio de filas y columnas, así que si $i,j \in I$ el DISCO permanece sin cambios. Si $i \in I$ y $j \in J$ entonces para $ \Pi\cdot A \cdot\Pi $ tendremos $i \in J$ y $j \in I$ . Eso es porque antes del intercambio, teníamos $a_{ik}=0$ para todos $k \in J$ , $j$ siendo incluido, y $a_{kj}=0$ para todos $k \in I$ , $i$ incluido en él; el intercambio de las columnas hace $a_{jk}=0$ para todos $k \in J$ . Entonces intercambiar las columnas significa que el cero en el lugar $a_{ij}$ traídos por la fila que se intercambia en el lugar $a_{jj}$ llegar al lugar $a_{ji}$ . Así que si nos movemos $j$ a $I$ el DISCO está satisfecho si y sólo si podemos probar $i$ puede ser colocado en $J$ . Pero entonces el intercambio de columnas asegura que, por la misma línea de pensamiento que este de la fila de intercambio de $j$ moviéndose a $I$ . Así que la prueba está concluida.

Probar la equivalencia de DISC y n-SCG parece más fácil que probar el UTPC $ \iff $ n-SCG, por lo que elegí este camino. Supongamos que tenemos DISC. Entonces tenemos $ \mu $ nodos asociados con los índices en $I$ de los cuales ninguno de los restantes $ \nu $ nodos asociados con los índices en $J$ puede ser alcanzado. Entonces es definitivamente imposible trazar un bucle a través de todos los nodos del gráfico, ya que a lo sumo se puede esperar conectar todos los $ \mu $ y $ \nu $ nodos por separado, y uno de los $ \nu $ a uno de los nodos de $ \mu $ pero no para cerrar el bucle yendo "desde $ \mu $ a $ \nu $ ".

Lo contrario es un poco más difícil. Lo he probado en casos especiales, y luego asumí que la misma línea de pensamiento puede ser usada para cualquier tamaño, pero la prueba es de todos modos larga y muy poco elegante, por lo que cualquier sugerencia de una prueba más elegante es muy bienvenida. En lugar de probar que n-SCG implica DISC, intenté probar que n-DISC implica SCG, porque probar el primero no parecía llevarme a ninguna parte, mientras que el segundo me dio algo que parecía estar bien para cualquier caso. Empecemos con $n=2$ . Entonces tenemos un $2 \times2 $ matriz y 2 nodos. Tomemos uno. No se puede separar del otro, de lo contrario tendríamos el DISCO. Así que desde este nodo, sea $A$ podemos llegar al otro, ya sea $B$ . El mismo argumento sobre $B$ demuestra que podemos alcanzar $A$ de $B$ y por lo tanto el gráfico es SC. Sigamos con $n=3$ . Empezamos en un nodo, ya sea $A$ . A partir de él, como se ha dicho antes, podemos llegar al menos a otro nodo, ya sea $B$ . De $B$ podemos llegar al menos a otro nodo. Ahora uno está tentado de decir que es el último nodo, $C$ pero por supuesto que no. Así que tenemos que casos: o bien $A \to B \to C$ o $A \leftrightarrow B$ . En el primer caso, de $C$ podemos alcanzar al menos un nodo. Si es $A$ hemos concluido. Si es así $B$ es decir. $A \to B \leftrightarrow C$ entonces de cualquiera de los dos $B$ o $C$ podemos alcanzar $A$ de lo contrario el DISC es violado por $B,C$ opuesto a $A$ . Si $A \to B \leftrightarrow C \to A$ hemos concluido, y si $A \leftrightarrow B \leftrightarrow C$ también hemos concluido. Sin embargo, todavía tenemos el último caso: $A \leftrightarrow B$ . Por supuesto, desde uno de esos debemos llegar a $C$ . Así que $A \leftrightarrow B \to C$ o $C \leftarrow A \leftrightarrow B$ . En el primer caso, de todos modos tenemos $A \to B \to C$ y hemos demostrado antes que este caso lleva a una conclusión positiva. En este último caso, de $C$ podemos llegar a cualquiera de los dos $B$ o $A$ de lo contrario violamos el supuesto DISC. Si $C \to B$ Entonces $A \to C \to B \to A$ lo que concluye la prueba. Si $C \to A$ Entonces $C \leftrightarrow A \leftrightarrow B$ que también concluye la prueba. Lo intenté por $n=4$ pero se aburrió en el proceso, concluyó un caso positivo y dejó muchos casos sin investigar. Una prueba así es muy larga, aburrida y poco elegante, y suena también muy nerd, por todos los casos que considera, especialmente para $n$ creciendo. Me pregunto cómo crece el número de casos con $n$ . Tal vez exponencialmente o factorialmente. De 2 a 3 hemos visto un cambio enorme. En cualquier caso, espero que exista una prueba más elegante y que alguien la conozca y la publique aquí como segunda respuesta. Si eso no sucede, aislaré esta parte y haré otra pregunta, y enlazaré esa pregunta en una segunda respuesta aquí. Esperaré como máximo 12 días antes de hacerlo. Por supuesto, marcando que como un duplicado cuando he tenido que responder este sonaría totalmente absurdo :). De todos modos parece razonable asumir que las pruebas dadas están libres de errores y que esta última prueba, con todas sus malas cualidades, puede extenderse, con mucha paciencia, a dimensiones mayores. Me pregunto si es posible probarlo por inducción en $n$ . Lo haré. no Piensa en ello, ya que he pensado demasiado en este problema, ya que era un teorema dado en el cálculo numérico sin demostración, no se me pedirá su prueba en un examen, y esto definitivamente basta para obtener un punto extra si soy lo suficientemente bueno para que me hagan la pregunta "30L", y además tengo muchas otras pruebas y ejercicios de los que preocuparme. Así que mi escrito aquí está concluido, salvo quizás por la otra pregunta vinculada a esta en una posible segunda respuesta, si me veo obligado a hacer tal pregunta.

Answer 2

Como esperaba, nadie ha respondido aquí. Así que aquí está la segunda respuesta, y el enlace que, con suerte, terminará finalmente con todo este lío: Demostrar que la irreductibilidad de una matriz implica una fuerte conexión del gráfico .