# Shannon entropy and doubly stochastic matrices

Suppose that $$A$$ is a stochastic matrix. We know that if $$A$$ is doubly stochastic, then $$H(Ap)\geq H(p)$$ where $$H$$ is Shannon entropy and $$p$$ is a probability vector. Is the converse true? i.e., if $$H(Ap)\geq H(p)$$ then $$A$$ is doubly stochastic.

Consider any $$n \times n$$ left stochastic matrix $$A$$, i.e. each column sums up to $$1$$. We argue that if $$H(Ap) \geq H(p)$$ for all probability distributions $$p$$, then $$A$$ is doubly stochastic.

Take $$p$$ to be the uniform distribution. Then $$H(Ap) \geq H(p)$$ implies that $$Ap = p$$, since the uniform distribution on $$[n]$$ is the unique maximizer of Shannon entropy among all probability distributions on $$[n]$$.

Since $$p = \frac{1}{n} 1$$ (the all ones vector), we have that $$A1 = 1$$ -- all rows sum up to $$1$$. Thus, $$A$$ is doubly stochastic.

If expressed in terms of majorization of vectors, at least for finite dimensional probability vectors, I think it is known that (Horn's Lemma?) $$q\prec p$$ if and only if there is a doubly stochastic matrix $$D$$ with $$q=Dp.$$ Since permuting the entries does not change entropy this should do it.

• I am sorry, I don't see how "this should do it". Oct 7 '20 at 2:48
• Thank you! Is it possible to introduce a reference including the proof of this lemma?
– Aram
Oct 7 '20 at 4:30
• @IosifPinelis, I am having trouble substantiating my claim. I may delete it. What about the other answer? Do you think that's correct? Oct 8 '20 at 3:35
• @kodlu : Yes, I think it's correct, except that "the uniform distribution on $[n]$ maximizes Shannon entropy among all probability distributions on $[n]$" should be replaced by "only the uniform distribution on $[n]$ maximizes Shannon entropy among all probability distributions on $[n]$". Oct 8 '20 at 13:09
• @IosifPinelis Thanks, corrected. :-) Oct 15 '20 at 0:34