Hispanopedia Wiki
Articulo de referencia

Matriz unimodular

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...

Hispanopedia WikiContenido en espanolLectura gratuita

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 . O {\displaystyle \mathbb {Z}} GL norte ⁡ ( O ) {\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 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 . { mín. do ⊤ incógnita ∣ A incógnita ≥ b , incógnita ≥ 0 } {\displaystyle \{\min c^{\top }x\mid Ax\geq b,x\geq 0\}} { máximo do ⊤ incógnita ∣ A incógnita ≤ b } {\displaystyle \{\max c^{\top }x\mid Ax\leq b\}} { incógnita ∣ A incógnita ≥ 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: A {\estilo de visualización A} B {\estilo de visualización B} do {\estilo de visualización C}

  • Cada entrada es 0, +1 o −1; A {\estilo de visualización A}
  • Cada columna contiene como máximo dos entradas distintas de cero (es decir, +1 o −1); A {\estilo de visualización 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 ; A {\estilo de visualización A} B {\estilo de visualización B} do {\estilo de visualización 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 . A {\estilo de visualización A} B {\estilo de visualización B} do {\estilo de visualización 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). s : R → ± 1 {\displaystyle s:R\to \pm 1} ∑ a ∈ R s ( a ) a {\displaystyle \sum_{r\in R}s(r)r} { 0 , ± 1 } {\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. GRAMO {\estilo de visualización G} PAG {\estilo de visualización P} GRAMO {\estilo de visualización G} A {\estilo de visualización A} V ( GRAMO ) {\displaystyle V(G)} PAG {\estilo de visualización P} A {\estilo de visualización A} GRAMO {\estilo de visualización 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 . ± {\estilo de visualización \pm} 0 , ± 1 {\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:

A = [ − 1 − 1 0 0 0 + 1 + 1 0 − 1 − 1 0 0 0 + 1 + 1 0 − 1 0 0 0 0 + 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}&\vpuntos &&\vpuntos \\\puntosb &+1&\puntosb &+1&\puntosb \\&\vpuntos &&\vpuntos \\\puntosb &+1&\puntosb &-1&\puntosb \\&\vpuntos &&\vpuntos \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] R {\estilo de visualización R} GL norte ⁡ ( R ) {\displaystyle \operatorname {GL} _{n}(R)} a {\estilo de visualización k} metro {\estilo de visualización m} metro − a {\estilo de visualización mk} R metro Estilo de visualización 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

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
  • 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
Obtenido de "https://es.wikipedia.org/w/index.php?title=Matriz_unimodular&oldid=1184325973"