Guest post by Cameron Marcott

The goal of this post is to introduce flag manifolds and common decompositions of them, and to explain how matroids serve as combinatorial models for these geometric objects. We illustrate how decompositions of flag manifolds can provide examples of interesting classes of Coxeter matroids. We shall also make effort to point out several matroidal facts which are direct translations of geometric facts. Over the course of this post, we will explain the following correspondences between geometric and matriodal objects.
$$\begin{array}{c|c}
\mathbf{geometry} & \mathbf{matroids} \\ \hline\hline
\mbox{points in } \mathrm{Gr}(k,n) & \mbox{rank-$k$, $\mathbb{R}$-representable matroids} \\\hline
\mbox{Schubert cells} & \mbox{nested matroids} \\\hline
\mbox{Richardson cells} & \mbox{lattice path matroids} \\\hline
\mbox{positroid cells} & \mbox{positroids} \\\hline
\mbox{points in } \mathrm{F}\ell(n) & \mbox{$\mathbb{R}$-representable full flag matroids}
\end{array}$$

1. The Grassmannian

The Grassmannian $\mathrm{Gr}(k,n)$ is the geometric object whose points are $k$-dimensional vector subspaces of $\mathbb{R}^n$. Any $k$-dimensional subspace of $\mathbb{R}^n$ may be interpreted as the row space of a full rank $k \times n$ matrix. Such a matrix represents a matroid in the usual fashion. Hence, any point in $\mathrm{Gr}(k,n)$ naturally represents a rank-$k$ matroid (two $k \times n$ matrices have the same row span if and only if they are related by elementary row operations, and elementary row operations preserve the matroid represented by a matrix, so this correspondence is well defined).

A common technique to study the geometry of $\mathrm{Gr}(k,n)$ is to decompose it into simpler geometric spaces. One may think of all these decompositions fancy versions of the familiar decomposition of the projective line into a line and a point at infinity. The most common of these decompositions is the Schubert decomposition. Of all of the matrices representing a given point in $\mathrm{Gr}(k,n)$, there is a unique representative in reduced row echelon form. A Schubert cell consists of all of the points in $\mathrm{Gr}(k,n)$ whose reduced row echelon representative has a fixed shape.

Definition 1. Given a set $S \in \binom{[n]}{k}$, the Schubert cell $X_{S}$ consists of all $V \in \mathrm{Gr}(k,n)$ which are the row space of a $k \times n$ matrix whose set of pivot columns is $S$ when written in reduced row echelon form.

Choosing a generic point in a Schubert cell $X_{S}$ and asking what matroid it represents, one always expects to see the same matroid (more rigorously, a dense open subset of $X_{S}$ represents the same matroid). To see what this matroid is, consider the partial order on $\binom{[n]}{k}$ where if $S = \{s_1 < s_2 < \cdots < s_k\}$ and $T = \{t_1 < t_2 < \cdots < t_k\}$, then $S \leq T$ if and only if $s_i \leq t_i$ for each $i$. Looking at a matrix representing a point in $X_{S}$, any set of columns indexed by $T$ with $S \nleq T$ will certainly be linearly dependent. Any other set of columns, we expect to be linearly independent (the vanishing of the square determinant indexed by a set of columns carves out a subset of the Schubert cell of dimension strictly lower than that of the Schubert cell, the compliment of this lower dimensional set is dense in the Schubert cell and is hence “generic”, the set of columns under consideration is thus linearly independent at a generic point). Hence, the matroid associated to a generic point in $X_{S}$ has basis set $\left\{ B \in \binom{[n]}{k} : S \leq B \right\}$. These matroids have been studied under the names “shifted matroids” or “nested matroids.”

Example 2. Let $n = 6$, $k = 3$, and $S = \{1,2,4\}$. Then, $X_{S}$ consists of all matrices of the form $$\left( \begin{array}{cccccc}
1 & 0 & \ast & 0 & \ast & \ast \\
0 & 1 & \ast & 0 & \ast & \ast \\
0 & 0 & 0 & 1 & \ast & \ast
\end{array}\right),$$ where the asterisks may be filled in with any real number. Filling in the asterisks randomly, we expect any set of three columns aside from $\{1,2,3\}$ to be linearly independent. Hence, a generic point in $X_{S}$ represents the matroid whose bases are all three element subsets of $[6]$ which are $\geq \{1,2,4\}$.

A common refinement of the Schubert decomposition is the Richardson decomposition. The opposite reduced row echelon form of a matrix is the matrix one gets by performing Gaussian elimination starting at the rightmost column and working their way left, as a left handed person, or Hebrew speaker might be tempted to do. The opposite Schubert cell $X^{T}$ consists of the points in $\mathrm{Gr}(k,n)$ whose unique opposite reduced row echelon representative has pivot columns indexed by the set $T$. Finally, the Richardson cell $X^{T}_{S}$ is defined to be the intersection $X^T \cap X_S$.

Just as generic points in Schubert cells defined a class of matroids, generic points in Richardson cells define their own class of matroids. The matroid associated to a generic point in $X^{T}_{S}$ has basis set $\left\{ B \in \binom{[n]}{k} : S \leq B \leq T \right\}$. These matroids were introduced and studied independent of this geometric motivation under the name of lattice path matroids.

Example 3. Let $n = 6$, $k = 3$, $S = \{1,2,4\}$, and $T = \{4,5,6\}$. Then, the matroid defined by a generic point in $X^{T}_{S}$ has bases
$$\left\{ B \in \binom{[n]}{k} : \{1,2,4\} \leq B \leq \{4,5,6\} \right\}.$$ This matroid is exactly the same as the matroid from Example 2. In general, all shifted matroids are also lattice path matroids. This fact mirrors the geometric fact that all Schubert varieties are also Richardson varieties (Schubert and Richardson varieties are the closure of Schubert and Richardson cells respectively).

At this point, it might be tempting to try to decompose the Grassmannian into cells where each cell consists all of the points representing a given matroid. This decomposition is known as the “thin Schubert decomposition,” or “GGMS decomposition” (after Gelfand, Goresky, MacPherson, and Serganova). While the idea is appealing, this decomposition turns out to be a geometric nightmare. Mnev’s universality theorem says roughly that these cells can be as poorly behaved as any real semialgebraic set (a set carved out of $\mathbb{R}^n$ by a set of polynomial equations and inequalities). This universality theorem has inspired, among other things, “Murphy’s law” results by Vakil, the name of which should give a sense of how poorly behaved GGMS cells can be.

Our final example of a class of matroids associated to a decomposition of the Grassmannian are positroids, which provide a geometrically tractable, but still matroidal, refinement of both the Schubert and Richardson decompositions. Though it is not perspective we take, we mention that the name positroid comes from the fact positroids are exactly the matroids representable by a $k \times n$ real matrix where every $k \times k$ minor is non-negative. To define a positroid cell, one starts by specifying which reduced row echelon shape a matrix representing a point in the positroid cell should have, just as with defining a Schubert cell. Then, one cyclically rotates the columns so they are now ordered $2,3,\dots, n,1$ instead of $1,2, \dots, n$ and specifics which reduced row echelon shape the matrix should have with this new basis ordering. One repeats this process, specifying a reduced row echelon shape for every cyclic rotation of $1,2,\dots,n$. The set of points in $\mathrm{Gr}(k,n)$ obeying these restrictions is called a positroid cell. Positroid cells are indexed by families of $n$ sets $(S_1, S_2, \dots, S_n)$ obeying a set of restrictions coming from the fact that it must be possible for a $k \times n$ matrix to have pivot columns $S_i$ after applying the $i$th cyclic rotation to its columns for every $i$ ($n$-tuples of sets obeying these restrictions are called Grassmann necklaces). Positroids may then be defined to be the matroids represented by generic points in positroid cells.

Example 4. Let $n = 6$. We write sets without curly brackets or commas to save on space. Consider the 6-tuple of sets
$$\mathcal{S} = (124,234,346,456,562,612).$$ Consider a matrix representing a generic point in postroid variety defined by $\mathcal{S}$. Since it has pivot columns 124 in the standard basis ordering, we expect every set aside from 123 to be independent, as in Example 2. Cyclically rotating the columns of our matrix and writing it in reduced row echelon form, the pivot columns are now 234 (the first, second and third columns in our new ordering). From this data, we have no reason to believe any set of three columns should be dependent. Rotating again, the pivot columns are now 346 (the first, second, and fourth columns). From this data, we see that 345 joins 124 as a dependent set, and we still have no reason to believe any other three element subset is dependent. Continuing in this way, we see that the 3-element dependent sets of the matroid defined by a generic point in this positroid variety are exactly $\{123,345,561\}$. So, the positroid is the rank-3 whirl, $\mathcal{W}^3$. It can be checked that this matroid is not a lattice path matroid. It is an interesting exercise to show that all lattice path matroids are positroids (mirroring the geometric fact that Richardson varieties are positroid varieties). As this example demonstrates, the converse does not hold.

2. The full flag manifold

The Grassmannian is the simplest example of a class of manifolds known as flag manifolds. Given a construction on the Grassmannian, one of the first questions asked by a geometer working in this area is “Does this construction generalize to other flag manifolds?” For the sake of this post, we will focus on generalizing the constructions from the previous section to the full flag manifold $\mathrm{F}\ell(n)$. Just as matroids served as a combinatorial model for points in $\mathrm{Gr}(k,n)$, full flag matroids will serve as a combinatorial model for points in $\mathrm{F}\ell(n)$. In general, the combinatorial model for points in other flag varieties are Coxeter matroids. Other flag manifolds come with Schubert and Richardson stratifications similar to the one described above, and tractable classes of Coxeter matroids could be obtained by studying the Coxeter matroids associated to these stratifications. For now, we play this game just for $\mathrm{F}\ell(n)$ and full flag matroids. However, it should be possible to find well behaved classes of Lagrangian matroids by considering Schubert cells in Lagrangian Grassmannians, classes of orthogonal matroids by considering Schubert cells in orthogonal Grassmannians, etc..

Flag manifolds generalize Grassmannians. The full flag manifold $\mathrm{F}\ell(n)$ is the space whose points are flags of subspaces $\{0\} = V_0 \subset V_1 \subset \cdots \subset V_n = \mathbb{R}^n$. This space may profitably be thought of as the subspace of $$\mathrm{Gr}(0,n) \times \mathrm{Gr}(1,n) \times \cdots \times \mathrm{Gr}(n,n)$$ consisting of points $(V_0, V_1, \dots, V_n)$ such that $V_i$ is a subspace of $V_j$ for all $i \leq j$. Just as points in $\mathrm{Gr}(k,n)$ were represented by $k \times n$ matrices, points in $\mathrm{F}\ell(n)$ may be represented by full rank $n \times n$ matrices where $V_1$ is the span of the first row, $V_2$ span of the first two rows, and so on. Just as two $k \times n$ matrices represent the same point in $\mathrm{Gr}(k,n)$ if and only if they are related by elementary row operations, two $n \times n$ matrices represent the same point in $\mathrm{F}\ell(n)$ if and only if they are related by the action of an upper triangular matrix. There is a natural projection from $\mathrm{F}\ell(n)$ to $\mathrm{Gr}(k,n)$ which sends a flag to its $k$-dimensional component.

Now, we wish to find a combinatorial object which plays the same role for $\mathrm{F}\ell(n)$ that matroids play for $\mathrm{Gr}(k,n)$. Since $$\mathrm{F}\ell(n) \subseteq \mathrm{Gr}(0,n) \times \mathrm{Gr}(1,n) \times \cdots \times \mathrm{Gr}(n,n),$$ our combinatorial object should consist of a subset of tuples $(\mathcal{M}_0, \mathcal{M}_1, \dots, \mathcal{M}_n)$ where $\mathcal{M}_i$ is a rank $i$ matroid for each $i$. Consider the restriction that for all $i < j$ that $V_i$ is a subspace of $V_j$. Given a linearly dependent set of points in $V_j$, we may project it to $V_i$. The set of points remains linearly dependent after preforming this projection. On the matriodal level, this fact tells us that any cycle of $\mathcal{M}_j$ should also be a cycle of $\mathcal{M}_i$. That is, $\mathcal{M}_i$ is a quotient of $\mathcal{M}_j$. This observation inspires the definition of a full flag matroid. Definition 5. A full flag matroid is a collection $(\mathcal{M}_0, \mathcal{M}_1, \dots, \mathcal{M}_n)$ such that for any $0 \leq i \leq n$ and any $j > i$, $\mathcal{M}_i$ is a rank $i$ matroid on the ground set $[n]$ and $\mathcal{M}_i$ is a quotient of $\mathcal{M}_j$.

When working with flag matroids, rather than thinking of bases, we think of flags of sets $\emptyset = B_0 \subset B_1 \subset \cdots \subset B_n = [n]$ such that $B_k$ is a basis of $\mathcal{M}_k$ for each $i$. We use the short hand $B_{\bullet}$ to denote a flag of sets. By a minor abuse of language, we call these flags $B_{\bullet}$ the bases of the flag matroid. Flags of sets will be represented by permutations by the map (for example): $$214365 \mapsto \emptyset \subset \{2\} \subset \{1,2\} \subset \{1,2,4\} \subset \cdots \subset \{1,2,3,4,5,6\}.$$ Any flag matroid $(\mathcal{M}_0, \mathcal{M}_1, \dots, \mathcal{M}_n)$ may be projected to the rank-$k$ matroid $\mathcal{M}_k$. Thinking in terms of bases, one may verify that the bases of $\mathcal{M}_k$ are exactly the $k$-element sets that occur as the $k$ element component of some basis of the flag matroid $B_{\bullet}$.

Points in $\mathrm{F}\ell(n)$ represent full flag matroids in a way analogous to the way that points in $\mathrm{Gr}(k,n)$ represent matroids. So, any point in $\mathrm{F}\ell(n)$ represents the full flag matroid, whose elements are flags of sets $B_{\bullet}$ such that $B_i$ is a basis of the matroid defined by $F_i$ for each $i$.

Just like the Grassmannian, $\mathrm{F}\ell(n)$ comes with Schubert and Richardson stratifications. The descriptions of Schubert and Richardson cells in $\mathrm{F}\ell(n)$, while not terribly difficult, is a little hard to absorb for a blog post. So, we just define the flag matroids associated to generic points in these spaces. The interested reader may find descriptions of the geometric spaces in [KLS13].

Let $\sigma$ be a permutation representing the flag $S_{\bullet}$. Just as the matroids associated to Schubert varieties in $\mathrm{Gr}(k,n)$ were given by taking all sets larger than a certain set in a given partial order, the flag matroid associated to the Schubert variety $X_{\sigma}$ in $\mathrm{F}\ell(n)$ will consist of all flags larger than $S_{\bullet}$ in a certain partial order. Specifically, we say that $B_{\bullet} \geq_{\bullet} S_{\bullet}$ if and only if $B_j \geq S_j$ in the partial order on sets for each $0 \leq j \leq n$. On permutations, this partial order is known as the Bruhat order.

Definition 6. Let $\sigma$ be a permutation representing a flag $S_{\bullet}$. The Schubert flag matroid $\mathcal{M}_{\sigma}$ associated to $\sigma$ has basis set $\left\{B_{\bullet}: S_{\bullet} \leq_{\bullet} B_{\bullet}\right\}$.

Example 7. Let $\sigma = 214365$. Then, $\mathcal{M}_{\sigma} = \left\{B_{\bullet}: 214365 \leq_{\bullet} B_{\bullet}\right\}$. For instance, $431652 \in \mathcal{M}_{\sigma}$ because $\{4\} \geq \{2\},$ $\{3,4\} \geq \{1,2\}$, $\{1,3,4\} \geq \{1,2,3\}$, etc.. However, $324516 \notin \mathcal{M}_{\sigma}$ because $\{1,2,3,4,5\} \ngeq \{1,2,3,4,6\}$. It is a simple exercise to check that the projection of $\mathcal{M}_{\sigma}$ onto its rank-3 component is exactly the shifted matroid from Example 3. In general, projections of Schubert flag matroids are always shifted matroids and all shifted matroids are obtained in this way. This fact is a shadow of the geometric fact that projections of Schubert varieties in $\mathrm{F}\ell(n)$ are Schubert varieties in $\mathrm{Gr}(k,n)$.

