Let $(a_i)_{i=1}^n$ be a probability vector, that is, $a_i\geq 0$ and $\sum_i a_i=1$ and let $(U_{ij})_{i,j=1}^n$ be a unistochastic matrix, that is, the pointwise square of a unitary matrix. Now consider the vector $v=U \cdot a$. It is a vector that is more mixed than $a$ (or more precisely $a$ majorizes $v$). It seems intuitive that there should exist a probabilistic ensemble $(t_i,x_i)_{i=1}^m$ (with $t_i$ probabilities and $x_i$ vectors) such that $v=\sum_{i=1}^m t_i x_i$ and the components of every $x_i$ is a permutation of the components of $a$.
One example to make things concrete. Let $a=(0.6,0.2,0.2)$ and
$$ U=\left(\begin{array}{ccc} 1/2 & 1/2 & 0 \\ 1/2 & 1/2 & 0 \\ 0 & 0 & 1 \end{array}\right) $$
then $v=(0.4,0.4,0.2)$ and it can be written as:
$$ v= 0.5 \left(\begin{array}{c} 0.6 \\ 0.2 \\ 0.2 \end{array}\right) + 0.5 \left(\begin{array}{c} 0.2 \\ 0.6 \\ 0.2 \end{array}\right) $$ that is, we can write $v$ as a convex combination of two permutations of $a$.
Then my question is, does this convex decomposition exist in general? I guess that the answer is yes, and that it is based on some well known litterature, so any pointers to the relevant texts would also be welcome.
This is indeed true. A unistochastic matrix $U$ is doubly stochastic (i.e. real, non-negative, and each row and column sums to $1$, see also here: http://en.wikipedia.org/wiki/Unistochastic_matrix). Moreover, the Birkhoff-von Neumann-Theorem states that every doubly stochastic matrix is a convex combination of permutation matrices (see here: http://en.wikipedia.org/wiki/Birkhoff-von_Neumann_Theorem). So we have a representation $$ U = \sum_{j=1}^m t_j P_j $$ with some $m \in \mathbb N$, permutation matrices $P_j$, and real coefficients $t_j \geq 0$ with $\sum_{j=1}^mt_j=1.$ If we put $x_j = P_ja$, then the coordinates of $x_j$ are a permutation of those of $a$, and we get $$ v=UA=\left(\sum_{j=1}^mt_jP_j\right)a = \sum_{j=1}^mt_j\left(P_ja\right) = \sum_{j=1}^mt_jx_j, $$ as desired.