MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.