Matriz doblemente estocástica

Una matriz cuadrada

En matemáticas , especialmente en probabilidad y combinatoria , una matriz doblemente estocástica (también llamada matriz bistocástica ) es una matriz cuadrada de números reales no negativos , cada una de cuyas filas y columnas suman 1, es decir, ${\displaystyle X=(x_{ij})}$

${\displaystyle \sum _{i}x_{ij}=\sum _{j}x_{ij}=1,}$

Por lo tanto, una matriz doblemente estocástica es tanto estocástica izquierda como estocástica derecha. ^[1]

De hecho, cualquier matriz que sea estocástica tanto izquierda como derecha debe ser cuadrada : si cada fila suma 1, entonces la suma de todas las entradas en la matriz debe ser igual al número de filas, y como lo mismo ocurre con las columnas, el número de filas y columnas debe ser igual.

Politopo de Birkhoff

La clase de matrices doblemente estocásticas es un politopo convexo conocido como politopo de Birkhoff . Si se utilizan las entradas de la matriz como coordenadas cartesianas , se encuentra en un subespacio afín de dimensión 1 del espacio euclidiano de dimensión 1 definido por restricciones lineales independientes que especifican que las sumas de las filas y las columnas son todas iguales a 1. (Existen restricciones en lugar de porque una de estas restricciones es dependiente, ya que la suma de las sumas de las filas debe ser igual a la suma de las sumas de las columnas). Además, todas las entradas están restringidas a ser no negativas y menores o iguales a 1. ${\displaystyle n\times n}$ ${\displaystyle B_{n}}$ ${\displaystyle (n-1)^{2}}$ ${\displaystyle n^{2}}$ ${\displaystyle 2n-1}$ ${\displaystyle 2n-1}$ ${\displaystyle 2n}$

Teorema de Birkhoff-von Neumann

El teorema de Birkhoff-von Neumann (conocido a menudo simplemente como teorema de Birkhoff ^{[2] [3] [4]} ) establece que el politopo es la envoltura convexa del conjunto de matrices de permutación , y además que los vértices de son precisamente las matrices de permutación. En otras palabras, si es una matriz doblemente estocástica, entonces existen y matrices de permutación tales que ${\displaystyle B_{n}}$ ${\displaystyle n\times n}$ ${\displaystyle B_{n}}$ ${\displaystyle X}$ ${\displaystyle \theta _{1},\ldots ,\theta _{k}\geq 0,\sum _{i=1}^{k}\theta _{i}=1}$ ${\displaystyle P_{1},\ldots ,P_{k}}$

${\displaystyle X=\theta _{1}P_{1}+\cdots +\theta _{k}P_{k}.}$

(Esta descomposición de X se conoce como "combinación convexa"). A continuación se ofrece una prueba del teorema basada en el teorema del matrimonio de Hall .

Esta representación se conoce como descomposición de Birkhoff-von Neumann y puede no ser única. A menudo se describe como una generalización de valores reales del teorema de König , donde la correspondencia se establece a través de matrices de adyacencia de grafos.

Propiedades

• El producto de dos matrices doblemente estocásticas es doblemente estocástica. Sin embargo, la inversa de una matriz doblemente estocástica no singular no tiene por qué ser doblemente estocástica (de hecho, la inversa es doblemente estocástica si tiene entradas no negativas).
• La distribución estacionaria de una cadena de Markov finita aperiódica irreducible es uniforme si y sólo si su matriz de transición es doblemente estocástica.
• El teorema de Sinkhorn establece que cualquier matriz con entradas estrictamente positivas puede hacerse doblemente estocástica mediante pre y post-multiplicación por matrices diagonales .
• Para , todas las matrices bistocásticas son unistocásticas y ortocásticas , pero para matrices más grandes este no es el caso. ${\displaystyle n=2}$ ${\displaystyle n}$
• La conjetura de Van der Waerden de que el mínimo permanente entre todas las matrices doblemente estocásticas n × n es , se logra por la matriz para la cual todas las entradas son iguales a . ^[5] Las pruebas de esta conjetura fueron publicadas en 1980 por B. Gyires ^[6] y en 1981 por GP Egorychev ^[7] y DI Falikman; ^[8] por este trabajo, Egorychev y Falikman ganaron el Premio Fulkerson en 1982. ^[9] ${\displaystyle n!/n^{n}}$ ${\displaystyle 1/n}$

Demostración del teorema de Birkhoff-von Neumann

Sea X una matriz doblemente estocástica. A continuación, demostraremos que existe una matriz de permutación P tal que x _ij  ≠ 0 siempre que p _ij  ≠ 0. Por lo tanto, si dejamos que λ sea el x _ij más pequeño correspondiente a un p _ij distinto de cero , la diferencia X  – λ P será un múltiplo escalar de una matriz doblemente estocástica y tendrá al menos una celda cero más que X . En consecuencia, podemos reducir sucesivamente el número de celdas distintas de cero en X eliminando múltiplos escalares de matrices de permutación hasta llegar a la matriz cero, en cuyo punto habremos construido una combinación convexa de matrices de permutación igual a la X original . ^[2]

