# Entropy of distribution with block matrix support

Let $$P(X_1,X_2)$$ be a discrete bivariate distribution that has the form shown in the figure below, i.e. its support can be split into blocks that do not overlap on either dimensions.

Let's build $$P'(B_1,B_2)$$ obtained from $$P(X_1,X_2)$$ by integrating (summing) the values within each block. I would like to show that the following inequality holds $$H(X_1) + H(X_2) - H(X_1,X_2) \ge H'(B_1) + H'(B_2) - H'(B_1,B_2)$$ where $$H$$ denotes entropy values computed with respect to $$P(X_1,X_2)$$ and $$H'$$ entropy values computed using $$P'(X_1,X_2)$$. Proving the inequality will allow me to prove this theorem.

Question 1: Any suggestion on how to prove this?

Question 2: How would you call a matrix like the one above? According to wikipedia the name "block diagonal matrix" applies only if the matrix and the blocks are squares.

You'd like to show that when you "coarse grain" the values of two random variables, then the mutual information between them cannot increase: $$I(B_1; B_2) \le I(X_1;X_2)$$. This is true, and more generally any kind of "post-processing" can only destroy mutual information.
Lemma: If $$X$$ and $$Z$$ are independent conditional on $$Y$$ (e.g. if $$Z$$ is a function of $$Y$$), then $$I(X;Z) \le I(X;Y)$$.
Proof: By the chain rule for information (Theorem 2.5.2 of Cover and Thomas), we can express $$I(X;Y,Z)$$ in two different ways: $$I(X;Z) + \underbrace{I(X;Y|Z)}_{\ge 0} = I(X;Y,Z) = I(X;Y) + \underbrace{I(X;Z|Y)}_{=0}$$ Since $$X$$ and $$Z$$ are independent conditional on $$Y$$, we have that $$I(X;Z|Y)=0$$, and all the terms (specifically $$I(X;Y|Z)$$) must be non-negative, so we have $$I(X;Z) \le I(X;Y)$$.
Since $$B_1$$ is a function of $$X_1$$ and $$B_2$$ is a function of $$X_2$$, you get the result you want by applying this lemma twice: $$I(B_1;B_2) \le I(X_1; B_2) \le I(X_1; X_2).$$