In analogy to what we expect from Grassmannians/matroids, Richardson flag matroids are obtained by taking all flags larger than a fixed flag $S_{\bullet}$ and smaller than a fixed flag $T_{\bullet}$.

Definition 8. Let $\sigma, \tau$ be a permutations representing flags $S_{\bullet}$ and $T_{\bullet}$ respectively such that $T_{\bullet} \geq_{\bullet} S_{\bullet}$. The Richardson flag matroid $\mathcal{M}^{\tau}_{\sigma}$ has basis set $\left\{B_{\bullet}: S_{\bullet} \leq_{\bullet} B_{\bullet} \leq_{\bullet} T_{\bullet} \right\}$.

Example 9. Let $\sigma = 214365$ and $\tau = 456123$. Then, $$\mathcal{M}^{\tau}_{\sigma} = \left\{B_{\bullet}: 214365 \leq_{\bullet} B_{\bullet}\leq_{\bullet} 456123\right\}.$$ For instance, $324165 \in \mathcal{M}^{\tau}_{\sigma}$. However, $324615 \notin \mathcal{M}^{\tau}_{\sigma}$ because $\{2,3,4,6\} \nleq \{1,4,5,6\}$.

Consider the projection of $\mathcal{M}^{\tau}_{\sigma}$ to its rank-3 component. Naively, one might conjecture that projections of Richardson flag matroids will be lattice path matroids. However, this example will illustrate that this is not the case. The set $\{1,2,3\}$ cannot appear as the rank-3 component of any flag in $\mathcal{M}^{\tau}_{\sigma}$ because $\{1,2,3\} \ngeq \{1,2,4\}$. Consider the set $\{3,4,5\}$. If this is to appear as the rank-3 component of a flag, the rank-4 component must be $\{1,3,4,5\}$ because the rank-4 component must be $\leq \{1,4,5,6\}$. Then, the rank-5 component must be $\{1,2,3,4,5\}$ becuase the rank-5 component must be $\leq \{1,2,4,5,6\}$. However, this contradicts the requirement that the rank-5 component be $\geq \{1,2,3,4,6\}$ and hence $\{3,4,5\}$ is not the rank-3 component of any flag in $\mathcal{M}^{\tau}_{\sigma}$. A similar exercise shows that $\{1,5,6\}$ also cannot appear as the rank-3 component of any flag in $\mathcal{M}^{\tau}_{\sigma}$. Any other 3 element subset appears as the rank-3 component of some flag in $\mathcal{M}^{\tau}_{\sigma}$ and hence the projection of $\mathcal{M}^{\tau}_{\sigma}$ to a rank-3 matroid is exactly $\mathcal{W}^3$, the positroid from Example 4.

This somewhat surprising fact is illustrative a more general theorem, which is a direct combinatorial analog of a geometric theorem appearing in [KLS13].

Theorem 10. Let $\sigma, \tau$ be a permutations representing flags $S_{\bullet}$ and $T_{\bullet}$ respectively such that $S_{\bullet} \leq_{\bullet} T_{\bullet}$. Then, the projection of $\mathcal{M}^{\tau}_{\sigma}$ to a rank-$k$ matroid is a positroid. All positroids arise in this fashion.

To recap: We saw that representable matroids can be viewed as combinatorial fingerprints of points in Grassmannians and that common stratifications of the Grassmannian are associated to well studied classes of matroids. In analogy, representable Coxeter matroids can be viewed as combinatorial fingerprints of points in flag manifolds. The Coxeter matroids associated to stratifications of these flag manifolds should represent nice classes of examples. Further, we saw that several matriodal facts can be recovered nearly for free as discrete analogs of geometric phenomena.

[KLS13] Allen Knutson, Thomas Lam, and David Speyer. Positroid Varieties: Juggling and Geometry. Composito Mathematica, 149(10):1710-1752, 2013.