Matriz unimodular

Matrices enteras con determinante +1 o -1; invertible sobre los números enteros. GL_n(Z)

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

Ejemplos de matrices unimodulares

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

• Matriz de identidad
• La inversa de una matriz unimodular
• El producto de dos matrices unimodulares.

Otros ejemplos incluyen:

• Matrices de Pascal
• Matrices de permutación
• las tres matrices de transformación en el árbol ternario de ternas pitagóricas primitivas
• Ciertas matrices de transformación para rotación , corte (ambas con determinante 1) y reflexión (determinante −1).
• La matriz unimodular utilizada (posiblemente implícitamente) en la reducción de celosía y en la forma normal de matrices de Hermite.
• El producto de Kronecker de dos matrices unimodulares también es unimodular. Esto se deduce ya que donde p y q son las dimensiones de A y B , respectivamente. ${\displaystyle \det(A\otimes B)=(\det A)^{q}(\det B)^{p},}$

Unimodularidad total

Una matriz totalmente unimodular ^[1] (matriz TU) es una matriz para la cual toda submatriz cuadrada no singular es unimodular. De manera equivalente, cada submatriz cuadrada tiene determinante 0, +1 o −1. Una matriz totalmente unimodular no necesita ser cuadrada en sí misma. De la definición se deduce que cualquier submatriz de una matriz totalmente unimodular es en sí misma totalmente unimodular (TU). Además, se deduce que cualquier matriz TU tiene sólo 0, +1 o −1 entradas. Lo contrario no es cierto, es decir, una matriz con sólo 0, +1 o −1 entradas no es necesariamente unimodular. Una matriz es TU si y sólo si su transpuesta es TU.

Las matrices totalmente unimodulares son extremadamente importantes en combinatoria poliédrica y optimización combinatoria, ya que brindan una manera rápida de verificar que un programa lineal es integral (tiene un óptimo integral, cuando existe algún óptimo). Específicamente, si A es TU y b es integral, entonces los programas lineales de formas como o 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 (p. ej. ) es integral y, por tanto, la región factible es un poliedro integral . ${\displaystyle \{\min c^{\top }x\mid Ax\geq b,x\geq 0\}}$ ${\displaystyle \{\max c^{\top }x\mid Ax\leq b\}}$ ${\displaystyle \{x\mid Ax\geq b\}}$

Matrices comunes totalmente unimodulares

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

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

Más tarde se comprendió que estas condiciones definen una matriz de incidencia de un gráfico con signo equilibrado ; por tanto, este ejemplo dice que la matriz de incidencia de un gráfico con signo es totalmente unimodular si el gráfico con signo está equilibrado. Lo contrario es válido para gráficos con signo sin medias aristas (esto generaliza la propiedad de la matriz de incidencia no orientada de un gráfico). ^[3]

2. Las restricciones de los problemas de flujo máximo y flujo de costo mínimo producen una matriz de coeficientes con estas propiedades (y con C vacía ). Por tanto, estos problemas de flujo de red con capacidades enteras acotadas tienen un valor óptimo integral. Tenga en cuenta que esto no se aplica a los problemas de flujo de múltiples productos , en los que es posible tener un valor óptimo fraccionario incluso con capacidades enteras acotadas.

3. La propiedad de los consecutivos: si A es (o puede permutarse en) una matriz 0-1 en la que, para cada fila, los unos 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. Cada 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 " fuera 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 la ruta s -to- t P 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 .

Ver más en Schrijver (2003).

5. Ghouila-Houri demostró que una matriz es TU si para cada subconjunto R de filas, hay una asignación de signos a las filas de modo que la suma con signo (que es un vector de fila del mismo ancho que la matriz) tenga todas sus entradas en (es decir, la submatriz de filas tiene una discrepancia como máximo de uno). Esta y varias otras caracterizaciones si y sólo si se prueban en Schrijver (1998). ${\displaystyle s:R\to \pm 1}$ ${\displaystyle \sum _{r\in R}s(r)r}$ ${\displaystyle \{0,\pm 1\}}$

