%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[12pt]{article}

\usepackage{amssymb}
\usepackage{latexsym}

\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}

\newtheorem{Thm}{Theorem}%[section]
\newtheorem{Ex}[Thm]{Example}
\newtheorem{Cor}[Thm]{Corollary}%[section]
\newtheorem{Lem}[Thm]{Lemma}%[section]

\newtheorem{notation}{Notation}
\newtheorem{remop}{Remarks on the proofs}

\setlength{\oddsidemargin}{0.25in}
\setlength{\evensidemargin}{0.25in}
\setlength{\topmargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\textwidth}{6.5in}

\def\oli{\overline}
\def\sbst{\subseteq}

\def\bpf{\noindent{\sc Proof.~}}
\def\epf{\hfill\qed}
\def\qed{\vbox{\hrule
 \hbox{\vrule\hbox to 5pt{\vbox to 8pt{\vfil}\hfil}\vrule}\hrule}}
\def\endofproof{\unskip \nobreak \hskip0pt plus 1fill \qquad \qed% \par
\medskip\noindent}

\def\({\left(}
\def\){\right)}
\def\Lolraw{\Longleftrightarrow}
\def\Raw{\Rightarrow}
\def\Law{\Leftarrow}

%\def\binom#1#2{\big( \begin{array}{c} #1 \\ #2 \end{array} \big)}
\DeclareRobustCommand{\binom}{\frbinom{}}
\def\frbinom#1#2#3{{#1{#2\atopwithdelims()#3}}}
\def\dbinom{\protect\frbinom\displaystyle}
\def\tbinom{\protect\frbinom\textstyle}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 3 (1996), \#R22\hfill} 
\thispagestyle{empty} 

\title{An improved tableau criterion for Bruhat order}

