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 izquierda y derecha debe ser cuadrada : si cada fila suma 1, entonces la suma de todas las entradas de la matriz debe ser igual al número de filas, y dado que lo mismo se aplica a las columnas, el número de Las filas y columnas deben ser iguales.

Politopo Birkhoff

La clase de matrices doblemente estocásticas es un politopo convexo conocido como politopo de Birkhoff . Usando las entradas de la matriz como coordenadas cartesianas , se encuentra en un subespacio afín de dimensión del espacio euclidiano de dimensión definido por restricciones lineales independientes que especifican que las sumas de fila y columna son todas iguales a 1. (Hay 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 obligadas 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 (a menudo conocido simplemente como teorema de Birkhoff ^{[2] [3] [4]} ) establece que el politopo es la cáscara 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 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 proporciona una demostración 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 en valor real del teorema de Kőnig , donde la correspondencia se establece mediante matrices de adyacencia de gráficos.

Otras propiedades

• El producto de dos matrices doblemente estocásticas es doblemente estocástico. Sin embargo, la inversa de una matriz doblemente estocástica no singular no necesita 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 la multiplicación previa y posterior por matrices diagonales .
• Para , todas las matrices bistocásticas son unistocásticas y ortostocásticas , pero para las 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 de n × n es , logrado 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}$

Prueba del teorema de Birkhoff-von Neumann

Sea X una matriz doblemente estocástica. Luego 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, momento en el cual 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}}}$

Prueba: Construya un gráfico bipartito en el que las filas de X se enumeran en una parte y las columnas en la otra, y en el que la fila i está conectada a la columna j 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 gráfico. Queremos expresar los tamaños | Un | 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 | Un | es la suma de todos i  ∈  A , j  ∈  A ' de x _ij .

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

De ello se deduce que se satisfacen las condiciones del teorema del matrimonio de Hall y que, por lo tanto, podemos encontrar un conjunto de aristas en el gráfico que unen cada fila de X con exactamente una columna (distinta). Estos bordes definen una matriz de permutación cuyas celdas distintas de cero corresponden a celdas distintas de cero en X .

Generalizaciones

Existe una generalización simple para matrices con más columnas y filas, de modo que la suma de la i-  ^ésima fila es igual a r _i (un entero positivo), las sumas de las columnas son iguales a 1 y todas las celdas no son negativas (la suma de las las sumas de las filas son iguales al número de columnas). Cualquier matriz en esta forma se puede expresar como una combinación convexa de matrices de la misma forma compuesta por 0 y 1. La prueba es reemplazar la i-  ^ésima fila 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 aditivamente las r _i filas en una única i-  ^ésima fila.

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. han propuesto una generalización diferente (con una prueba significativamente más sólida). ^[3]

Ver también

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

Referencias

1. Mariscal, Olkin (1979). Desigualdades: teoría de la mayorización y sus aplicaciones . págs.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 márgenes 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  0638007. Egorychev, GP (1981), "La solución del problema de van der Waerden para permanentes", Avances en Matemáticas , 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 el permanente de una matriz doblemente estocástica", Akademiya Nauk Soyuza SSR (en ruso), 29 (6): 931–938, 957, MR  0625097.
9. Premio Fulkerson, Sociedad de Optimización Matemática, 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: Prensa de la Universidad de Cambridge . 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 prueba del teorema de Birkhoff-von Neumann