Matriz unimodular

Matrices enteras con determinante +1 o -1; invertibles sobre los enteros. GL_n(Z)

En matemáticas , una matriz unimodular M es una matriz entera cuadrada que tiene determinante +1 o −1. Equivalentemente, es una matriz entera que es invertible sobre los números enteros : hay una matriz entera N que es su inversa (estas son equivalentes bajo la regla de Cramer ). Por lo tanto, cada ecuación Mx = b , donde M y b tienen componentes enteros y M es unimodular, tiene una solución entera. Las matrices unimodulares n  ×  n forman un grupo llamado grupo lineal general n  ×  n sobre , 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 la 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 , cizallamiento (ambas con determinante 1) y reflexión (determinante −1).
• Matriz unimodular utilizada (posiblemente implícitamente) en la reducción reticular y en la forma normal de Hermite de las matrices.
• El producto de Kronecker de dos matrices unimodulares también es unimodular. Esto se deduce de 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 cada submatriz cuadrada no singular es unimodular. Equivalentemente, 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 solo 0, +1 o −1 entradas. Lo inverso no es cierto, es decir, una matriz con solo 0, +1 o −1 entradas 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 brindan una forma 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 (por ejemplo, ) es integral y, por lo 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 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 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 m por n cuyas filas se pueden 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 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 observó que estas condiciones definen una matriz de incidencia de un grafo con signo equilibrado ; por lo tanto, este ejemplo dice que la matriz de incidencia de un grafo con signo es totalmente unimodular si el grafo con signo está equilibrado. Lo inverso es válido para grafos con signo sin medias aristas (esto generaliza la propiedad de la matriz de incidencia no orientada de un grafo). ^[3]

2. Las restricciones de los problemas de flujo de máximo y mínimo costo dan como resultado una matriz de coeficientes con estas propiedades (y con C vacía ). Por lo tanto, dichos problemas de flujo de red con capacidades enteras acotadas tienen un valor óptimo integral. Obsérvese 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 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 tenga "raíces 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 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 .

Ver más en Schrijver (2003).

5. Ghouila-Houri demostró que una matriz es TU si y solo 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 fila tiene discrepancia como máximo una). Esta y varias otras caracterizaciones de tipo si y solo 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. Supóngase que es un grafo dirigido sin 2-diciclos, es el conjunto de todos los ditrayectos en , y es la matriz de incidencia 0-1 de frente a . Entonces es totalmente unimodular si y solo si cada ciclo simple arbitrariamente orientado en consiste en arcos hacia adelante y hacia atrás alternados. ${\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 hacia abajo (por lo que todos los −1 están arriba, luego los 0 y luego los 1 abajo). Fujishige demostró ^[6] que la matriz es TU si y solo 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 establece 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 , no limitadas a los enteros. En este contexto, una matriz unimodular es una que es invertible sobre el anillo; equivalentemente, cuyo determinante es una unidad . Este grupo se denota como . ^[8] Se dice que una matriz rectangular -por- es unimodular si se puede extender con filas en una matriz cuadrada unimodular. ^{[9] [10] [11]} ${\displaystyle R}$ ${\displaystyle \operatorname {GL} _{n}(R)}$ ${\displaystyle k}$ ${\displaystyle m}$ ${\displaystyle m-k}$ ${\displaystyle R^{m}}$

En un cuerpo , unimodular tiene el mismo significado que no singular . Unimodular se refiere aquí 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 cuerpo.

Véase también

• Matriz equilibrada
• Matroide regular
• Grupo lineal especial
• Integralidad dual total
• Forma normal de Hermite

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 polihedra convexa ", en M. Jünger; et al. (eds.), 50 años de programación entera, 1958-2008 , Springer-Verlag, págs. 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 , Anales de estudios matemáticos, vol. 38, Princeton (Nueva Jersey): Princeton University Press, págs. 247-254
3. T. Zaslavsky (1982), "Gráficos con signo", Matemáticas Aplicadas Discretas 4, págs. 401–406.
4. Fulkerson, DR; Gross, OA (1965). "Matrices de incidencia y gráficos de intervalo". Revista del Pacífico de Matemáticas . 15 (3): 835–855. ISSN  0030-8730.
5. Hoffman, AJ; Kruskal , JB (1956), "Puntos de contorno integrales de poliedros convexos", en Kuhn , HW; Tucker , AW (eds.), Desigualdades lineales y sistemas relacionados , Anales de estudios matemáticos, 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.; Maze, 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 de funciones , Desarrollos contemporáneos en campos finitos y aplicaciones, World Scientific, págs. 244-253
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, 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 & Sons, ISBN 0-471-98232-6 (matemáticas) 
• 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 de M. Walter y K. Truemper