\author{ {\sc Anders Bj\"orner} and {\sc Francesco Brenti} \\
    {\small \em Matematiska Institutionen} \\
    {\small \em Kungl. Tekniska H\"ogskolan} \\
    {\small \em S-100 44  Stockholm, Sweden} \\
    {\small \texttt{  bjorner@math.kth.se}} \\
    {\small \em Dipartimento di Matematica} \\
    {\small \em Universit\'a degli Studi di Perugia} \\
    {\small \em I-061 23 Perugia, Italy} \\
    {\small \texttt{  brenti@ipgaix.unipg.it}} \\
    {\small Submitted: March 26, 1996; Accepted: July 12, 1996.}
}

\date{}
\begin{document}

\maketitle

\def\thefootnote{}
\footnote{1991 {\it Mathematics Subject Classification.} Primary~~05E15,~20F55;~~Secondary~14M15.
\newline
\indent\quad
Research supported by the Volkswagen-Stiftung (RiP-program at
Oberwolfach) and by 
\newline
\indent\quad
EC grant No. CHRX-CT93-0400.}

\begin{abstract}
\noindent
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\le y$ only $d_1+d_2+\dots+d_k$ of these comparisons
are needed, where $\{d_1,d_2,\dots,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. 
\end{abstract}
\bigskip
\bigskip

\section{Introduction} The classical tableau criterion for Bruhat
order on $S_n$ says that $x\le y$ if and only if $x_{i,k}\le y_{i,k}$
for all $1\le i\le k\le n-1$, where $x_{i,k}$ is the $i$-th entry in
the increasing rearrangement of $x_1,x_2,\dots,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

$$\begin{array}{c}
\begin{array}{cccc}
1 & 2 & 3 & 4\\
1 & 2 & 4\\
1 & 2\\
2
\end{array}
\qquad\qquad
\begin{array}{cccc}
1 & 3 & 4 & 5\\
3 & 4 & 5\\
3 & 5\\
5
\end{array}
\end{array}$$

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 \cite{E} to describe cell decompositions of flag
manifolds. The construction (but not the characterization) also
appears in Lehmann \cite{L} for purposes in statistics. Similar
tableau criteria were given for the other classical finite groups by
Proctor \cite{P} and for certain affine Weyl groups by Bj\"orner and
Brenti \cite{BB} and by Eriksson and Eriksson \cite{HE,EE}.
%\newpage

In 1977 Deodhar \cite{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\"orner
and Brenti. A different combinatorial characterization of Bruhat
order in the finite case was recently given by Lascoux and
Sch\"utzenberger \cite{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
\cite{H} for all unexplained terminology.
\bigskip

\section{Deodhar's Criterion} 
Let $(W,S)$ be a Coxeter group. For $J\sbst S$ and $w\in W$, let
$w=w^J\cdot w_J$ with $w^J\in W^J=\{w\in W\mid\ell(ws)>\ell(w)\mbox{~
for all~}s\in J\}$ and $w_J\in W_J=\langle J\rangle$. This
factorization is unique, and $\ell(w)=\ell\(w^J\)+\ell(w_J)$.

\begin{Thm} Let $J_i\sbst S$, $i\in E$, be a family of subsets such
that $\smash{\bigcap\limits_{i\in E}} J_i=I$, and let $x\in W^I$, $y\in
W$. Then:
$$
x\le y \Lolraw x^{J_i}\le y^{J_i}\qquad,\qquad\mbox{for all~} i\in E.
$$
\end{Thm}

\bpf For $I=\varnothing$ this is Lemma 3.6 of Deodhar
\cite[p. 195]{D}. His result takes care of the $\Raw$ direction. His
proof of the $\Law$ direction is by induction on $\ell(y)$. The
induction step (the laborious part) goes through unchanged for general
$I$ and we refer to his paper, but the induction base (the $\ell(y)=0$
case) requires some minor attention.

If $\ell(y)=0$ then $x^{J_i}=e$ for all $i\in E$, which implies that
$x\in\bigcap_{i\in E} W_{J_i}=W_I$. Since $W_I\cap W^I=\{e\}$ we
deduce that $x=e$, so $x=y$ in this case.
\epf

\bigskip

Let $(s)=S-\{s\}$ for $s\in S$, and let $D_R(x)=\{s\in
S\mid\ell(xs)<\ell(x)\}$. Then we have the following as a special
case.

\begin{Cor} Let $x,y\in W$. Then
$$
x\le y\Lolraw x^{(s)}\le y^{(s)}\qquad,\qquad\mbox{for all\quad } s\in
D_R(x).
$$
\end{Cor}

If $(W,S)$ is finite with top element $w_0$ one gets (since $x\le
y\Lolraw w_0x\ge w_0y$) the following alternative version.

\begin{Cor} $x\le y\Lolraw (w_0y)^{(s)}\le(w_0x)^{(s)}$\,, for all\,\, $s\in
S-D_R(y)$.
\end{Cor}
\bigskip

\section{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, \dots, n-1$. Permutations will
be written $x=x_1x_2\dots x_n$ with $x_i=x(i)$, and $D_R(x)=\{i\mid
x_i>x_{i-1}\}$.

Let $(k)=\{1,\dots,n-1\}-\{k\}$. The elements of $S^{(k)}_n$ are
permutations $x=x_1x_2\dots x_n$ such that
$x_1<x_2<\dots<x_k$ and $x_{k+1}<x_{k+2}<\dots<x_n$. Clearly, $x$ is
determined by the set $\{x_1,x_2,\dots,x_k\}$, and Bruhat order
restricted to $S^{(k)}_n$ can easily be described in terms of these
sets. The following is well known, but for completeness we include a
proof.

\begin{Lem} For $x,y\in S^{(k)}_n$:
$$
x\le y\Lolraw x_i\le y_i\qquad,\qquad\mbox{for all\quad } 1\le i\le k.
$$
\end{Lem}

\bpf 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\le k<m$. Hence,
$x_j<x_m=y_j$, and $x_i=y_i$ for $i\in\{1,\dots,k\}-\{j\}$.

Conversely, suppose that $x_i\le y_i$ for all $1\le i\le k$, and that
$x_j<y_j$ for some $1\le j\le k$ while $x_i=y_i$ for all $j+1\le i\le
k$. Then $x_j+1=x_m$ for some $m>k$, since $x_j+1\le
y_j<y_{j+1}=x_{j+1}$ if $j<k$. Let $x'=(x_j,x_j+1)\cdot
x=x\cdot(j,m)$. Then $x'_i\le y_i$ for all $1\le i\le k$ and $x<x'$ is
a Bruhat covering (in fact, a left weak order covering), so we are
done by induction on $\ell(y)-\ell(x)$.
\epf

\bigskip

We now come to the improved tableau criterion.

\begin{Cor}For $x,y\in S_n$ let $x_{i,k}$ be the $i$-th element in the
increasing rearrangement of $x_1,x_2,\dots,x_k$; and define $y_{i,k}$
similarly. Then the following are equivalent:
\begin{enumerate}
\item $x\le y$;
\item $x_{i,k}\le y_{i,k}$, for all $k\in D_R(x)$ and $1\le i\le k$;
\item $x_{i,k}\le y_{i,k}$, for all $k\in\{1,\dots,n-1\}-D_R(y)$ and
$1\le i\le k$.
\end{enumerate}
\end{Cor}

\bpf By Lemma 4 condition (ii) says that $x^{(k)}\le
y^{(k)}$ for all $k\in D_R(x)$, and condition (iii) that
$(w_0y)^{(k)}\le(w_0x)^{(k)}$ for all $k\in\{1,\dots,n-1\}-D_R(w_0y)$. The result
then follows from Corollaries 2 and 3.
\epf

\bigskip

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{array}{c}
\begin{array}{ccccccc}
& & & x\\
& & &\\
3 & 4 & 5 & 6 & 7 & 8 & 9\\
3 & 4 & 6 & 7 & 8\\
3 & 6 & 8
\end{array}
\qquad\qquad
\begin{array}{ccccccc}
& & & y\\
& & &\\
2 & 4 & 5 & 6 & 7 & 8 & 9\\
2 & 4 & 6 & 8 & 9\\
4 & 6 & 9
\end{array}
\end{array}$$

Comparing cell by cell we find two violations ($3>2$) in the upper left
corner, so we conclude that $x\nleq y$. Since
$\{1,\dots,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{array}{c}
\begin{array}{cccc}
& x\\
& & &\\
3 & 4 & 6 & 8\\
3
\end{array}
\qquad\qquad
\begin{array}{cccc}
& y\\
& & &\\
2 & 4 & 6 & 9\\
6
\end{array}
\end{array}$$

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}\)$, 
\newline
$\{1,\dots,n-1\}-D_R(y)$ and
$\{1,\dots,n-1\}-D_L(y)$. If it is $D_L(x)$ one
uses that $x\le y\Lolraw x^{-1}\le y^{-1}$, and similarly for
$D_L(y)$.
\smallskip
 
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.
\bigskip

\section{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 \not \leq y$
then by the usual tableau criterion there exists $1 \leq i \leq k \leq n$
such that $x_{i,k} > y _{i,k}$ and $x_{j,l} \leq y_{j,l}$
for all $1 \leq j \leq l \leq k-1$
(where $x_{i,j}$ denotes the $i$-th smallest
element of $\{ x_{1}, \ldots , x_{j} \}$, and similarly for $y$). Now let
$r \stackrel{\rm def}{=} $ min$\{ d \in D_{R}(x)\cup\{n\}: \; d \geq k \}$. Then
we have that $x_{i,k} \leq x_{k} < x_{k+1} < \ldots < 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}
\leq y_{i,k} < x_{i,k} =x_{i-1,k-1}$ which contradicts the minimality of $k$).
Therefore $y_{i,r} \leq y_{i,r-1} \leq \ldots \leq y_{i,k} < x_{i,k}
=x_{i,k+1} = \ldots = x_{i,r}$, which contradicts (ii) if 
$r\in D_R (x)$ and is absurd if $r=n$ (since $y_{i,n}=x_{i,n}$). 
Similarly one can show that (iii) implies (i).
\smallskip

(4.2) A. Lascoux has remarked that Corollary 5 can be deduced from the
recent Lascoux-Sch\"utzenberger \cite{LS} characterization 
of the Bruhat order on a
finite Coxeter group in terms  of bigrassmannian elements ($x \in W$ is
{\em 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 \leq y$ if and only if $x^{(s)} \leq y$ for all $s \in D_{R}
(x)$''. On the other hand, it follows from Theorem 4.4 of  \cite{LS} that
``$x \leq y$ if and only if $z \leq y$ for all $z \in B(x)$'', where $B(x)$
is the set of all maximal elements  of $\{ u \leq x$: $u$ is bigrassmannian
$\}$. But it is easy to see that $B(x) \subseteq \bigcup _{s \in D_{R}(x)}
B(x^{(s)})$. Therefore if $x^{(s)} \leq y$ for all $s \in D_{R}(x)$ then
$z \leq y$ for all $z \in  \bigcup _{s \in D_{R}(x)}
B(x^{(s)})$ and hence $z \leq y$ for all $z \in B(x)$, which 
by Theorem 4.4 of \cite{LS} implies that $z \leq y$.
\bigskip

\begin{thebibliography}{9999}

\bibitem[BB]{BB} 
A. Bj\"orner and F. Brenti, {\em Affine permutations of
type A}, Electronic Journal of Combinatorics 3(2) (1996), \#R18 (35 pp).

\bibitem[D]{D}
V. V. Deodhar, {\em Some characterizations of Bruhat ordering 
on a Coxeter group and determination of the relative M\"obius
function}, Invent. Math. {\bf 39} (1977), 187--198.

\bibitem[E]{E}
C. Ehresmann, {\em Sur la topologie de certains espaces
homog\`{e}nes}, Ann. Math. {\bf 35} (1934), 396--443.

\bibitem[HE]{HE} H. Eriksson, {\em Computational and Combinatorial Aspects of
Coxeter Groups}, Ph. D. Thesis, KTH, 1994.

\bibitem[EE]{EE} H. Eriksson and K. Eriksson, {\em Affine Weyl groups as 
infinite permutations}, preprint, 1996.

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

\bibitem [LS]{LS}
A. Lascoux, M.-P. Sch\"utzenberger, {\em Treillis et bases des groupes de
Coxeter}, Electronic Journal of Combinatorics 3(2) (1996), \#R27 (35 pp).

\bibitem[L]{L}
E. L. Lehmann, {\em Some concepts of dependence}, Ann. Math.
Statist. {\bf 37} (1966), 1137--1153.

\bibitem[P]{P}
R. A. Proctor, {\em Classical Bruhat orders and lexicographic
shellability}, J. Algebra {\bf 77} (1982), 104--126.

\end{thebibliography}

\vfill

\end{document}