37 Permanents and the power of entropy

Theorem 37.1

Let $M = (m_{i j})$ 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_{i j}$ . Then

per M \leq \prod_{i = 1}^{n} (d_{i}!)^{1 / d_{i}} .

Proof ▶

Theorem 37.2

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

\frac{n!^{2 n}}{n^{n^{2}}} \leq L (n) \leq \prod_{k = 1}^{n} k!^{n / k}

Proof ▶

37.1 Appendix: More about entropy

Theorem 37.3 Fact A

H (X) \leq \log_{2} (| supp X) .

Proof ▶

Theorem 37.4 Fact B

H (X, Y) = H (X) + H (Y | X) .

Proof ▶

Theorem 37.5 Fact B

H (Y | X) \leq \sum_{j = 1}^{d} Prop (X \in E_{j}) \log_{2} j .

Proof ▶