37 Permanents and the power of entropy

Theorem 37.1

Let \(M = (m_{ij})\) be an \(n \times n\) matrix with entries in \(\{ 0, 1\} \), and let \(d_1, \dots , d_n\) be the row sums of \(M\), that is, \(d_i = \sum _{j=1}^{n} m_{ij}\). Then

\[ \operatorname {per} M \leq \prod _{i=1}^{n} (d_i!)^{1/d_i}. \]

Proof ▶

TODO

Theorem 37.2

The number \(L(n)\) of Latin squares of order \(n\) is bounded by

\[ \frac{n!^{2n}}{n^{n^2}} \le L(n) \le \prod _{k=1}^{n}k!^{n/k} \]

Proof ▶

TODO

37.1 Appendix: More about entropy

Theorem 37.3 Fact A

\[ H(X)\le \log _2(|\operatorname {supp}{X}). \]

Proof ▶

TODO

Theorem 37.4 Fact B

\[ H(X, Y) = H(X) + H(Y|X). \]

Proof ▶

TODO

Theorem 37.5 Fact B

\[ H(Y|X)\le \sum _{j=1}^d \operatorname {Prop}(X\in E_j)\log _2 j. \]

Proof ▶

TODO