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