Por ejemplo, si entonces , , y . ${\displaystyle X={\frac {1}{12}}{\begin{pmatrix}7&0&5\\2&6&4\\3&6&3\end{pmatrix}}}$ ${\displaystyle P={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}}$ ${\displaystyle \lambda ={\frac {2}{12}}}$ ${\displaystyle X-\lambda P={\frac {1}{12}}{\begin{pmatrix}7&0&3\\0&6&4\\3&4&3\end{pmatrix}}}$

Demostración: Construya un grafo bipartito en el que las filas de X estén listadas en una parte y las columnas en la otra, y en el que la fila i esté conectada a la columna j si y solo si x _ij  ≠ 0. Sea A cualquier conjunto de filas y defina A ' como el conjunto de columnas unidas a filas en A en el grafo. Queremos expresar los tamaños | A | y | A' | de los dos conjuntos en términos de x _ij .

Para cada i en A , la suma sobre j en A' de x _ij es 1, ya que todas las columnas j para las cuales x _ij  ≠ 0 están incluidas en A ' , y X es doblemente estocástico; por lo tanto | A | es la suma sobre todos los i  ∈  A , j  ∈  A ' de x _ij .

Mientras tanto | A ' | es la suma de todos los i (estén o no en A ) y todos los j en A ' de x _ij  ; y esto es ≥ la suma correspondiente en la que los i están limitados a filas en A . Por lo tanto | A ' | ≥ | A |.

De ello se deduce que se cumplen las condiciones del teorema del matrimonio de Hall y que, por tanto, podemos encontrar un conjunto de aristas en el grafo que unen cada fila de X con exactamente una columna (distinta). Estas aristas definen una matriz de permutación cuyas celdas no nulas corresponden a celdas no nulas en X.

Generalizaciones

Existe una generalización sencilla para matrices con más columnas y filas, de modo que la suma de  ^las filas i sea igual a r _i (un entero positivo), las sumas de las columnas sean iguales a 1 y todas las celdas no sean negativas (la suma de las sumas de las filas sea igual al número de columnas). Cualquier matriz en esta forma se puede expresar como una combinación convexa de matrices en la misma forma formadas por 0 y 1. La prueba consiste en reemplazar la  ^fila i de la matriz original por r _i filas separadas, cada una igual a la fila original dividida por r _i  ; aplicar el teorema de Birkhoff a la matriz cuadrada resultante; y al final, recombinar de forma aditiva las r _i filas en una única  ^fila i .

De la misma manera, es posible replicar columnas y filas, pero el resultado de la recombinación no se limita necesariamente a 0 y 1. R. M. Caron et al. propusieron una generalización diferente (con una prueba significativamente más difícil) ^[3].

Véase también

• Matriz estocástica
• Matriz unistocástica
• Algoritmo de Birkhoff

Referencias

1. Marshal, Olkin (1979). Desigualdades: teoría de la mayorización y sus aplicaciones . pp. 8. ISBN 978-0-12-473750-1.
2. Teorema de Birkhoff, notas de Gábor Hetyei.
3. RM Caron, Xin Li, P. Mikusiński, H. Sherwood y MD Taylor, Matrices no cuadradas “doblemente estocásticas” , en: Distribuciones con marginales fijos y temas relacionados , IMS Lecture Notes – Monographs Series, editado por L. Rüschendorf, B. Schweizer y MD Taylor, vol. 28, págs. 65-75 (1996) | DOI:10.1214/lnms/1215452610
4. WB Jurkat y HJ Ryser, "Rangos de términos y permanentes de matrices no negativas" (1967).
5. van der Waerden, BL (1926), "Aufgabe 45", Jber. Alemán. Matemáticas.-Verein. , 35 : 117.
6. Gyires, B. (1980), "La fuente común de varias desigualdades relativas a matrices doblemente estocásticas", Publicationes Mathematicae Institutum Mathematicum Universitatis Debreceniensis , 27 (3–4): 291–304, MR  0604006.
7. Egoryčev, GP (1980), Reshenie problemy van-der-Vardena dlya permanenteov (en ruso), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., pág. 12, SEÑOR  0602332. Egorychev, GP (1981), "Prueba de la conjetura de van der Waerden para permanentes", Akademiya Nauk SSSR (en ruso), 22 (6): 65–71, 225, MR  0638007Egorychev , GP (1981), "La solución del problema de van der Waerden para permanentes", Advances in Mathematics , 42 (3): 299–305, doi : 10.1016/0001-8708(81)90044-X , MR  0642395.
8. Falikman, DI (1981), "Prueba de la conjetura de van der Waerden sobre la permanente de una matriz doblemente estocástica", Akademiya Nauk Soyuza SSR (en ruso), 29 (6): 931–938, 957, MR  0625097.
9. Premio Fulkerson, Mathematical Optimization Society, consultado el 19 de agosto de 2012.

• Brualdi, Richard A. (2006). Clases de matrices combinatorias . Enciclopedia de matemáticas y sus aplicaciones. Vol. 108. Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4.Zbl 1106.05001  .

Enlaces externos

• Página de PlanetMath sobre el teorema de Birkhoff-von Neumann
• Página de PlanetMath sobre la demostración del teorema de Birkhoff-von Neumann