6. Hoffman y Kruskal ^[5] demostraron el siguiente teorema. Supongamos que es un gráfico dirigido sin 2 diciclos, es el conjunto de todos los dipaths en y es la matriz de incidencia 0-1 de versus . Entonces es totalmente unimodular si y sólo si cada ciclo simple orientado arbitrariamente consiste en alternar arcos hacia adelante y hacia atrás. ${\displaystyle G}$ ${\displaystyle P}$ ${\displaystyle G}$ ${\displaystyle A}$ ${\displaystyle V(G)}$ ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle G}$

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

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

Ejemplos concretos

1. La siguiente matriz es totalmente unimodular:

${\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

${\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 , sin limitarse a los números enteros. En este contexto, una matriz unimodular es aquella que es invertible sobre el anillo; de manera equivalente, cuyo determinante es una unidad . Este grupo se denota . ^[8] Una matriz rectangular por matriz se dice que es unimodular si se puede extender con filas hasta formar una matriz cuadrada unimodular. ^{[9] [10] [11]} ${\displaystyle R}$ ${\displaystyle \operatorname {GL} _{n}(R)}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle m-k}$ ${\displaystyle R^{m}}$

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

Ver también

• Matriz equilibrada
• matroide normal
• Grupo lineal especial
• Integralidad dual total
• Forma normal de Hermita

Notas

1. El término fue acuñado por Claude Berge , véase Hoffman , AJ; Kruskal , J. (2010), "Introducción a los puntos límite integrales de poliedros convexos ", en M. Jünger; et al. (eds.), 50 años de programación entera, 1958-2008 , Springer-Verlag, págs.
2. Heller, yo; 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 (Nueva Jersey): Princeton University Press, págs. 247–254
3. T. Zaslavsky (1982), "Gráficos firmados", Matemáticas aplicadas discretas 4, págs.
4. Fulkerson, DR; Bruto, OA (1965). "Matrices de incidencia y gráficas de intervalos". Revista Pacífico de Matemáticas . 15 (3): 835–855. ISSN  0030-8730.
5. Hoffman, AJ; Kruskal , JB (1956), "Puntos de límite integrales de poliedros convexos", en Kuhn , HW; Tucker , AW (eds.), Desigualdades lineales y sistemas relacionados , Annals of Mathematics Studies, vol. 38, Princeton (Nueva Jersey): Princeton University Press, págs. 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 (rev.3ª ed.). Saltador. pag. 510, Sección XIII.3. ISBN 0-387-95385-X.
9. Rosenthal, J.; Laberinto, G.; Wagner, U. (2011), Densidad natural de matrices enteras unimodulares rectangulares , Álgebra lineal y sus aplicaciones, vol. 434, Elsevier, págs. 1319-1324
10. Micheli, G.; Schnyder, R. (2016), La densidad de matrices unimodulares sobre subanillos integralmente cerrados de campos funcionales , Desarrollos contemporáneos en campos y aplicaciones finitos, World Scientific, págs.
11. Guo, X.; Yang, G. (2013), La probabilidad de matrices unimodulares rectangulares sobre Fq [x] , Álgebra lineal y sus aplicaciones, Elsevier, págs. 2675–2682

Referencias

• Papadimitriou, Christos H.; Steiglitz, Kenneth (1998), "Sección 13.2", Optimización combinatoria: algoritmos y complejidad, Mineola, Nueva York: Dover Publications, p. 316, ISBN 978-0-486-40258-1
• Alexander Schrijver (1998), Teoría de la programación lineal y entera . John Wiley & Sons, ISBN 0-471-98232-6 (matemático) 
• Alexander Schrijver (2003), Optimización combinatoria: poliedros y eficiencia , Springer

enlaces externos

• 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