Matriz doblemente estocástica

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

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

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

En efecto, cualquier matriz que sea estocástica tanto por la izquierda como por la derecha debe ser cuadrada : si la suma de cada fila es igual a 1, entonces la suma de todas las entradas de 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.

La clase de${\displaystyle n\times n}$Las matrices doblemente estocásticas son un politopo convexo conocido como politopo de Birkhoff.${\displaystyle B_{n}}$. Utilizando las entradas de la matriz como coordenadas cartesianas , se encuentra en un${\displaystyle (n-1)^{2}}$subespacio afín de dimensión -${\displaystyle n^{2}}$Espacio euclidiano de -dimensiones definido por${\displaystyle 2n-1}$restricciones lineales independientes que especifican que las sumas de filas y columnas son todas iguales a 1. (Hay${\displaystyle 2n-1}$restricciones en lugar de${\displaystyle 2n}$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.

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

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

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

Esta representación se conoce como la descomposición de Birkhoff-von Neumann y puede no ser única. A menudo se describe como una generalización en valores reales del teorema de Kőnig , donde la correspondencia se establece mediante matrices de adyacencia de grafos. El teorema de Birkhoff-von Neumann también encuentra aplicaciones en la programación lineal entera . ^{[ 5 ]}

• 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 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 solo 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 premultiplicación y postmultiplicación por matrices diagonales .
• Para${\displaystyle n=2}$, todas las matrices bistocásticas son unistocásticas y ortostocásticas , pero para matrices más grandes${\displaystyle n}$Este no es el caso.
• La conjetura de Van der Waerden de que el permanente mínimo entre todas las matrices doblemente estocásticas n × n es${\displaystyle n!/n^{n}}$, logrado mediante la matriz para la cual todas las entradas son iguales a${\displaystyle 1/n}$. ^{[ 6 ]} Las pruebas de esta conjetura fueron publicadas en 1980 por B. Gyires ^{[ 7 ]} y en 1981 por GP Egorychev ^{[ 8 ]} y DI Falikman; ^{[ 9 ]} por este trabajo, Egorychev y Falikman ganaron el Premio Fulkerson en 1982. ^{[ 10 ]}

Sea X una matriz doblemente estocástica. Demostraremos entonces que existe una matriz de permutación P tal que x _ij ≠ 0 siempre que p _ij ≠ 0. Por lo tanto, si denotamos por λ el menor x _ij 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 que habremos construido una combinación convexa de matrices de permutación igual a la X original . ^{[ 2 ]}      

Por ejemplo, si${\displaystyle X={\frac {1}{12}}{\begin{pmatrix}7&0&5\\2&6&4\\3&6&3\end{pmatrix}}}$entonces ${\displaystyle P={\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}}$,${\displaystyle \lambda ={\frac {2}{12}}}$, y ${\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 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 y solo si x _ij ≠ 0. Sea  ${\displaystyle A}$sea ​​cualquier conjunto de filas y defina${\displaystyle A'}$como el conjunto de columnas unidas a filas en A en el gráfico. Queremos expresar los tamaños${\displaystyle |A|}$y${\displaystyle |A'|}$de los dos conjuntos en términos de los 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  ${\displaystyle |A|}$es la suma sobre todos los i  ∈ A , j ∈ A ' de x _ij .   

Mientras tanto${\displaystyle |A'|}$es la suma sobre 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${\displaystyle |A'|\geq |A|}$.

De ello se deduce que se cumplen las condiciones del teorema de matrimonio de Hall y que, por lo 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.

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

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

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