Hispanopedia Wiki
Articulo de referencia

Matriz unimodular

En matemáticas , una matriz unimodular M es una matriz cuadrada de enteros con determinante +1 o −1. Equivalentemente, es una matriz de enteros invertible sobre los enteros : ex...

Hispanopedia WikiContenido en espanolLectura gratuita

En matemáticas , una matriz unimodular M es una matriz cuadrada de enteros con determinante +1 o −1. Equivalentemente, es una matriz de enteros invertible sobre los enteros : existe una matriz de enteros N que es su inversa (estas son equivalentes bajo la regla de Cramer ). Por lo tanto, toda ecuación Mx = b , donde M y b tienen componentes enteras y M es unimodular, tiene una solución entera. Las matrices unimodulares n × n forman un grupo llamado grupo lineal general n × n sobreZ{\displaystyle \mathbb {Z} }, que se denotaGLnorte⁡(Z){\displaystyle \operatorname {GL} _ {n}(\mathbb {Z} )}.

Ejemplos de matrices unimodulares

Las matrices unimodulares forman un subgrupo del grupo lineal general bajo la multiplicación de matrices , es decir, las siguientes matrices son unimodulares:

Otros ejemplos incluyen:

Unimodularidad total

Una matriz totalmente unimodular [ 1 ] (matriz TU) es una matriz para la cual cada submatriz cuadrada tiene determinante 0, +1 o −1 . Una matriz totalmente unimodular no tiene por qué ser cuadrada. De la definición se deduce que cualquier submatriz de una matriz totalmente unimodular es también totalmente unimodular (TU). Además, se deduce que cualquier matriz TU tiene únicamente entradas 0, +1 o −1 . Lo contrario no es cierto; es decir, una matriz con solo entradas 0, +1 o −1 no es necesariamente unimodular. Una matriz es TU si y solo si su transpuesta es TU.

Las matrices totalmente unimodulares son extremadamente importantes en la combinatoria poliédrica y la optimización combinatoria , ya que proporcionan una forma rápida de verificar que un programa lineal es integral (tiene un óptimo integral, cuando existe alguno). Específicamente, si A es TU y b es integral, entonces los programas lineales de formas como{mindo⊤incógnita∣Aincógnita≥b,incógnita≥0}{\displaystyle \{\min c^{\top }x\mid Ax\geq b,x\geq 0\}}o{máximodo⊤incógnita∣Aincógnita≤b}{\displaystyle \{\max c^{\top }x\mid Ax\leq b\}}tienen óptimos integrales, para cualquier c . Por lo tanto, si A es totalmente unimodular y b es integral, cada punto extremo de la región factible (por ejemplo,{incógnita∣Aincógnita≥b}{\displaystyle \{x\mid Ax\geq b\}}) es integral y, por lo tanto, la región factible es un poliedro integral .

Matrices comunes totalmente unimodulares

1. La matriz de incidencia no orientada de un grafo bipartito , que es la matriz de coeficientes para el emparejamiento bipartito , es totalmente unimodular (TU). (La matriz de incidencia no orientada de un grafo no bipartito no es TU). De forma más general, en el apéndice de un artículo de Heller y Tompkins, [ 2 ] AJ Hoffman y D. Gale demuestran lo siguiente. SeaA{\displaystyle A}Sea una matriz m x n cuyas filas se pueden particionar en dos conjuntos disjuntos.B{\displaystyle B}y do{\displaystyle C}Entonces, las siguientes cuatro condiciones en conjunto son suficientes para que A sea totalmente unimodular:

  • Cada entrada enA{\displaystyle A}es 0, +1 o −1;
  • Cada columna deA{\displaystyle A}contiene como máximo dos entradas distintas de cero (es decir, +1 o −1);
  • Si hay dos entradas distintas de cero en una columna deA{\displaystyle A}tienen el mismo signo, entonces la fila de uno está enB{\displaystyle B}y el otro endo{\displaystyle C};
  • Si hay dos entradas distintas de cero en una columna deA{\displaystyle A}tienen signos opuestos, entonces las filas de ambos están enB{\displaystyle B}o ambos endo{\displaystyle C}.

Posteriormente se comprendió que estas condiciones definen una matriz de incidencia de un grafo con signos equilibrado ; por lo tanto, este ejemplo indica que la matriz de incidencia de un grafo con signos es totalmente unimodular si el grafo con signos está equilibrado. Lo contrario es válido para grafos con signos sin aristas intermedias (esto generaliza la propiedad de la matriz de incidencia no orientada de un grafo). [ 3 ]

