Matriz doblemente estocástica

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Una matriz cuadrada

En matemáticas, especialmente en probabilidad y combinatoria, a doblemente la matriz estocástica (también llamado matriz bitocástica) es una matriz cuadrada ${displaystyle X=(x_{ij})}$ de números reales no negativos, cada una de cuyas filas y columnas suma a 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 izquierda como estocástica derecha.

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 en la matriz debe ser igual al número de filas, y dado que lo mismo se aplica a las columnas, el número de filas y columnas debe ser igual.

Politopo de Birkhoff

La clase de ${displaystyle ntimes n}$ matrices doblemente estocásticas es un politopo convexo conocido como Birkhoff polytope ${displaystyle B_{n}}$ . Utilizando las entradas de la matriz como coordenadas cartesianas, se encuentra en una ${displaystyle (n-1)^{2}}$ - subespacial affine dimensional ${displaystyle n^{2}}$ -dimensional Espacio euclidiano definido por ${displaystyle 2n-1}$ restricciones lineales independientes que especifican que la fila y la columna suma todos iguales 1. (Hay ${displaystyle 2n-1}$ limitaciones en lugar de ${displaystyle 2n}$ porque una de estas limitaciones es dependiente, ya que la suma de la fila debe igualar la suma de las sumas de la columna.) Además, todas las entradas están limitadas a ser no negativas y menos que o iguales a 1.

Teorema de Birkhoff-von Neumann

El Birkhoff-von Neumann teorema (a menudo conocido simplemente como El teorema de Birkhoff) declara que el politope ${displaystyle B_{n}}$ es el casco convexo del conjunto de ${displaystyle ntimes 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},ldotstheta _{k}geq 0,sum _{i=1}^{k}theta _{i}=1}$ y matrices de permutación ${displaystyle P_{1},ldotsP_{k}}$ tales que

{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, el inverso de una matriz doblemente estocástica no es necesario ser doblemente estocástico (de hecho, el inverso es doblemente stocástico si tiene entradas no negativas).
La distribución estacionaria de una cadena aperiodica finita irreducible Markov es uniforme si y sólo si su matriz de transición es doblemente estocástica.
El teorema de Sinkhorn declara que cualquier matriz con entradas estrictamente positivas puede ser doblemente estocástica por pre- y post-multiplicación por matrices diagonales.
Para ${displaystyle n=2}$ , todas las matrices bistocásticas son inistocásticas y ortocásticas, pero para mayores ${displaystyle n}$ Este no es el caso.
Conjetura de Van der Waerden de que el mínimo permanente entre todos n × n matrices doblemente estocásticas es ${displaystyle n!/n^{n}}$ , logrado por la matriz para la cual todas las entradas son iguales ${displaystyle 1/n}$ . Proofs of this conjecture were published in 1980 by B. Gyires and in 1981 by G. P. Egorychev and D. I. Falikman; for this work, Egorychev and Falikman won the Fulkerson Prize in 1982.

Demostración 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 iguales a la X original.

Por ejemplo si ${displaystyle X={frac {1}{12}}{begin{pmatrix}7&0&5\2&6&4\3&6&3end{pmatrix}}}$ entonces ${displaystyle P={begin{pmatrix}0&0&1\1&0&0\0&1&0end{pmatrix}}}$ , ${displaystyle lambda ={frac {2}{12}}}$ , y ${displaystyle X-lambda P={frac {1}{12}}{begin{pmatrix}7&0&3\0&6&4\3&4&3end{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 qué fila i está conectada a la columna j si x_ij ≠ 0. Sea A > ser cualquier conjunto de filas y definir A' como el conjunto de columnas unidas a filas en A en el gráfico. 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 de todo i ∈ A, j ∈ A' de x_ij.

Mientras tanto |A'| es la suma de todo i (ya sea que esté o no en A) y todo j en el estilo A' de x_ij; y esta 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 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 en X con exactamente una (distinta ) columna. 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^a fila es igual a r_i (un número entero positivo), las sumas de las columnas son iguales a 1 y todas las celdas no son negativas (la suma de las sumas de las filas es igual al número de columnas). Cualquier matriz en esta forma se puede expresar como una combinación convexa de matrices de la misma forma formada 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 de forma aditiva las filas r_i en una única fila i^th.

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

Más resultados...