# 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.

• See also the comments to the post Qiaochu links; the original post is not correct. – David E Speyer Mar 10 '10 at 17:42
• Nice to see my words get a second airing... ;) – Yemon Choi Mar 10 '10 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. – Jonas Meyer Mar 10 '10 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)". – Kevin Buzzard Mar 10 '10 at 23:11
• Indeed it is one of the favourite wrong common beliefs on MO mathoverflow.net/questions/23478/… – Andrea Ferretti Jun 1 '10 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.) – PersonX Jun 9 '10 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 Jun 21 '10 at 18:23
• This is an interesting application of chain complexes for linear algebra! I like it very much! – Patrick Da Silva Jan 30 '19 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. – Peter Shor Mar 14 '10 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. (I am too lazy to draw $D_4$ on MO, sorry!). 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 just wanted to point out, for other readers, the excellent paper by Gian-Carlo Rota "On the foundations of combinatorial theory I. Theory of Möbius function"

http://www.maths.ed.ac.uk/~aar/papers/rota1.pdf

The paper somehow sets up the proper framework to generalize the inclusion-exclusion principle (which is basically a special case of Möbius inversion).

(I wanted to make a comment following Shor's answer, but it seems I don't have enough reputation credit ^^ ...)

The question immediately reminded me of this answer to the famous post of "Examples of common false beliefs in mathematics". Obviously, it does not answer the question, but I believe it adds something informative and worthy.