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, [1] es decir,
- ,
Por lo tanto, una matriz doblemente estocástica es tanto estocástica izquierda como estocástica derecha. [1] [2]
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. [1]
Politopo Birkhoff
La clase de matrices doblemente estocásticas es un politopo convexo conocido como el politopo de Birkhoff . Usando las entradas de la matriz como coordenadas cartesianas , se encuentra en un-subespacio afín dimensional de -espacio euclidiano dimensional definido porrestricciones lineales independientes que especifican que las sumas de fila y columna son todas iguales. (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 para ser no negativas y menores o iguales a uno.
Teorema de Birkhoff-von Neumann
El teorema de Birkhoff-von Neumann establece que el politopoes el casco convexo del conjunto de matrices de permutación , y además que los vértices deson precisamente las matrices de permutación. En otras palabras, si es una matriz doblemente estocástica, entonces existen y matrices de permutación tal que
Esta representación se conoce como la descomposición de Birkhoff-von Neumann y puede que no sea única en general. Por el teorema de Carathéodory , sin embargo, existe una descomposición con no más detérminos, es decir, con [3]
En otras palabras, mientras exista una descomposición con matrices de permutación, hay al menos una descomposición construible con no más de matrices. Tal descomposición se puede encontrar en tiempo polinomial usando el algoritmo de Birkhoff . Esto 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.
- Van der Waerden conjeturó que el mínimo permanente entre todas las n × n matrices doblemente estocásticas es, logrado por la matriz para la cual todas las entradas son iguales a . [4] Las pruebas de esta conjetura fueron publicadas en 1980 por B. Gyires [5] y en 1981 por GP Egorychev [6] y DI Falikman; [7] por este trabajo, Egorychev y Falikman ganaron el Premio Fulkerson en 1982. [8]
Ver también
Referencias
- ↑ a b c Gagniuc, Paul A. (2017). Cadenas de Markov: de la teoría a la implementación y experimentación . Estados Unidos, Nueva Jersey: John Wiley & Sons. págs. 9-11. ISBN 978-1-119-38755-8.
- ^ Mariscal, Olkin (1979). Desigualdades: teoría de la mayorización y sus aplicaciones . pp. 8 . ISBN 978-0-12-473750-1.
- ^ Marcus, M .; Ree, R. (1959). "Diagonales de matrices doblemente estocásticas". The Quarterly Journal of Mathematics . 10 (1): 296-302. doi : 10.1093 / qmath / 10.1.296 .
- ^ van der Waerden, BL (1926), "Aufgabe 45", Jber. Alemán. Math.-Verein. , 35 : 117.
- ^ 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.
- ^ Egoryčev, GP (1980), Reshenie problemy van-der-Vardena dlya permanentov (en ruso), Krasnoyarsk: Akad. Nauk SSSR Sibirsk. Otdel. Inst. Fiz., Pág. 12, MR 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", Advances in Mathematics , 42 (3): 299-305, doi : 10.1016 / 0001-8708 (81) 90044-X , MR 0642395.
- ^ 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.
- ^ 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 las matemáticas y sus aplicaciones. 108 . Cambridge: Cambridge University Press . ISBN 978-0-521-86565-4. Zbl 1106.05001 .
enlaces externos
- Página PlanetMath sobre el teorema de Birkhoff-von Neumann
- Página de PlanetMath sobre la demostración del teorema de Birkhoff-von Neumann