On entropy-preserving stochastic averages

When an n×n doubly stochastic matrix A acts on Rn on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γn denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γn is a subset of Bn×Σn where Bn is the Birkhoff polytope and Σn is the probability simplex.We characterize Γn and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γn if and only if AtAP=P. We show that for any n, Γn is a connected set, and is in fact piecewise-linearly contractible in Bn×Σn. We write Γn as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γn. Γ3 is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable.