# Is there a version of inclusion/exclusion for vector spaces?

I am asking for a way to compute the rank of the 'join' of a bunch of subspaces whose pairwise intersections might be non-zero. So in the case n=2 this is just $\dim(A_1+A_2) = \dim(A_1) + \dim(A_2) - \dim(A_1\cap A_2)$. For general $n$, I don't know a good formula.

• Nice to see my words get a second airing... ;) Commented Mar 10, 2010 at 18:08
• To those who haven't seen it, this is a redo of mathoverflow.net/questions/17702. Most of the wording here is copied from Yemon's comment there. Commented Mar 10, 2010 at 20:04
• The example already kicking around (the spaces generated by v,w,v+w vs the spaces generated by e1,e2,e3) already shows that dim(A1+A2+A3) cannot be computed from the dimensions of sum_{i in I}A_i for I running through all the proper subsets of {1,2,3}, and cap_{i in I}A_i for all I. So what is left of this question? Isn't the answer "if you only allow dim(sum_{i in I}A_i) etc then there's no formula, and if you allow more general things then the answer is that it's dim(A1+A2+A3)". Commented Mar 10, 2010 at 23:11
• Indeed it is one of the favourite wrong common beliefs on MO mathoverflow.net/questions/23478/… Commented Jun 1, 2010 at 15:56

As the blog link points out, for any finite collection of subspaces U_1,...,U_n there's a chain complex

$$0 \to \cap U_i \to \ldots \to \bigoplus U_i \cap U_j \cap U_k \to \bigoplus U_i \cap U_j \to \bigoplus U_i \to \sum U_i \to 0$$

where the rth term after the left hand zero is the external direct sum of (n-r+1)-fold intersections of U_i's. The differential sends $$x \in U_{i_1} \cap \cdots \cap U_{i_r}$$ to $$\sum_j (-1)^j (x \in U_{i_1} \cap \cdots \hat{U_{i_j}} \cap \cdots \cap U_{i_r})$$

Failure of "inclusion-exclusion for vector spaces" is failure of exactness of this sequence. For example, for three subspaces the only non-trivial homology is H^1 which is $(U \cap (V+W))/(U\cap V + U \cap W)$ i.e. it measures failure of distributivity.

You can find out what the Euler characteristic of the sequence is by repeatedly using the formula for dim(U+V). What this gives for 4 subspaces is that the alternating sum of Betti numbers is

$$|((U \cap V) \cap (U\cap W + U \cap X)) / (U \cap V \cap W + U \cap V \cap X) |$$ minus the sum of $$| (V \cap (W+X))/(V \cap W + V \cap X) |$$ and $$| ( U \cap (V+W+X) )/ (U\cap V + U\cap W + U \cap X) |$$

where I've written |s for "dim". First homology is the direct sum $$( U \cap (V+W+X) )/ (U\cap V + U\cap W + U \cap X) \oplus (V \cap (W+X))/(V \cap W + V \cap X)$$

Example1: 4 planes in R^3, with the intersection of any 3 being {0}. Then 2nd homology is 1-dim and 1st homology is zero. Euler char is 3-8+6=1.

Example2: 4 planes in R^3, three of which meet in a line, the other in "general position". Euler char 3-8+6-1=0, no homology.

This ought to be part of some kind of homology theory for subspace configurations, but it doesn't seem to be in the literature.

Disclaimer: this is all from some ancient notes of mine, and I can't vouch for how reliable it is

• One reference for this is Section 1.7 of the book Quadratic Algebras, by A. Polishchuk and L. Positselski. (ams.org/bookstore-getitem/item=ulect-37) (I think I've seen the second author on Math Overflow.) Commented Jun 9, 2010 at 20:04
• for those who don't have access to this book, what they prove (amongst other things) is that if you have a finite set S of subspaces every proper subset of which is distributive (this fails in my Example 2), then S is distributive if and only if the complex above is exact.
– M T
Commented Jun 21, 2010 at 18:23
• This is an interesting application of chain complexes for linear algebra! I like it very much! Commented Jan 30, 2019 at 12:26

What goes wrong with a proof of inclusion-exclusion, as was tried in the post that Qiaochu links to, is that $A \cap (B + C) \neq (A \cap B) + (A \cap C)$. You might be able to get a useful expression for the dimension of the join of a bunch of subspaces by looking at the dimension of more complicated spaces expressed using meets and joins.

In the paper "A Quantum Lovasz Local Lemma" (arxiv link; don't be scared by the "quantum" in the title -- the motivation is quantum, but the theorems are just about dimensions of joins, meets, and complements of subspaces) there is a definitely non-trivial theorem proved about dimensions of spaces using this calculus of meets and joints. So depending on what you want it for, you might be able to find some interesting expressions for the dimension of the join of a set of spaces.

• I wasn't as clear as I should have been in my answer. Both the Lovasz Local Lemma and the inclusion-exclusion principle are theorems about probability. If you express the Lovasz Local Lemma properly, it generalizes to meets and joins of subspaces. (You have to replace some quantities in the usual formulation by their complements; the reformulated statement is equivalent for probability distributions). We don't know how to do that for inclusion-exclusion. But there might be a more complicated, equivalent, statement which generalizes to meets, joins, and orthogonal complements of subspaces. Commented Mar 14, 2010 at 17:14

One way to look at this question is via quiver representations. Two subspaces of a vector space form a representation of the quiver $$A_3$$ with orientations $$\bullet \rightarrow \bullet \leftarrow \bullet$$ with the additional condition that both maps are injective (that's tautology). Now, every representation of $$A_3$$ is a sum of indecomposables, whose dimension vectors are (1,0,0), (0,1,0), (0,0,1), (1,1,0), (0,1,1), (1,1,1), where for the first and the third one the maps are not injective, and for the remaining four the maps are injective. Thus, the dimension vector for a generic representation with injective maps is a(0,1,0)+b(1,1,0)+c(0,1,1)+d(1,1,1)=(b+d,a+b+c+d,c+d). Clearly, the dimension of the sum of the two subspaces is b+c+d (the complement is represented by the first summand a(0,1,0)), which is (b+d)+(c+d)-d, and d is the dimension of the intersection.

Now, for the three subspaces we deal with representations of the quiver $$D_4$$ with injective maps: \begin{align} & \bullet\\ & \big\downarrow\\ \bullet \longrightarrow &\bullet\longleftarrow \bullet \end{align} Indecomposable representations have dimension vectors $$(d_1,d_2,d_3,d)$$ (note different ordering of dimensions - the largest one is the last one) being (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (1,0,0,1), (0,1,0,1), (0,0,1,1), (1,1,0,1), (1,0,1,1), (0,1,1,1), (1,1,1,1), (1,1,1,2) - altogether 12 vectors. Among them, the first three have non-injective maps, and the fourth one captures the complement of the sum of our three subspaces. Thus, there are 8 numbers through which the dimension can be expressed (not 7, as in the inclusion-exclusion formula), and what remains is to choose the 8th number, in addition to the dimensions of all possible intersections, reasonably for your needs.

For $$k>3$$ subspaces the classification problem stops being of finite type so it becomes a bit more nasty...

• I like you line of proof (+1). Cannot this be reformulated as "In order that a collection of subspaces in a f.d. space satisfy the dimension formula, it is necessary and sufficient that they generate a distributive sublattice of that of subspaces" i.e. "that the set of atoms of the sublattice generated be in direct sum position" ? Commented Nov 21, 2021 at 9:00
• I put a depiction of the quiver $D_4$ in. I messed around with alignment until it looked about right.