La prueba de que el conjunto de doblemente estocástico matrices formas convexos polytope?

Question

¿El conjunto de todos los doblemente estocástico matrices de una forma convexa polytope? En general, me pregunto cómo las pruebas de la convexidad y la geometría puede ser establecido para los conjuntos de matrices de este tipo? Nada que ver con la del teorema de birkhoff!? No estoy segura de si estoy pensando en la dirección correcta y por lo tanto el post.

Answer 1

Yo sólo escribo esta respuesta para resumir los comentarios.

Identificar el espacio de la matriz $\mathbb{R}^{n\times n}$$\mathbb{R}^{n^2}$. Una matriz de $(a_{i,j})_{i,j\leq n}$ es doblemente estocástica si

1. $0\leq a_{i,j}\leq 1\ \forall i,j$
2. $\sum_i a_{i,j}=1 \ \forall j$
3. $\sum_j a_{i,j}=1 \ \forall i$

Es directo comprobar que si $(a_{i,j})_{i,j\leq n}$ $(b_{i,j})_{i,j\leq n}$ son doblemente estocástico, a continuación, $(t a_{i,j}+ (1-t) b_{i,j})_{i,j\leq n}$ es doblemente estocástico para cualquier $0\leq t\leq1$ (las condiciones anteriores son claramente cumplió). Esto le da a la convexidad.

Observar que el conjunto de doblemente estocástica de las matrices es un polytope en $\mathbb{R}^{n^2}$ sólo tenemos que tener en cuenta que un polytope puede ser definida como un número finito de intersección de la mitad de los espacios. Las condiciones anteriores son, en realidad $2n^2+4$ desigualdades (tener en cuenta que $a=b\iff (a\leq b \text{ and } b\leq a)$ ).

Creo que es usual considerar que un polytope es acotado, aquí esto es evidente debido a la condición $1$.

Edit: Como usted sugiere en su pregunta, este es un corolario directo de Birkhoff-Von Neumann teorema que es mucho más fuerte. El Birkhoff–von Neumann teorema establece que el conjunto de doblemente estocástica de las matrices es el casco convexo de un conjunto de matrices de permutación. Hay un número finito de permutaciones y el casco convexo de un número finito de puntos es un cuerpo convexo, por lo que la conclusión es inmediata. Pero si lo que desea es ver que este es un convexo polytope sin ir más precisos usted no necesita usar este teorema, la primaria argumentos utilizados anteriormente son sufficients.