Grassmann’s dimension formula, its analogies and where they stop

This week my pupils proved Grassmann’s dimension formula. For subspaces W and Y of a finite-dimensional vector space,

dim( W + Y ) + dim( W ∩ Y ) = dim W + dim Y.

The join plus the meet is the sum of the parts. Where else is that true?

• Sets|A ∪ B| + |A ∩ B| = |A| + |B|
• Topologyχ( A ∪ B ) + χ( A ∩ B ) = χ( A ) + χ( B )
• Groups|HK| · |H ∩ K| = |H| · |K|
• Matroidsr( A ∪ B ) + r( A ∩ B ) ≤ r( A ) + r( B )

For finite sets it is the first case of inclusion–exclusion. For the Euler characteristic of subcomplexes it is the numerical shadow of the Mayer–Vietoris sequence. For subgroups H and K of a finite group the law holds even when HK is not a subgroup; for subspaces over a field with q elements, HK is the sum and |W| = q^{dim W}, so logarithms to the base q give Grassmann’s formula exactly. In Whitney’s matroids only the inequality survives, r being the rank (for vectors, the dimension of their span): with A = {e₁, e₂} and B = {e₁ + e₂} in the plane, it reads 2 + 0 < 2 + 1.

The equalities share a name: a function v on a lattice is a valuation if

v( x ∨ y ) + v( x ∧ y ) = v( x ) + v( y ),

where ∨ is the join and ∧ the meet. Counting is a valuation on the subsets of a finite set, probability on events, dimension on subspaces; matroid rank, with only ≤, is called submodular. Banach’s remark, as Ulam recalled it, heads the foreword to Analogies between Analogies: ‘Good mathematicians see analogies between theorems or theories, the very best ones see analogies between analogies.’

How far does the analogy go? Subsets form a distributive lattice, so inclusion–exclusion holds for any number of sets. Subspaces form a lattice that is modular but not distributive, and inclusion–exclusion for dimension stops at two. Take three distinct lines L₁, L₂ and L₃ through the origin of a plane. Then L₁ ∩ ( L₂ + L₃) = L₁, but ( L₁ ∩ L₂) + ( L₁ ∩ L₃) = 0; and inclusion–exclusion for three would give the dimension 1 + 1 + 1 − 0 − 0 − 0 + 0 = 3, though the lines span only a plane. Pairwise conditions are not enough either: the lines meet pairwise in 0, yet their sum is not direct. So it is with independence: for two fair coins, ‘first heads’, ‘second heads’ and ‘the coins agree’ are pairwise independent, yet all three happen with probability 1/4, not 1/8.

The proof of the formula shows why two subspaces are safe. Extend a basis of W ∩ Y once to a basis B of W and once to a basis C of Y. Then B ∩ C is a basis of W ∩ Y and B ∪ C a basis of W + Y, and the formula is inclusion–exclusion for B and C. But no basis of the plane contains a basis of each of the three lines: it has two vectors, and each line would need one of its own.

Past this point the question is how many configurations there are, up to invertible linear maps. Two subspaces have no parameters; three fall into finitely many indecomposable types, a case of Gabriel’s theorem of 1972. Four do not. Four distinct lines through the origin of a plane, taken in order, can be moved to y = 0, x = 0, y = x and x = λy, and λ can be changed no further, as only scalars fix each of the first three lines. This λ is the cross-ratio of the four lines, and two such quadruples are related by an invertible linear map exactly when their cross-ratios agree. The lines meet pairwise in 0 and pairwise span the plane: dimensions and intersections no longer determine the configuration. The four-subspace problem was solved by L. A. Nazarova in 1967 and, independently, by I. M. Gelfand and V. A. Ponomarev in a paper given at Tihany in 1970. From five on, the problem is wild: it contains the classification of pairs of matrices up to simultaneous similarity.

Here is what my pupils took from it. One fact, that subspaces form a modular but not a distributive lattice, met us three times in one seminar, and each time three was where the likeness to sets ran out.

Two subspaces behave like two sets.
Three need not.