An improved tableau criterion for Bruhat order

Anders Björner and Francesco Brenti

Matematiska Institutionen Kungl. Tekniska Högskolan S-100 44 Stockholm, Sweden

                           bjorner@math.kth.se

Dipartimento di Matematica Universitá degli Studi di Perugia I-061 23 Perugia, Italy

                         brenti@ipgaix.unipg.it

Submitted: March 26, 1996; Accepted: July 12, 1996.

Abstract

To decide whether two permutations are comparable in Bruhat order of S_{n} with the well-known tableau criterion requires \binom{n}{2} comparisons of entries in certain sorted arrays. We show that to decide whether x ≤ y only d_{1} + d_{2} + … + d_{k} of these comparisons are needed, where {d_{1}, d_{2}, …, d_{k}} = {i|x(i) > x(i + 1)}. This is obtained as a consequence of a sharper version of Deodhar’s criterion, which is valid for all Coxeter groups.

1 Introduction

The classical tableau criterion for Bruhat order on S_{n} says that x ≤ y if and only if x_{i,k} ≤ y_{i,k} for all 1 ≤ i ≤ k ≤ n − 1, where x_{i,k} is the i-th entry in the increasing rearrangement of x_{1}, x_{2}, …, x_{k}, and similarly for y_{i,k}. For instance, 2 1 4 3 5 < 5 3 4 1 2 is checked by cellwise comparisons in the arrays

1991 Mathematics Subject Classification. Primary 05E15, 20F55; Secondary 14M15.

Research supported by the Volkswagen-Stiftung (RiP-program at Oberwolfach) and by EC grant No. CHRX-CT93-0400.

1 2 3 4 1 2 4 1 2 2  1 3 4 5 3 4 5 3 5 5

These are actually tableaux (rows and columns are increasing), hence the name of the criterion.

This characterization of Bruhat order (in the geometric version) was found by Ehresmann [E] to describe cell decompositions of flag manifolds. The construction (but not the characterization) also appears in Lehmann [L] for purposes in statistics. Similar tableau criteria were given for the other classical finite groups by Proctor [P] and for certain affine Weyl groups by Björner and Brenti [BB] and by Eriksson and Eriksson [HE, EE].

In 1977 Deodhar [D] published a characterization of Bruhat order on any Coxeter group in terms of the induced order on minimal length coset representatives modulo parabolic subgroups. It was subsequently realized that his characterization implies the tableau criteria of Ehresmann and Proctor, and Deodhar’s work was also used by Björner and Brenti. A different combinatorial characterization of Bruhat order in the finite case was recently given by Lascoux and Schützenberger [LS].

This note is based on the observation that Deodhar’s characterization allows a slight sharpening. This will imply for S_{n} that rows in the tableaux that don’t correspond to descents of the tested permutations can be removed.

We will assume familiarity with Coxeter groups and refer to Humphreys [H] for all unexplained terminology.

2 Deodhar’s Criterion

Let (W, S) be a Coxeter group. For J ⊆ S and w ∈ W, let w = w^{J} · w_{J} with w^{J} ∈ W^{J} = {w ∈ W | ℓ(ws) > ℓ(w) for all s ∈ J} and w_{J} ∈ W_{J} = ⟨J⟩. This factorization is unique, and ℓ(w) = ℓ (w^{J}) + ℓ(w_{J}).

Theorem 1 Let J_{i} ⊆ S, i ∈ E, be a family of subsets such that ⋂_{i∈E}J_{i} = I, and let x ∈ W^{I}, y ∈ W. Then:

x ≤ y ⟺ x^{J_{i}} ≤ y^{J_{i}}  ,  for all i ∈ E.

Proof. For I = ∅ this is Lemma 3.6 of Deodhar [D, p. 195]. His result takes care of the ⇒ direction. His proof of the ⇐ direction is by induction on ℓ(y). The induction step (the laborious part) goes through unchanged for general I and we refer to his paper, but the induction base (the ℓ(y) = 0 case) requires some minor attention.

If ℓ(y) = 0 then x^{J_{i}} = e for all i ∈ E, which implies that x ∈ ⋂_{i∈E} W_{J_{i}} = W_{I}. Since W_{I} ∩ W^{I} = {e} we deduce that x = e, so x = y in this case.

Let (s) = S − {s} for s ∈ S, and let D_{R}(x) = {s ∈ S | ℓ(xs) < ℓ(x)}. Then we have the following as a special case.