2. Las restricciones de los problemas de flujo máximo y flujo de costo mínimo generan una matriz de coeficientes con estas propiedades (y con C vacía ). Por lo tanto, estos problemas de flujo en red con capacidades enteras limitadas tienen un valor óptimo entero. Cabe destacar que esto no se aplica a los problemas de flujo de múltiples productos , en los que es posible obtener un valor óptimo fraccional incluso con capacidades enteras limitadas.

3. La propiedad de los unos consecutivos: si A es (o puede permutarse en) una matriz 0-1 en la que para cada fila, los 1 aparecen consecutivamente, entonces A es TU. (Lo mismo se aplica a las columnas, ya que la transpuesta de una matriz TU también es TU). [ 4 ]

4. Toda matriz de red es TU. Las filas de una matriz de red corresponden a un árbol T = ( V , R ) , cada uno de cuyos arcos tiene una orientación arbitraria (no es necesario que exista un vértice raíz r tal que el árbol esté "enraizado en r " o "saliendo de r "). Las columnas corresponden a otro conjunto C de arcos en el mismo conjunto de vértices V. Para calcular la entrada en la fila R y la columna C = st , observe el camino P de s a t en T ; entonces la entrada es:

  • +1 si el arco R aparece hacia adelante en P ,
  • −1 si el arco R aparece al revés en P ,
  • 0 si el arco R no aparece en P.

Véase más información en Schrijver (2003).

5. Ghouila-Houri demostró que una matriz es TU si y solo si para cada subconjunto R de filas, existe una asignacións:R→±1{\displaystyle s:R\to \pm 1}de signos a filas de modo que la suma con signo∑r∈Rs(r)r{\displaystyle \sum _{r\in R}s(r)r}(que es un vector fila del mismo ancho que la matriz) tiene todas sus entradas en{0,±1}{\displaystyle \{0,\pm 1\}}(es decir, la submatriz de filas tiene una discrepancia como máximo de uno). Esta y otras caracterizaciones del tipo "si y solo si" se demuestran en Schrijver (1998).

6. Hoffman y Kruskal [ 5 ] demostraron el siguiente teorema. Supongamos queGRAMO{\displaystyle G}es un grafo dirigido sin 2-diciclos,PAG{\displaystyle P}es el conjunto de todos los dipaths enGRAMO{\displaystyle G}, yA{\displaystyle A}es la matriz de incidencia 0-1 deV(GRAMO){\displaystyle V(G)}versusPAG{\displaystyle P}. EntoncesA{\displaystyle A}es totalmente unimodular si y solo si todo ciclo simple arbitrariamente orientado enGRAMO{\displaystyle G}Consiste en arcos alternos hacia adelante y hacia atrás.

7. Supongamos que una matriz tiene 0-(±{\displaystyle \pm }1) entradas y en cada columna, las entradas son no decrecientes de arriba a abajo (por lo que todos los −1 están arriba, luego los 0, luego los 1 están abajo). Fujishige demostró [ 6 ] que la matriz es TU si y solo si cada submatriz de 2x2 tiene determinante en0,±1{\displaystyle 0,\pm 1}.

8. Seymour (1980) [ 7 ] demostró una caracterización completa de todas las matrices TU, que aquí describimos solo de manera informal. El teorema de Seymour establece que una matriz es TU si y solo si es una combinación natural determinada de algunas matrices de red y algunas copias de una matriz TU particular de 5x5.

Ejemplos concretos

1. La siguiente matriz es totalmente unimodular:

A=[−1−1000+1+10−1−1000+1+10−10000+1+1−1].{\displaystyle A=\left[{\begin{array}{rrrrrr}-1&-1&0&0&0&+1\\+1&0&-1&-1&0&0\\0&+1&+1&0&-1&0\\0&0&0&+1&+1&-1\end{array}}\right].}

Esta matriz surge como la matriz de coeficientes de las restricciones en la formulación de programación lineal del problema de flujo máximo en la siguiente red:

2. Cualquier matriz de la forma

A=[⋮⋮⋯+1⋯+1⋯⋮⋮⋯+1⋯−1⋯⋮⋮].{\displaystyle A=\left[{\begin{array}{ccccc}&\vdots &&\vdots \\\dotsb &+1&\dotsb &+1&\dotsb \\&\vdots &&\vdots \\\dotsb &+1&\dotsb &-1&\dotsb \\&\vdots &&\vdots \end{array}}\right].}

no es totalmente unimodular, ya que tiene una submatriz cuadrada de determinante  −2.

álgebra lineal abstracta

El álgebra lineal abstracta considera matrices con entradas de cualquier anillo conmutativo.R{\displaystyle R}, no limitado a los enteros. En este contexto, una matriz unimodular es aquella que es invertible sobre el anillo; equivalentemente, cuyo determinante es una unidad . Este grupo se denotaGLnorte⁡(R){\displaystyle \operatorname {GL} _{n}(R)}. [ 8 ] Un rectangulark{\displaystyle k}-por-metro{\displaystyle m}Se dice que una matriz es unimodular si se puede extender conmetro−k{\displaystyle m-k}filas enRmetro{\displaystyle R^{m}}a una matriz cuadrada unimodular. [ 9 ] [ 10 ] [ 11 ]

Sobre un cuerpo , unimodular tiene el mismo significado que no singular . Aquí, unimodular se refiere a matrices con coeficientes en algún anillo (a menudo los enteros) que son invertibles sobre ese anillo, y se usa no singular para referirse a matrices que son invertibles sobre el cuerpo.

Véase también

Notas

  1. ↑ El término fue acuñado por Claude Berge , véase Hoffman, AJ ; Kruskal, J. (2010), "Introducción a los puntos de contorno integrales de poliedros convexos ", en M. Jünger; et  al. (eds.), 50 años de programación entera, 1958-2008 , Springer-Verlag, pp . 49–50 
  2. ↑ Heller, I.; Tompkins, CB (1956), "Una extensión de un teorema de Dantzig", en Kuhn , HW; Tucker , AW (eds.), Desigualdades lineales y sistemas relacionados , Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, pp . 247–254  
  3. ↑ T. Zaslavsky (1982), "Grafos con signo", Matemáticas Aplicadas Discretas 4, págs. 401 – 406.
  4. ↑ Fulkerson, DR; Gross, OA (1965). "Matrices de incidencia y grafos de intervalos" . Pacific Journal of Mathematics . 15 (3): 835– 855. doi : 10.2140/pjm.1965.15.835 . ISSN 0030-8730 . 
  5. ↑ Hoffman, AJ; Kruskal, JB (1956), "Puntos de frontera integrales de poliedros convexos", en Kuhn , HW; Tucker , AW (eds.), Desigualdades lineales y sistemas relacionados , Annals of Mathematics Studies, vol. 38, Princeton (NJ): Princeton University Press, pp . 223–246  
  6. ↑ Fujishige, Satoru (1984), "Un sistema de desigualdades lineales con una función submodular en vectores (0, ±1)", Álgebra lineal y sus aplicaciones , 63 : 253–266 , doi : 10.1016/0024-3795(84)90147-2
  7. ↑ Seymour , PD (1980), "Descomposición de matroides regulares", Journal of Combinatorial Theory , Serie B, 28 (3): 305–359 , doi : 10.1016/0095-8956(80)90075-1
  8. ↑ Lang, Serge (2002). Álgebra (3.ª ed. revisada ). Springer. pág. 510, Sección XIII.3. ISBN   0-387-95385-X.
  9. ↑ Rosenthal, J.; Maze, G.; Wagner, U. (2011), Densidad natural de matrices enteras unimodulares rectangulares , Álgebra lineal y sus aplicaciones, vol. 434, Elsevier, pp. 1319–1324  
  10. ↑ Micheli, G.; Schnyder, R. (2016), La densidad de matrices unimodulares sobre subanillos integralmente cerrados de cuerpos de funciones , Contemporary Developments in Finite Fields and Applications, World Scientific, pp . 244–253 
  11. ↑ Guo, X.; Yang, G. (2013), La probabilidad de matrices unimodulares rectangulares sobre Fq [x] , Álgebra lineal y sus aplicaciones, Elsevier, pp. 2675– 2682 

Referencias

  • Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), "Sección 13.2", Optimización combinatoria: algoritmos y complejidad , Mineola, NY: Dover Publications, pág.  316, ISBN 978-0-486-40258-1
  • Alexander Schrijver (1998), Teoría de la programación lineal y entera . John Wiley e hijos, ISBN 0-471-98232-6(matemático)
  • Alexander Schrijver (2003), Optimización combinatoria: poliedros y eficiencia , Springer
  • Glosario de programación matemática de Harvey J. Greenberg
  • Matriz unimodular de MathWorld
  • Software para probar la unimodularidad total por M. Walter y K. Truemper