# Rank matrices for type $D$ Bruhat order

Roughly, this question asks how the Bruhat (strong) order in type $$D$$ can be understood like the Bruhat orders in types A and B=C. I'll review how types A and B work before asking my question. As a side note, I tried to ask this question earlier today, then deleted it with the intention of fixing some errors and reasking it, but I can't find the deleted question.

Notation: I write $$[n]$$ for $$\{1,2,\ldots, n \}$$.

Type A The Bruhat order of type $$A_{n-1}$$ is a partial order on the group of permutation of $$[n]$$. It can be described in the two following manners:

("Tableaux criterion") Put a partial order on the set of $$k$$ element subsets of $$[n]$$ as follows: For $$I$$, $$J$$ two such subsets, sort $$I = \{ i_1 < i_2 < \cdots < i_k \}$$ and $$J = \{ j_1 < j_2 < \cdots < j_k \}$$, and define $$I \leq J$$ if $$i_1 \leq j_1$$, $$i_2 \leq j_2$$, ..., $$i_k \leq j_k$$. Then, for permutations $$u$$ and $$v$$, we have $$u \leq v$$ if and only if $$u[k] \leq v[k]$$ for $$1 \leq k \leq n-1$$.

("Rank matrix criterion") We have $$u \leq v$$ if and only if, for all $$1 \leq k, \ell \leq n-1$$, we have $$\#(u[k] \cap [\ell]) \leq \#(v[k] \cap [\ell])$$.

The numbers $$r_{k \ell} = \#(u[k] \cap [\ell])$$ are called the rank matrix of $$u$$. It is often useful to formally define $$r_{0k}=r_{k0} = 0$$ and $$r_{kn}=r_{nk}=k$$. With those boundary definitions, rank matrices are characterized by $$0 \leq r_{(k+1)\ell} - r_{k \ell},\ r_{k(\ell+1)} - r_{k \ell} \leq 1$$ and, if $$r_{(k+1)\ell} = r_{k(\ell+1)} = r_{k\ell}+1$$ then $$r_{(k+1)(\ell+1)} = r_{k\ell}+2$$.

Type B Let $$\sigma : [2n] \to [2n]$$ be the involution $$\sigma(k) = 2n+1-k$$. Then the Coxeter group of type $$B$$ is the centralizer of $$\sigma$$ in $$S_{2n}$$. Bruhat order in type $$B$$ is the induced order from $$S_{2n}$$, and thus can be described as by either the Tableaux Criterion or the Rank Matrix Criterion. In either case, we may cut roughly in half the number of cases which need to be checked, because $$u[k]$$ determines $$u[2n-k]$$, so we only need check the conditions for $$1 \leq k \leq n$$.

Type D The Coxeter group of type $$D_n$$ is the index two subgroup of $$B_n$$ consisting of permutations for which $$\#(u [n] \cap [n]) \equiv n \bmod 2$$. The Bruhat order is no longer induced from $$B_n$$. It seems to follow from other things I will say below that there is a quick definition of it as an induced order though, so that will be my first question:

Let $$\tau$$ be the permutation $$(n \ n+1)$$ in $$B_n$$; this permutation is not in $$D_n$$ but normalizes $$D_n$$. Embed $$D_n$$ into $$B_n \times B_n$$ by $$u \mapsto (u, \tau u \tau^{-1})$$. Is the Bruhat order on $$D_n$$ simply the $$B_n \times B_n$$ Bruhat order restricted to the image?

In any case, what I can find in sources is that something like the tableaux criterion holds. Namely, in any Coxeter group, there is a collection of subgroups called the maximal parabolics, and there are partial orders on the quotients by the maximal parabolics such that $$u \leq v$$ if and only if their cosets in by each maximal parabolic $$P$$ obey $$u P \leq v P$$. To make this sound more like the tableaux criterion, note that the maximal parabolics in type $$D_n$$ are the stabilizers of $$[1]$$, $$[2]$$, ..., $$[n-2]$$, $$[n]$$ and $$[n]':=\tau([n])$$. So we can identify cosets of maximal parabolics with $$D_n$$ orbits of these sets. So we can detect whether $$u \leq v$$ by comparing $$uX$$ and $$vX$$ for some poset relation, with $$X$$ in the list $$[1]$$, $$[2]$$, ..., $$[n-2]$$, $$[n]$$ and $$[n]':=\tau([n])$$. But I haven't found a source which spells out how to order the $$D_n X$$'s.

What, explicitly, is the order on the $$D_n X$$'s?

I tried to work this out myself, and I believe I got the following: Let $$Y$$ and $$Z \in D_n X$$ for $$X$$ as above. Then the poset relation is that we have both $$Y \leq Z$$ and $$\tau(Y) \leq \tau(Z)$$, in our order on subsets of $$[2n]$$.

