Consider a vector $p =(p\_1,...p\_n)$, $p\_i>0$, $\sum p\_i = 1$
and a matrix $M\_{ij}$, which is [doubly stochastic](https://en.wikipedia.org/wiki/Doubly_stochastic_matrix): $\sum\_i M\_{ij} = 1, \sum\_j M\_{ij} = 1, M\_{ij} > 0$.


**Question 1** Just apply matrix M to a vector $p$ , i.e. $q = Mp$ (i.e. $q\_i = \sum\_j M\_{ij} p\_j$) is it true that [entropy](https://en.wikipedia.org/wiki/Entropy_(information_theory)) of new vector $q$ is greater then of original vector $p$ ? I.e.


$$ H(q) = -\sum\_i q\_i ln(q\_i) > -\sum\_i p\_i ln(p\_i) = H(p) $$ 


**Question 2** Is there a simple proof of it ? (It might follow from the [Gibb's inequality](https://en.wikipedia.org/wiki/Gibbs%27_inequality), but it does not seem obvious for me). 


**Question 3** What are generalizations,
in view of meta-principle "entropy *always* grows" that might be an example of some more general phenomena ? 




---


**Motivation:** There is a meta-principle that *entropy grows* is some natural systems, matrix applied to a vector is probably the most simple system one can consider ([Markov chain](https://en.wikipedia.org/wiki/Markov_chain)), so the question above arises. After some thinking one can restrict from all matrices to doubly stochastic, because $M^n v$ tends to a uniform distribution (which has maximal entropy of all) only for doubly stochastic $M$ , so it cannot be true for general $M$. 



Apply doubly stochastic matrix M to a probability vector, then entropy increases?
This is a particular case of the following general principle. On the one hand, a bistochastic matrix $M$ has the property that for every non-negative vector (say, a probability vector), $Mp\succ p$. On another hand, the order $\succ$ can be defined by $x\succ y$ iff $\sum\_if(x\_i)\le\sum\_if(y\_i)$ for every convex function $f$.


Now, use the fact that $f=-H$ is convex.


For proofs, see my book *Matrices* (Springer-Verlag GTM #216, second edition) at sections 6.5 (Proposition 6.4) and 8.5 (Theorem 8.5).


**Edit** (at Alexander's request.) Let $\alpha\ne1$ be a positive parameter. The Renyi entropy is
$$\frac1{1-\alpha}\log\sum\_jp\_j^\alpha.$$
The map $p\mapsto Mp$ does increase Renyi entropy. **Proof**: if $\alpha>1$, the map $t\mapsto t^\alpha$ is convex, and $s\mapsto\frac1{1-\alpha}\log s$ is increasing. If instead $\alpha<1$, the map $t\mapsto t^\alpha$ is concave, and $s\mapsto\frac1{1-\alpha}\log s$ is decreasing.