Corollary 2 Let x, y ∈ W. Then

x ≤ y ⟺ x^{(s)} ≤ y^{(s)}  ,  for all s ∈ D_{R}(x).

If (W, S) is finite with top element w_{0} one gets (since x ≤ y ⟺ w_{0}x ≥ w_{0}y) the following alternative version.

Corollary 3 x ≤ y ⟺ (w_{0}y)^{(s)} ≤ (w_{0}x)^{(s)} , for all s ∈ S − D_{R}(y).

3 The tableau criterion

We will now specialize to the symmetric group S_{n} with its standard Coxeter generators s_{i} = (i, i + 1), i = 1, …, n − 1. Permutations will be written x = x_{1}x_{2} … x_{n} with x_{i} = x(i), and D_{R}(x) = {i | x_{i} > x_{i−1}}.

Let (k) = {1, …, n − 1} − {k}. The elements of S_{n}^{(k)} are permutations x = x_{1}x_{2} … x_{n} such that x_{1} < x_{2} < … < x_{k} and x_{k+1} < x_{k+2} < … < x_{n}. Clearly, x is determined by the set {x_{1}, x_{2}, …, x_{k}}, and Bruhat order restricted to S_{n}^{(k)} can easily be described in terms of these sets. The following is well known, but for completeness we include a proof.

Lemma 4 For x, y ∈ S_{n}^{(k)}:

x ≤ y ⟺ x_{i} ≤ y_{i}  ,  for all 1 ≤ i ≤ k.

Proof. Assume that x < y is a Bruhat covering. Then y is obtained from x by a transposition (j, m), and in order not to introduce a forbidden descent we must have j ≤ k < m. Hence, x_{j} < x_{m} = y_{j}, and x_{i} = y_{i} for i ∈ {1, …, k} − {j}.

Conversely, suppose that x_{i} ≤ y_{i} for all 1 ≤ i ≤ k, and that x_{j} < y_{j} for some 1 ≤ j ≤ k while x_{i} = y_{i} for all j + 1 ≤ i ≤ k. Then x_{j} + 1 = x_{m} for some m > k, since x_{j} + 1 ≤ y_{j} < y_{j+1} = x_{j+1} if j < k. Let x′ = (x_{j}, x_{j} + 1) · x = x · (j, m). Then x′_{i} ≤ y_{i} for all 1 ≤ i ≤ k and x < x′ is a Bruhat covering (in fact, a left weak order covering), so we are done by induction on ℓ(y) − ℓ(x).

We now come to the improved tableau criterion.

Corollary 5 For x, y ∈ S_{n} let x_{i,k} be the i-th element in the increasing rearrangement of x_{1}, x_{2}, …, x_{k}; and define y_{i,k} similarly. Then the following are equivalent:

(i) x ≤ y; (ii) x_{i,k} ≤ y_{i,k}, for all k ∈ D_{R}(x) and 1 ≤ i ≤ k;

(iii) x_{i,k} ≤ y_{i,k}, for all k ∈ {1, …, n − 1} − D_{R}(y) and 1 ≤ i ≤ k.

Proof. By Lemma 4 condition (ii) says that x^{(k)} ≤ y^{(k)} for all k ∈ D_{R}(x), and condition (iii) that (w_{0}y)^{(k)} ≤ (w_{0}x)^{(k)} for all k ∈ {1, …, n − 1} − D_{R}(w_{0}y). The result then follows from Corollaries 2 and 3.

For example let us check whether x = 3 6 8 4 7 5 9 1 2 < y = 6 9 4 2 8 7 5 3 1. Since D_{R}(x) = {3, 5, 7} we generate the three-line arrays of increasing rearrangements of initial segments of lengths 3, 5 and 7:

\begin{aligned}& & & x \\ 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 3 & 4 & 6 & 7 & 8 \\ 3 & 6 & 8 \end{aligned}  \begin{aligned}& & & y \\ 2 & 4 & 5 & 6 & 7 & 8 & 9 \\ 2 & 4 & 6 & 8 & 9 \\ 4 & 6 & 9 \end{aligned}

Comparing cell by cell we find two violations (3 > 2) in the upper left corner, so we conclude that x ≰ y. Since {1, …, 8} − D_{R}(y) = {1, 4} it is quicker to use the alternative version (iii) of the criterion, which requires comparing the smaller arrays

\begin{aligned}& x \\ 3 & 4 & 6 & 8 \\ 3 \end{aligned}  \begin{aligned}& y \\ 2 & 4 & 6 & 9 \\ 6 \end{aligned}

To reduce the size of a calculation (the size of the tableaux) it may be worth having a preprocessing step to determine which is the smallest of the sets D_{R}(x), D_{L}(x) = D_{R} (x^{−1}), {1, …, n − 1} − D_{R}(y) and {1, …, n − 1} − D_{L}(y). If it is D_{L}(x) one uses that x ≤ y ⟺ x^{−1} ≤ y^{−1}, and similarly for D_{L}(y).

The tableau criteria for other Coxeter groups, being consequences of Deodhar’s abstract criterion, can also be given sharper versions as a consequence of Corollary 2. We will however not make explicit statements for any of the other groups.

4 Remarks

(4.1) A referee has pointed out that it is possible to prove Corollary 5 directly from the usual tableau criterion. Namely, if x ≰ y then by the usual tableau criterion there exists 1 ≤ i ≤ k ≤ n such that x_{i,k} > y_{i,k} and x_{j,l} ≤ y_{j,l} for all 1 ≤ j ≤ l ≤ k − 1 (where x_{i,j} denotes the i-th smallest element of {x_{1}, …, x_{j}}, and similarly for y). Now let r =^{def} min{d ∈ D_{R}(x) ∪ {n} : d ≥ k}. Then we have that x_{i,k} ≤ x_{k} < x_{k+1} < … < x_{r} (for if x_{i,k} > x_{k} then x_{i−1,k−1} = x_{i,k} and hence y_{i−1,k−1} ≤ y_{i,k} < x_{i,k} = x_{i−1,k−1} which contradicts the minimality of k). Therefore y_{i,r} ≤ y_{i,r−1} ≤ … ≤ y_{i,k} < x_{i,k} = x_{i,k+1} = … = x_{i,r}, which contradicts (ii) if r ∈ D_{R}(x) and is absurd if r = n (since y_{i,n} = x_{i,n}). Similarly one can show that (iii) implies (i).

(4.2) A. Lascoux has remarked that Corollary 5 can be deduced from the recent Lascoux-Schützenberger [LS] characterization of the Bruhat order on a finite Coxeter group in terms of bigrassmannian elements (x ∈ W is bigrassmannian if |D_{R}(x)| = |D_{R}(x^{−1})| = 1), which in turn follows from the usual Deodhar’s criterion. In fact, Corollary 2 can be restated as saying that “x ≤ y if and only if x^{(s)} ≤ y for all s ∈ D_{R}(x)”. On the other hand, it follows from Theorem 4.4 of [LS] that “x ≤ y if and only if z ≤ y for all z ∈ B(x)”, where B(x) is the set of all maximal elements of {u ≤ x: u is bigrassmannian }. But it is easy to see that B(x) ⊆ ⋃_{s∈D_{R}(x)} B(x^{(s)}). Therefore if x^{(s)} ≤ y for all s ∈ D_{R}(x) then z ≤ y for all z ∈ ⋃_{s∈D_{R}(x)} B(x^{(s)}) and hence z ≤ y for all z ∈ B(x), which by Theorem 4.4 of [LS] implies that z ≤ y.

References

[BB] A. Björner and F. Brenti, Affine permutations of type A, Electronic Journal of Combinatorics 3(2) (1996), #R18 (35 pp).

[D] V. V. Deodhar, Some characterizations of Bruhat ordering on a Coxeter group and determination of the relative Möbius function, Invent. Math. 39 (1977), 187–198.

[E] C. Ehresmann, Sur la topologie de certains espaces homogènes, Ann. Math. 35 (1934), 396–443.

[HE] H. Eriksson, Computational and Combinatorial Aspects of Coxeter Groups, Ph. D. Thesis, KTH, 1994.

[EE] H. Eriksson and K. Eriksson, Affine Weyl groups as infinite permutations, preprint, 1996.

[H] J. E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge Studies in Advanced Mathematics, no. 29, Cambridge Univ. Press, Cambridge, 1990.

[LS] A. Lascoux, M.-P. Schützenberger, Treillis et bases des groupes de Coxeter, Electronic Journal of Combinatorics 3(2) (1996), #R27 (35 pp).

[L] E. L. Lehmann, Some concepts of dependence, Ann. Math. Statist. 37 (1966), 1137– 1153.

[P] R. A. Proctor, Classical Bruhat orders and lexicographic shellability, J. Algebra 77 (1982), 104–126.