The Unapologetic Mathematician

Mathematics for the interested outsider

The Inclusion-Exclusion Principle

In combinatorics we have a method of determining the cardinality of unions in terms of the sets in question and their intersection: the Inclusion-Exclusion Principle. Predictably enough, this formula is reflected in the subspaces of a vector space. We could argue directly in terms of bases, but it’s much more interesting to use the linear algebra we have at hand.

Let’s start with just two subspaces V and W of some larger vector space. We’ll never really need that space, so we don’t need to give it a name. The thing to remember is that V and W might have a nontrivial intersection — their sum may not be direct.

Now we consider the sum of the subspaces. Every vector in V+W is the sum of a vector in V and a vector in W. This tells us that there’s a linear map f_1:V\oplus W\rightarrow V+W defined by f_1(v,w)=v+w. Note carefully that this is linear as a function of the pair (v,w). It’s not bilinear — linear in each of v and w separately — which would mean bringing in the tensor product.

This function is always surjective, but it may fail to be injective. Specifically, if V and W have a nontrivial intersection then it gives us a nontrivial kernel. If x\in V\cap W then f_1(x,-x)=0. But rather than talk about elements, let’s use the intersection to parametrize the kernel! We’ve got another linear map f_2:V\cap W\rightarrow V\oplus W, defined by f_2(x)=(x,-x).

Now it’s clear that f_2 has a trivial kernel. On the other hand, its image is precisely the set of pairs that f_1 kills off. That means we’ve got an exact sequence:

\mathbf{0}\rightarrow V\cap W\xrightarrow{f_2}V\oplus W\xrightarrow{f_1}V+W\rightarrow\mathbf{0}

Taking the Euler characteristic we find that

\dim\left(V\cap W\right)-\dim\left(V\oplus W\right)+\dim\left(V+W\right)=0

Some simple juggling turns this into

\dim\left(V+W\right)=\dim\left(V\right)+\dim\left(W\right)-\dim\left(V\cap W\right)

which is the inclusion-exclusion principle for two subspaces.

What about three subspaces U, V, and W? We start off again with

U\oplus V\oplus W\xrightarrow{f_1}U+V+W\rightarrow\mathbf{0}

defined by f_1(u,v,w)=u+v+w. Then the kernel contains triples like (0,x,-x), (-y,0,y), and (z,-z,0). We use the pairwise intersections to cover the kernel by the map

\left(V\cap W\right)\oplus\left(W\cap U\right)\oplus\left(U\cap V\right)\xrightarrow{f_2}U\oplus V\oplus W

defined by (x,y,z)=(z-y,x-z,y-x). The image of f_2 is exactly the kernel of f_1, but this time it has a nontrivial kernel itself! Now we need another map

\mathbf{0}\rightarrow U\cap V\cap W\xrightarrow{f_3}\left(V\cap W\right)\oplus\left(W\cap U\right)\oplus\left(U\cap V\right)

defined by f_3(t)=(t,t,t). Now f_3 is injective, and its image is exactly the kernel of f_2. We stick these maps all together to have the long exact sequence

\begin{aligned}\mathbf{0}\rightarrow U\cap V\cap W\xrightarrow{f_3}\left(V\cap W\right)\oplus\left(W\cap U\right)\oplus\left(U\cap V\right)\\\xrightarrow{f_2}U\oplus V\oplus W\xrightarrow{f_1}U+V+W\rightarrow\mathbf{0}\end{aligned}

Taking the Euler characteristic and juggling again we find

\begin{aligned}\dim\left(U+V+W\right)=\dim\left(U\right)+\dim\left(V\right)+\dim\left(W\right)\\-\dim\left(U\cap V\right)-\dim\left(U\cap W\right)-\dim\left(V\cap W\right)\\+\dim\left(U\cap V\cap W\right)\end{aligned}

We include the dimensions of the individual subspaces, exclude the dimensions of the pairwise intersections, and include back in the dimension of the triple intersection.

For larger numbers of subspaces we can construct longer and longer exact sequences. The kth term consists of the direct sum of the intersections of the subspaces, taken k at a time. The kth map consists of including each k-fold intersection into each of the (k-1)-fold intersections it lies in, with positive and negative signs judiciously sprinkled throughout to make the sequence exact.

The result is that the dimension of a sum of subspaces is the alternating sum of the dimensions of the k-fold intersections. First add the dimension of each subspace, then subtract the dimension of each pairwise intersection, then add back in the dimension of each triple intersection, and so on.

From here it’s the work of a moment to derive the combinatorial inclusion-exclusion principle. Given a collection of sets, just construct the free vector space on each of them. These free vector spaces will have nontrivial intersections corresponding to the nonempty intersections of the sets, and we’ve got canonical basis elements floating around to work with. Then all these dimensions we’re talking about are cardinalities of various subsets of the sets we started with, and the combinatorial inclusion-exclusion principle follows. Of course, as I said before we could have proved it from the other side, but that would require a lot of messy hands-on work with bases and such.

The upshot is that the combinatorial inclusion-exclusion principle is equivalent to the statement that exact sequences of vector spaces have trivial Euler characteristic! This little formula that we teach in primary or secondary school turns out to be intimately connected with one of the fundamental tools of homological algebra and the abstract approach to linear algebra. Neat!

July 24, 2008 Posted by | Algebra, Linear Algebra | 13 Comments



Get every new post delivered to your Inbox.

Join 366 other followers