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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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 ^^ ...)

Answer 5

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.

Answer 6

The general inclusion-exclusion fails in general for subspaces and therefore cannot be used to express the dimension of intersection of three or more subspaces in terms of dimension of sums of subspaces such as in $$\mathrm{dim}(A\cap B)=\mathrm{dim}(A)+\mathrm{dim}(B)-\mathrm{dim}(A+B).$$ However there is a formula to compute the dimension of intersection of subspaces formed by generic vectors. We discovered it while studying the list-decoding problem in coding theory.

Let $A_1,A_2,\dots,A_m\subset [n]$ be sets of size at most $d$ and let $W_{d\times n}$ be a generic $d\times n$ matrix with columns $W_1,W_2,\dots,W_n$. For $S\subset[n]$, let $W_S=\mathrm{span}\{W_i:i\in S\}$ be the subspace spanned by columns of $W$ indexed by $S$. Our goal is to compute the intersection dimension, $\mathrm{dim}(W_{A_1}\cap \cdots \cap W_{A_m})$. Note that since $W$ is generic, the intersection dimension only depends on the sets $A_1,\dots,A_m$ and $d$. If the inclusion exclusion principle were true for subspaces, we could compute the intersection dimension as: $$\mathrm{dim}(W_{A_1}\cap \cdots \cap W_{A_m})=\sum_{T\subset [m],T\ne \phi} (-1)^{|T|-1}\dim\left(\sum_{i\in T}W_{A_i}\right)\quad \text{(wrong: inclusion-exclusion)}$$ where it is easy to compute $\mathrm{dim}(\sum_{i\in T} W_{A_i})=\mathrm{dim}(W_{\cup_{i\in T} A_i})=\mathrm{min}(|\cup_{i\in T} A_i|,d).$

But we know that inclusion-exclusion doesn't hold for subspaces and this formula indeed sometimes gives the wrong answer, such as the classic example of three generic lines through origin in a plane. In this paper https://arxiv.org/abs/2206.05256 (see Theorem 1.15), Joshua Brakensiek, Visu Makam, and I proved the following correct formula for computing the intersection dimension: $$\mathrm{dim}(W_{A_1}\cap \cdots \cap W_{A_m})=\max_{P_1\sqcup \dots \sqcup P_s = [m]} \sum_{\ell=1}^s \left|\bigcap_{i\in P_\ell} A_i\right| - (s-1)d$$ where the maximum is over all partitions of $[m]$.