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?
Best Answer
This question has been studied here (but no characterization is given)
Marcus, Marvin; Kidman, Kent; Sandy, Markus. Products of elementary doubly stochastic matrices. Linear and Multilinear Algebra 15 (1984), no. 3-4, 331–340.
Note also that if we consider the family of matrices with rows and columns adding up to 1 (but allow negative entries) and $\alpha \in \mathbf{R}$, the corresponding result is true, see
Johnsen, E. C. Essentially doubly stochastic matrices. III. Products of elementary matrices. Linear and Multilinear Algebra 1 (1973), no. 1, 33–45.