How can I represent the inclusion-exclusion principle in a matrix form?

Question

I have some interactive sets and I can calculate their cardinalities and intersections. So, by applying the inclusion-exclusion principle, the union of the sets is calculable. My question is: How can I arrange these cardinalities and intersections on a matrix in a meaningful way so that the union is measurable by a matrix operation like finding its determinant or eigenvalue. I mean how can I migrate/map/transform the inclusion-exclusion principle into a matrix problem.

Answer 1

Let $P$ be a finite partially ordered set, such as a the Boolean algebra of subsets of a set $A$, $2^A$. The incidence algebra of the set is the set of all functions $f:P\times P\to \mathbb R$ such that $f(a,b)=0$ unless $a\leq b$. We view these as upper triangular matrices over $P$, and this comes with a corresponding multiplication.

Let $\zeta$ be the function such that $$\zeta(a,b)=\begin{cases} 1&\mbox{ if }a\leq b\\ 0&\mbox{ otherwise.} \end{cases}$$ Being upper triangular with $1$'s on the diagonal, this matrix is invertible. Its inverse is called the Mobius function $\mu$. It is then a simple theorem of linear algebra that if $g:P\to\mathbb R$ is a function and $h:P\to\mathbb R$ is defined by $$h(b)=\sum_{a\leq b}g(a)=\sum_{a\leq b}g(a)\zeta(a,b)$$ Then $$g(b)=\sum_{a\leq b}h(a)\mu(a,b)$$ If $P=2^A$, this is a generalization of the principle of inclusion-exclusion. To see this say we have a collection of sets $A_1,\ldots,A_k$ and we want to compute the size of $A=\bigcup_{i=1}^kA_i$. Let $P$ be the set consisting of $A$ as well as all intersections of the $A_i$ ordered by inclusion. Let $g(B)$ be the number of elements of $B$ that are not contained in any $B'\in P$ with $B'\subset B$. If $h(B)=|B|$, then $$h(B)=\sum_{B'\subseteq B}g(B')$$ Thus $$g(A)=0=\sum_{B\subseteq A}h(B)\mu(B,A)=\sum_{B\subseteq A}(-1)^{r(B)}h(B)$$ where $r(B)$ is the number of intersections of the $A_i$ required to get $B$. Thus $$h(A)=\sum_{B\subset A}(-1)^{r(B)+1}h(B)$$ which is the principle of inclusion-exclusion.

This is not exactly a determinant or eigenvalue, but it is a matrix representation.