• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






Matrices doblemente estocásticas

+1 voto
Sea $N$ un número natural fijo. Sea $P_N$ el conjunto de matrices de permutación de dimensión $N \times N$.
Sea $E_N$ el conjunto de matrices doblemente estocásticas de dimensión $N \times N$. Demuestra que la envolvente convexa de $P_N$ coincide con $E_N$.
preguntado por Gerardo (430 puntos) Mar 6, 2014 en Problemas
editado por Gerardo Mar 7, 2014

1 Respuesta

+1 voto
El conjunto $E_N$ es convexo y compacto en $\mathbb{R}^{N \times N}$, así que es la envolvente convexa de sus puntos extremos. Así que basta probar que los puntos extremos de $E_N$ son las matrices de permutación.
 
Sea $M$ una matrix doble estocástica que no es de permutación. Debemos probar que existe un segmento de recta de matrices en $E_N$ que tiene a $M$ como punto medio. Si todas las entradas de $M$ fueran $0$ o $1$, $M$ tendría que ser una matriz de permutación. Por lo tanto $M$ debe tener al menos una entrada $m_{i_0j_0} \in (0,1)$. Como $M$ es doblemente estocástica, para cada entrada estríctamente entre $0$ y $1$, debe haber otra en el mismo renglón y otra en la misma columna. Así que empezando con $m_{i_0j_0}$ podemos encontrar una sucesión de entradas en $(0,1)$, $m_{i_0j_0}, m_{i_0j_1}, m_{i_1j_1}, m_{i_1j_2}, \ldots$, alternando movimientos dentro del renglón y de la columna.
 
Como $M$ solo tiene un número finito de entradas, hay ciclos de entradas de esta forma. Si escogemos el ciclo más corto posible, $m_{i_0j_0}, m_{i_0j_1}, m_{i_1j_1}, m_{i_1j_2}, \ldots, m_{i_rj_0}$, el movimiento de $m_{i_rj_0}$ a $m_{i_0j_0}$ es horizontal (como indica la notación). En efecto, si el ciclo terminara y empezara con un movimiento vertical, podríamos combinar los dos movimientos eliminando un paso del ciclo.
 
Finalmente, ya teniendo el ciclo consideremos la matrix $M(t)$ cuyas entradas coinciden con las de $M$ fuera del ciclo y dentro del ciclo cambiamos las entradas por $m_{i_0j_0}+t, m_{i_0j_1}-t, m_{i_1j_1}+t, m_{i_1j_2}-t, \ldots, m_{i_rj_0}-t$ respectivamente. Para cualquier $t$ las entradas en cada renglón y en cada columna de $M(t)$ sumand $1$. También, si $|t|$ es suficientemente pequeño, todas las entradas de $M(t)$ son no-negativas. Así que hay un $\epsilon>0$ tal que $M(\epsilon), M(-\epsilon)$ son puntos de $E_N$ cuyo punto medio es $M$.
respondido por Omar Antolín (33,060 puntos) Jun 10, 2014
editado por Omar Antolín Jun 10, 2014
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...