Is this right? Is there a source for this?

It seems to me I can also encode this in a rank matrix style. Namely, for $$X$$ and $$Y$$ one of $$[1]$$, $$[2]$$, ..., $$[n-2]$$, $$[n]$$, $$[n]'$$, $$[n+2]$$, ..., $$[2n-2]$$, $$[2n-1]$$ and $$u$$ in the $$D_n$$ Coxeter group, let $$r_{XY}(u) = \#(uX \cap Y)$$.

Is it true that $$u \leq v$$ if and only if $$r_{XY}(u) \leq r_{XY}(v)$$ for all such $$X$$, $$Y$$? Is there a source for this?

Finally, one could ask for a simple local characterization of the $$r_{XY}$$'s, similar to the characterization I gave above for type $$A$$ rank matrices.

Is such a characterization known?

• Shouldn't the partial order on the $D_nX$'s be root order (on the $D_n$ orbit of the sets $X$ viewed as weights)? – Sam Hopkins Nov 30 '19 at 2:30
• @SamHopkins It is definitely the transitive closure of the $\to$ relation on $D_n X$ where $\omega \to \eta$ if $\eta - \omega$ is a positive multiple of a positive root. I'm not sure whether that is the same as asking that $\alpha - \beta$ be a positive linear combination of positive roots, and I'm not sure which of those is root order. – David E Speyer Nov 30 '19 at 2:56
• See Lemma 3.1 of Proctor's "Bruhat lattices, ..." sciencedirect.com/science/article/pii/S0195669884800372 – Sam Hopkins Nov 30 '19 at 2:56
• Thanks! It looks like Proctor is making the transitive closure statement. I'll have to read more closely to see whether it is also the more direct condition. – David E Speyer Nov 30 '19 at 2:57
• Sorry, you're right. I know the statement about root order (which is indeed different, it's $\alpha-\beta$ is a nonnegative sum of positive roots) is definitely true for minuscule weights (see Theorem 4.3 of arxiv.org/abs/1108.5245), but Type D has many non-minuscule weights so this probably does not help you. – Sam Hopkins Nov 30 '19 at 3:00

Here are some more thoughts about how the Type D Bruhat order is more complicated than the Type A and Type B/C orders. These ideas might even suggest that giving a "rank matrix"-like description of the partial order is "impossible" in Type D.

There is a certain property of posets called "clivage" (by Lascoux and Schützenberger) or "dissective" (by Reading). Lascoux and Schützenberger (cited below) showed that the Type A and Type B Bruhat orders are dissective. Meanwhile, Geck and Kim (cited below) showed that Type D Bruhat order is not dissective (they address the exceptional types as well). Also, it is known that a finite poset $$P$$ is dissective if and only if the MacNeille completion of $$P$$ is distributive (see Theorem 7 of the paper of Reading cited below).

(As an aside, the MacNeille completion of the Bruhat order of Type A is the distributive lattice of Monotone Triangles (a.k.a. Alternating Sign Matrices) with componentwise order. See the paper of Brualdi and Schroeder cited below for more on this lattice.)

So, Type D Bruhat order lacks a nice property ("dissective") which Type A and B have. But what does this have to do with the possibility of a "rank matrix"-like description of the partial order in Type D? Well, intuitively at least, if you have a partial order defined by componentwise order on some arrays of numbers satisfying certain inequalities, then to formally extend your partial order to be a lattice, what you'll end up doing is taking $$\min$$'s and $$\max$$'s of the entries until you get enough new arrays so that everyone has a meet and join. And if so, the result will be distributive because $$\min$$'s and $$\max$$'s distribute over one another. But we know Type D Bruhat order does not have a distributive lattice as its completion, so it "can't" have a partial order given by comparing arrays of numbers in this way.

Brualdi, Richard A.; Schroeder, Michael W., Alternating sign matrices and their Bruhat order, Discrete Math. 340, No. 8, 1996-2019 (2017). ZBL1366.15024.

Geck, Meinolf; Kim, Sungsoon, Bases for the Bruhat-Chevalley order on all finite Coxeter groups, J. Algebra 197, No. 1, 278-310 (1997). ZBL0977.20033.

Lascoux, Alain; Schützenberger, Marcel-Paul, Lattices and bases of Coxeter groups, Electron. J. Comb. 3, No. 2, Research paper R27, 35 p. (1996); printed version J. Comb. 3, No. 2, 633-667 (1996). ZBL0885.05111..

Reading, Nathan, Order dimension, strong Bruhat order and lattice properties for posets, Order 19, No. 1, 73-100 (2002). ZBL1007.05097.

• Incidentally, I didn't quite work it out, but I feel like there must be a connection between what you call the "rank matrices" for Type A Bruhat order and ASMs/monotone triangles (because of this MacNeille completion business). – Sam Hopkins Dec 1 '19 at 17:16
• Thanks! Yes, ASM's are in easy bijection with arrays of integers obeying $r_{0k}=r_{k0}=0$, $r_{kn}=r_{nk}=k$, $0 \leq r_{(i+1)j} - r_{ij},\ r_{i(j+1)}-r_{ij} \leq 1$. The distributive lattice structure on ASM's is termwise dominance of these arrays, with meet and join given by min and max. – David E Speyer Dec 2 '19 at 1:26
• As a side note, I have a guess as to what the Dedekind-MacNeille completion of $B_n$ might be. We have $B_n \subset S_{2n} \subset \mathrm{ASM}_{2n}$. Since $B_n$ are the matrices in $S_{2n}$ which are fixed by $180^{\circ}$ rotation, one might guess that the Dedekind-Macneille completion of $B_n$ is the ASMs which are fixed by $180^{\circ}$ rotation. This is wrong! – David E Speyer Dec 3 '19 at 14:15
• I wasn't familiar with the Brualdi-Schroeder paper so I glanced at it. I noticed a misleading sentence and I wanted to correct it in case someone goes there to try to figure out what Dedekind-MacNeille completion is. The misleading sentence is "Every finite partially ordered set $(X,\le)$ can be completed to a finite distributive lattice and there is a unique minimal completion of $(X,\le)$ called its MacNeille completion." A more correct sentence will appear in the next comment. – Nathan Reading Dec 5 '19 at 2:40
• More correct: "Every partially ordered set $(X,\le)$ can be completed to a complete lattice (in the sense that $(X,\le)$ is an induced subposet of the lattice) and there is a unique minimal completion of $(X,\le)$ called its (Dedekind-)MacNeille completion." Some comments: 1) You don't need finiteness for DM completion. Dedekind used it to construct the reals from the rationals. 2) DM completion is not about completing to a distributive lattice. It completes to a complete lattice, which may or may not be distributive. (See Sam's answer above.) – Nathan Reading Dec 5 '19 at 2:45

The answer to my questions is that I was wrong. I'll switch to the more standard notation of having $$D_n$$ act on $$\{ -n, -n+1, \ldots, -2, -1, 1, 2, \ldots, n-1, n \}$$ in order to match the reference of Proctor.

Here is the simplest example to demonstrate my error. Take $$n \geq 4$$ and look at $$D_n \cdot [2]$$. Then my belief above was that we should have $$(2,1) > (1,-2)$$, since $$(2,1) > (1,-2)$$ and $$(2,-1) > (-1,-2)$$ are both valid inequalities in type $$B$$. But this is wrong; any type $$D$$ transposition which lowers $$(2,1)$$ takes it below $$(1,-2)$$. In terms of weights, we are taking about $$e_2+e_1$$ and $$-e_2+e_1$$. They differ by $$2 e_2 = (e_2+e_1) + (e_2-e_1)$$, which is a sum of positive roots. However, subtracting either $$e_2+e_1$$ or $$e_2-e_1$$ from $$e_2+e_1$$ gives $$0$$ and $$2 e_1$$ respectively, neither of which are in the $$D_n$$ orbit of $$e_2+e_1$$.

The paper of Proctor which Sam Hopkins pointed me to gives the correct criterion in Theorem 5D: Let $$I=\{ i_1 < i_2 < \cdots < i_k \}$$ and $$J=\{ j_1 < j_2 < \cdots < j_k \}$$ be two $$k$$-element subsets of $$\{ \pm 1, \pm 2, \ldots, \pm n \}$$, both of which have the property of not containing both $$a$$ and $$-a$$. Then $$I \leq J$$ if and only if two conditions hold:

• $$i_r \leq j_r$$ and

• If there is a set of indices $$p, p+1, \ldots, q$$ such that $$\{ |i_p|, |i_{p+1}|, \ldots, |i_q| \}$$ and $$\{ |j_p|, |j_{p+1}|, \ldots, |j_q| \}$$ are each permutations of $$\{ 1,2,\ldots, q-p+1 \}$$, then the number of negative elements among $$(i_p, i_{p+1}, \ldots, i_q)$$ and $$(j_p, j_{p+1}, \ldots, j_q)$$ must have the same parity.

At the moment, I don't see how to make this second condition sound like a rank matrix condition.

• Interesting; so the failure of the partial order on $W^{J}$ to adhere to root order outside of the minuscule case significantly complicates things. – Sam Hopkins Dec 1 '19 at 4:07
• In case it's useful, Björner and Brenti give a different criterion in their Theorem 8.2.8. Björner and Brenti assign the Proctor result as Exercise 11 in their Chapter 8. – Nathan Reading Dec 4 '19 at 15:42