Matriz doblemente estocástica - Doubly stochastic matrix

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.

De hecho, cualquier matriz que sea estocástica tanto a la izquierda como a la derecha debe ser cuadrada : si cada fila suma uno, 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 las filas y las 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 -dimensional del espacio euclidiano -dimensional definido por restricciones lineales independientes que especifican que las sumas de filas y columnas son todas iguales. (Hay restricciones en lugar de porque una de estas restricciones sea 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 para ser no negativas y menores o iguales a uno. . ${\ 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 (generalmente conocido simplemente como teorema de Birkhoff ) establece que el politopo es el casco convexo 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}.}

(Tal descomposición de X se conoce como una 'combinación convexa'). Una prueba del teorema basado en el matrimonio de Hall teorema se da a continuación .

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 con valores reales 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 doble 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 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 pre y post multiplicación por matrices diagonales .
Para , todas las matrices son biestocástica unistochastic y orthostochastic , pero para mayor este no es el caso. ${\ Displaystyle n = 2}$ ${\ Displaystyle n}$
Van der Waerden conjeturó que el mínimo permanente entre todas las n × n matrices doblemente estocásticas se logra mediante la matriz para la cual todas las entradas son iguales a . Las pruebas de esta conjetura fueron publicadas en 1980 por B. Gyires y en 1981 por GP Egorychev y DI Falikman; Por este trabajo, Egorychev y Falikman ganaron el Premio Fulkerson en 1982. ${\ Displaystyle n! / n ^ {n}}$ ${\ Displaystyle 1 / n}$

Prueba del teorema de Birkhoff-von Neumann

Sea X una matriz doblemente estocástica. Entonces mostraremos 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 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 uno más cero celular 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, punto en el que habremos construido una combinación convexa de matrices de permutación igual a la X original .

Por ejemplo, si a continuación , 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 la que la fila i está conectada a la columna j sif x _ij  ≠ 0. Sea A cualquier conjunto de filas, y defina A 'como el conjunto de columnas unidas a las filas de A en el gráfico. Queremos expresar las tallas | A | y | A '| de los dos conjuntos en términos de x _ij .

Para todo 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ástica; 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 (esté o no en | A |) y todo j en A 'de x _ij  ; y esto es ≥ la suma correspondiente en el que la i se limitan 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 a exactamente una columna (distinta). Estos bordes definen una matriz de permutación cuyas células no cero corresponden a las células distintos de cero en X . ∎

Generalizaciones

Hay una generalización simple para matrices con más columnas y filas, de modo que la i- ^ésima suma de la fila es igual a r _i (un entero positivo), las sumas de las columnas son iguales a 1 y todas las celdas son no negativas (la suma de la 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 en 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 aditivamente las filas r _i en una única fila i- ^ésima .

De la misma manera, es posible replicar tanto columnas como 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 difícil).

Ver también

Referencias

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

Languages

In other projects