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?


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.