Matroids and Geometric Lattices

LECTURE 3 Matroids and geometric lattices 3.1. Matroids A matroid is an abstraction of a set of vectors in a vector space (for us, the normals to the hyperplanes in an arrangement). Many basic facts about arrangements (especially linear arrangements) and their intersection posets are best understood from the more general viewpoint of matroid theory. There are many equivalent ways to define matroids. We will define them in terms of independent sets, which are an abstraction of linearly independent sets. For any set S we write 2S = {T : T ∗ S}. Definition 3.8. A (finite) matroid is a pair M = (S, I), where S is a finite set and I is a collection of subsets of S, satisfying the following axioms: (1) I is a nonempty (abstract) simplicial complex, i.e., I = ⇔ �, and if J ≤ I and I ⊇ J, then I ≤ I. (2) For all T ∗ S, the maximal elements of I ⊕ 2T have the same cardinality. In the language of simplicial complexes, every induced subcomplex of I is pure. The elements of I are called independent sets. All matroids considered here will be assumed to be finite. By standard abuse of notation, if M = (S, I) then we write x ≤ M to mean x ≤ S. The archetypal example of a matroid is a finite subset S of a vector space, where independence means linear independence. A closely related matroid consists of a finite subset S of an affine space, where independence now means affine independence. It should be clear what is meant for two matroids M = (S, I) and M � = (S � , I� ) to be isomorphic, viz., there exists a bijection f : S ∃ S � such that {x1 , . . . , xj } ≤ I if and only if {f (x1 ), . . . , f (xj )} ≤ I� . Let M be a matroid and S a set of points in Rn , regarded as a matroid with independence meaning affine independence. If M and S are isomorphic matroids, then S is called an affine diagram of M . (Not all matroids have affine diagrams.) Example 3.7. (a) Regard the configuration in Figure 1 as a set of five points in the two-dimensional affine space R2 . These five points thus define the affine diagram of a matroid M . The lines indicate that the points 1,2,3 and 3,4,5 lie on straight 31 32 R. STANLEY, HYPERPLANE ARRANGEMENTS 1 5 2 4 3 Figure 1. A five-point matroid in the affine space R2 lines. Hence the sets {1, 2, 3} and {3, 4, 5} are affinely dependent in R2 and therefore dependent (i.e., not independent) in M . The independent sets of M consist of all subsets of [5] with at most two elements, together with all three-element subsets of [5] except 123 and 345 (where 123 is short for {1, 2, 3}, etc.). (b) Write I = �S1 , . . . , Sk � for the simplicial complex I generated by S1 , . . . , Sk , i.e., �S1 , . . . , Sk � = {T : T ∗ Si for some i} = 2 S1 ∅ · · · ∅ 2 Sk . Then I = �13, 14, 23, 24� is the set of independent sets of a matroid M on [4]. This matroid is realized by a multiset of vectors in a vector space or affine space, e.g., by the points 1,1,2,2 in the affine space R. The affine diagam of this matroid is given by 1,2 3,4 (c) Let I = �12, 23, 34, 45, 15�. Then I is not the set of independent sets of a matroid. For instance, the maximal elements of I ⊕ 2{1,2,4} are 12 and 4, which do not have the same cardinality. (d) The affine diagram below shows a seven point matroid. 1 2 3 LECTURE 3. MATROIDS AND GEOMETRIC LATTICES 33 If we further require the points labelled 1,2,3 to lie on a line (i.e., remove 123 from I), we still have a matroid M , but not one that can be realized by real vectors. In fact, M is isomorphic to the set of nonzero vectors in the vector space F32 , where F2 denotes the two-element field. 010 110 100 111 101 011 001 Let us now define a number of important terms associated to a matroid M . A basis of M is a maximal independent set. A circuit C is a minimal dependent set, i.e., C is not independent but becomes independent when we remove any point from it. For example, the circuits of the matroid of Figure 1 are 123, 345, and 1245. If M = (S, I) is a matroid and T ∗ S then define the rank rk(T ) of T by rk(T ) = max{#I : I ≤ I and I ∗ T }. In particular, rk(�) = 0. We define the rank of the matroid M itself by rk(M ) = rk(S). A k-flat is a maximal subset of rank k. For instance, if M is an affine matroid, i.e., if S is a subset of an affine space and independence in M is given by affine independence, then the flats of M are just the intersections of S with affine subspaces. Note that if F and F � are flats of a matroid M , then so is F ⊕ F � (see Exercise 2). Since the intersection of flats is a flat, we can define the closure T of a subset T ∗ S to be the smallest flat containing T , i.e., ⎦ T = F. flats F ∅T This closure operator has a number of nice properties, such as T = T and T � ∗ � T ⊆ T ∗ T. 3.2. The lattice of flats and geometric lattices For a matroid M define L(M ) to be the poset of flats of M , ordered by inclusion. Since the intersection of flats is a flat, L(M ) is a meet-semilattice; and since L(M ) has a top element S, it follows from Lemma 2.3 that L(M ) is a lattice, which we call the lattice of flats of M . Note that L(M ) has a unique minimal element 0̂, viz., ¯ � or equivalently, the intersection of all flats. It is easy to see that L(M ) is graded by rank, i.e., every maximal chain of L(M ) has length m = rk(M ). Thus if x � y in 34 R. STANLEY, HYPERPLANE ARRANGEMENTS 1 2 3 4 5 Figure 2. The lattice of flats of the matroid of Figure 1 L(M ) then rk(y) = 1 + rk(x). We now define the characteristic polynomial ψ M (t), in analogy to the definition (3) of ψA (t), by � ˆ x)tm−rk(x) , (22) ψM (t) = µ(0, x⊆L(M ) where µ denotes the Möbius function of L(M ) and m = rk(M ). Figure 2 shows the lattice of flats of the matroid M of Figure 1. From this figure we see easily that ψM (t) = t3 − 5t2 + 8t − 4. Let M be a matroid and x ≤ M . If the set {x} is dependent (i.e., if rk({x}) = 0) then we call x a loop. Thus ¯ � is just the set of loops of M . Suppose that x, y ≤ M , neither x nor y are loops, and rk({x, y}) = 1. We then call x and y parallel points. A matroid is simple if it has no loops or pairs of parallel points. It is clear that the following three conditions are equivalent: • M is simple. ¯ = � and x • � ¯ = x for all x ≤ M . • rk({x, y}) = 2 for all points x = ⇔ y of M (assuming M has at least two points). ¯ = ȳ. It is easy to see that ∪ is For any matroid M and x, y ≤ M , define x ∪ y if x an equivalence relation. Let (23) ¯ , � = {¯ M x : x ≤ M, x ⇔≤ �} with an obvious definition of independence, i.e., �) √ {x1 , . . . , xk } ≤ I(M ). {¯ x1 , . . . , x ¯k } ≤ I(M � is simple, and L(M ) ∪ � Thus insofar as intersection lattices L(M ) Then M = L(M). are concerned, we may assume that M is simple. (Readers familiar with point set topology will recognize the similarity between the conditions for a matroid to be simple and for a topological space to be T0 .) Example 3.8. Let S be any finite set and V a vector space. If f : S ∃ V , then define a matroid Mf on S by the condition that given I ∗ S, I ≤ I(M ) √ {f (x) : x ≤ I} is linearly independent. LECTURE 3. MATROIDS AND GEOMETRIC LATTICES 35 Then a loop is any element x satisfying f (x) = 0, and x ∪ y if and only if f (x) is a nonzero scalar multiple of f (y). Note. If M = (S, I) is simple, then L(M ) determines M . For we can identify S with the set of atoms of L(M ), and we have {x1 , . . . , xk } ≤ I √ rk(x1 ⇒ · · · ⇒ xk ) = k in L(M ). See the proof of Theorem 3.8 for further details. We now come to the primary connection between hyperplane arrangements and matroid theory. If H is a hyperplane, write nH for some (nonzero) normal vector to H. Proposition 3.6. Let A be a central arrangement in the vector space V . Define a matroid M = MA on A by letting B ≤ I(M ) if B is linearly independent (i.e., {nH : H ≤ B} is linearly independent). Then M is simple and L(M ) ∪ = L(A). Proof. M has no loops, since every H ≤ A has a nonzero normal. Two distinct nonparallel hyperplanes have linearly independent normals, so the points of M are closed. Hence M is simple. Let B, B� ∗ A, and set ⎦ ⎦ X= H = XB , X � = H = X B� . H⊆B H⊆B� Then X = X � if and only if span{nH : H ≤ B} = span{nH : H ≤ B� }. Now the closure relation in M is given by B = {H � ≤ A : nH � ≤ span{nH : H ≤ B}}. � � Hence X = X � if and only if B = B , so L(M ) ∪ = L(A). It follows that for a central arrangement A, L(A) depends only on the matroidal structure of A, i.e., which subsets of hyperplanes are linearly independent. Thus the matroid MA encapsulates the essential information about A needed to define L(A). Our next goal is to characterize those lattices L which have the form L(M ) for some matroid M . Proposition 3.7. Let L be a finite graded lattice. The following two conditions are equivalent. (1) For all x, y ≤ L, we have rk(x) + rk(y) ⊂ rk(x ∈ y) + rk(x ⇒ y). (2) If x and y both cover x ∈ y, then x ⇒ y covers both x and y. Proof. Assume (1). Let x, y � x ∈ y, so rk(x) = rk(y) = rk(x ∈ y) + 1 and rk(x ⇒ y) > rk(x) = rk(y). By (1), rk(x) + rk(y) ⊂ (rk(x) − 1) + rk(x ⇒ y) ⊆ rk(y) ⊂ rk(x ⇒ y) − 1 ⊆ x ⇒ y � x. Similarly x ⇒ y � y, proving (2). For (2)⊆(1), see [18, Prop. 3.3.2]. � 36 R. STANLEY, HYPERPLANE ARRANGEMENTS (a) (b) (c) Figure 3. Three nongeometric lattices Definition 3.9. A finite lattice L satisfying condition (1) or (2) above is called (upper) semimodular. A finite lattice L is atomic if every x ≤ L is a join of atoms (where we regard 0̂ as an empty join of atoms). Equivalently, if x ≤ L is joinirreducible (i.e., covers a unique element), then x is an atom. Finally, a finite lattice is geometric if it is both semimodular and atomic. To illustrate these definitions, Figure 3(a) shows an atomic lattice that is not semimodular, (b) shows a semimodular lattice that is not atomic, and (c) shows a graded lattice that is neither semimodular nor atomic. We are now ready to characterize the lattice of flats of a matroid. Theorem 3.8. Let L be a finite lattice. The following two conditions are equivalent. (1) L is a geometric lattice. (2) L ∪ = L(M ) for some (simple) matroid M . Proof. Assume that � � L is geometric, and let A be the set of atoms of L. If T ∗ A then write T = x⊆T x, the join of all elements of T . Let I = {I ∗ A : rk(⇒I) = #I}. � Note � that by semimodularity, we have for � any S ∗ A and x ≤ A that rk(( S)⇒x) → rk( S) + 1. (Hence in particular, rk( S) → #S.) It follows that I is a simplicial complex. Let S ∗ A, and let T, T � be maximal elements of 2S ⊕ I. We need to show that #T = #T � . � #T < #T � , say. If y ≤ S then y → T � , else T �� = T � ∅ y satisfies �Assume the maximality of T � . Since #T < #T � and T ∗ S, rk( T �� ) = #T��� , contradicting � � it follows that � T < T [why?]. � Since L is atomic, there exists y ≤ S such that y ≤ S but y ⇔→ T . But then rk( (T ∅ y)) = 1 + #T , contradicting the maximality of T . Hence M = (A, I) is a matroid, and L ∪ = L(M ). Conversely, given a matroid M , which we may assume is simple, we need to show that L(M ) is a geometric lattice. Clearly L(M ) is atomic, since every flat is the join of its elements. Let S, T ∗ M . We will show that (24) rk(S) + rk(T ) ⊂ rk(S ⊕ T ) + rk(S ∅ T ). LECTURE 3. MATROIDS AND GEOMETRIC LATTICES 37 Note that if S and T are flats (i.e., S, T ≤ L(M )) then S ⊕ T = S ∈ T and rk(S ∅ T ) = rk(S ⇒ T ). Hence taking S and T to be flats in (24) shows that L(M ) is semimodular and thus geometric. Suppose (24) is false, so rk(S ∅ T ) > rk(S) + rk(T ) − rk(S ⊕ T ). Let B be a basis for S ∅T extending a basis for S ∅T . Then either #(B ⊕S) > rk(S) � or #(B ⊕ T ) > rk(T ), a contradiction completing the proof. Note that by Proposition 3.6 and Theorem 3.8, any results we prove about geo­ metric lattices hold a fortiori for the intersection lattice LA of a central arrangement A. Note. If L is geometric and x → y in L, then it is easy to show using semimodularity that the interval [x, y] is also a geometric lattice. (See Exercise 3.) In general, however, an interval of an atomic lattice need not be atomic. For noncentral arrangements L(A) is not a lattice, but there is still a connection with geometric lattices. For a stronger statement, see Exercise 4. Proposition 3.8. Let A be an arrangement. Then every interval [x, y] of L(A) is a geometric lattice. ˆ Now [0, ˆ y] ∪ Proof. By Exercise 3, it suffices to take x = 0. = L(Ay ), where Ay is given by (6). Since Ay is a central arrangement, the proof follows from Proposi­ tion 3.6. � The proof of our next result about geometric lattices will use a fundamental formula concerning Möbius functions known as Weisner’s theorem. For a proof, see [18, Cor. 3.9.3] (where it is stated in dual form). Theorem 3.9. Let L be a finite lattice with at least two elements and with Möbius 0= ⇔ a ≤ L. Then function µ. Let ˆ � µ(x) = 0. (25) x : x∞a=1̂ Note that Theorem 3.9 gives a “shortening” of the recurrence (2) defining µ. Normally we take a to be an atom, since that produces fewer terms in (25) than choosing any b > a. As an example, let L = Bn , the boolean algebra of all subsets of [n], and let a = {n}. There are two elements x ≤ Bn such that x ⇒ a = 1̂ = [n], ˆ x1 ] = Bn−1 and viz., x1 = [n − 1] and x2 = [n]. Hence µ(x1 ) + µ(x2 ) = 0. Since [0, n ˆ ˆ [0, x2 ] = Bn , we easily obtain µBn (1) = (−1) , agreeing with (4). If x → y in a graded lattice L, write rk(x, y) = rk(y) − rk(x), the length of every saturated chain from x to y. The next result may be stated as “the Möbius function of a geometric lattice strictly alternates in sign.” Theorem 3.10. Let L be a finite geometric lattice with Möbius function µ, and let x → y in L. Then (−1)rk(x,y) µ(x, y) > 0. Proof. Since every interval of a geometric lattice is a geometric lattice (Exercise 3), ˆ ˆ it suffices to prove the theorem for [x, y] = [0, 1]. The proof is by induction on the ˆ = −1. Assume the result rank of L. It is clear if rk(L) = 1, in which case µ(ˆ 0, 1) for geometric lattices of rank < n, and let rk(L) = n. Let a be an atom of L in Theorem 3.9. For any y ≤ L we have by semimodularity that rk(y ∈ a) + rk(y ⇒ a) → rk(y) + rk(a) = rk(y) + 1. 38 R. STANLEY, HYPERPLANE ARRANGEMENTS Hence x ⇒ a = ˆ 1 if and only if x = ˆ 1 or x is a coatom (i.e., x � ˆ 1) satisfying a ⇔→ x. From Theorem 3.9 there follows � ˆ =− µ(ˆ 0, 1) µ(ˆ 0, x). a∈⊇x�1̂ The sum on the right is nonempty since L is atomic, and by induction every x 0, x) > 0. Hence (−1)n µ(ˆ 0, ˆ 1) > 0. � indexing the sum satisfies (−1)n−1 µ(ˆ Combining Proposition 3.8 and Theorem 3.10 yields the following result. Corollary 3.4. Let A be any arrangement and x → y in L(A). Then (−1)rk(x,y) µ(x, y) > 0, where µ denotes the Möbius function of L(A). Similarly, combining Theorem 3.10 with the definition (22) of ψM (t) gives the next corollary. Corollary 3.5. Let M be a matroid of rank n. Then the characteristic polynomial ψM (t) strictly alternates in sign, i.e., if ψM (t) = an tn + an−1 tn−1 + · · · + a0 , then (−1)n−i ai > 0 for 0 → i → n. Let A be an n-dimensional arrangement of rank r. If MA is the matroid corresponding to A, as defined in Proposition 3.6, then (26) ψA (t) = tn−r ψM (t). It follows from Corollary 3.5 and equation (26) that we can write ψA (t) = bn tn + bn−1 tn−1 + · · · + bn−r tn−r , where (−1)n−i bi > 0 for n − r → i → n.