¿Cuántas matrices doblemente estocásticas con $Dp=q$ existen?

Question

Sean $p,q$ vectores de probabilidad $n$-dimensionales tal que $p$ majoriza a $q$ (es decir, $p$ está menos mezclado que $q$). Es un resultado clásico que esto se cumple si y solo si existe una matriz doblemente estocástica de $n\times n$ tal que $Dp=q$. Estoy interesado en el conjunto $D(p,q)$ de matrices doblemente estocásticas que mapean $p$ a $q$.

¿Qué se sabe sobre este conjunto? Claramente, $D(p,q)$ es un conjunto convexo. ¿Cuáles son los puntos extremos? ¿Existen matrices doblemente estocásticas $D\in D(p,q)$ que sean óptimas de alguna manera?

También es evidente que cualquier degeneración en $p$ y $q$ genera una simetría de $D(p,q)$, por ejemplo, si $p=(\frac12, \frac14,\frac14)$ entonces $D\in D(p,q) \iff D P_{(12)} \in D(p,q)$ donde $P_{(12)}$ es la matriz de permutación que intercambia la primera y segunda entrada. ¿Existen otras simetrías? Si asumimos que tanto $p$ como $q$ son no degenerados (es decir, todas las entradas son distintas), esta simetría desaparece. ¿Qué tan grande es $D(p,q)$ ahora? ¿Hay una única matriz d.s. en este caso?

Answer 1

Esta pregunta se discute en el libro A. Marshall, I. Olkin y B. Arnold. Inequalities: Theory of Majorization and Its Applications. 2a ed. Nueva York: Springer, 2011., más precisamente en las páginas 54 y siguientes de la sección "The Doubly Stochastic Matrices of a Given Majorization". Después de presentar algunos ejemplos y resultados relacionados, en la página 59 dan el siguiente resultado (Cap. 2, Lemma G.6); sustituiré algunas de sus notaciones para que las cosas sean más accesibles:

Sean $ p,q \in \mathbb R^n$ con $p_1\geq\ldots\geq p_n$, $q_1\geq\ldots\geq q_n$ dados de tal manera que $q \prec p$. Existe una matriz doblemente estocástica única $D$ con $Dp=q$ si y solo si se cumplen las siguientes dos condiciones:

• $p$ tiene componentes distintas
• Para algún entero $m \leq n$, $p$ y $q$ tienen coincidencias en posiciones $1 \leq k_1 < k_2 < \ldots < k_{m−1} \leq n − 1$, donde $k_j − k_{j−1}\leq 2$ para cada $j = 1, 2, \ldots , m-2$.

Por lo tanto, la condición que identificaste de que las entradas de $p$ deben ser distintas no es suficiente para garantizar la unicidad de $D$. Marshall et al. también dan un ejemplo para ilustrar esto (Cap. 2, Ejemplo G.2): Para $p=(5,3,1)$ (¡entradas distintas!) y $q=(4,3,2)$ muestran que el conjunto $D(p,q)$ tiene cuatro puntos extremos.