MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Which doubly stochastic matrices can be written as products of pairwise averaging matrices?

A matrix $A$ is called doubly stochastic if its entries are nonnegative, and if all of its rows and columns add up to $1$. A subset of doubly stochastic matrices is the set of pairwise averaging matrices which move two components of a vector closer to their average. More precisely, a pairwise averaging matrix $P_{i,j,\alpha}$ is defined by stipulating that $y=P_{i,j,\alpha}x$ is $$y_i = (1-\alpha) x_i + \alpha x_j$$ $$y_j = \alpha x_i + (1-\alpha) x_j$$ $$y_k = x_k ~~{\rm for~ all }~ k \neq i,j~,$$ where $\alpha \in [0,1]$.

My question is: can every doubly stochastic matrix be written as a product of pairwise averaging matrices?

If the answer is no, I would like to know if its possible to characterize the doubly stochastic matrices which can be written this way.

Update: I just realized that the answer is no. Here is a sketch of the proof. Pick any $3 \times 3$ doubly stochastic matrix matrix $A$ with $A_{23}=A_{32}=0$. If $A$ can be written as the product of pairwise averages, the pairwise average matrices $P_{2,3,\alpha}$ never appear in the product, since they result in setting the $(2,3)$ and $(3,2)$ entries to positive numbers, which remain positive after any more applications of pairwise averages. So the product must only use $P_{1,2,\alpha}$ or $P_{1,3,\alpha}$. But one can see that no matter in what order one applies these matrices, at least one of $A_{23}$ or $A_{32}$ will be set to a positive number. For example, if we average 1 and 2 first and then 1 and 3, then $A_{32}$ will be nonzero.

My second question is still unanswered: is it possible to characterize the matrices which are products of pairwise averages?

-