Math. J. Okayama Univ. 57 (2015), 159–172

ENUMERATIVE COMBINATORICS ON DETERMINANTS
AND SIGNED BIGRASSMANNIAN POLYNOMIALS
Masato Kobayashi
Abstract. As an application of linear algebra for enumerative combinatorics, we introduce two new ideas, signed bigrassmannian polynomials and bigrassmannian determinant. First, a signed bigrassmannianpolynomial is a variant of the statistic given by the number of bigrassmannian permutations below a permutation in Bruhat order as Readingsuggested (2002) and afterward the author developed (2011). Second,bigrassmannian determinant is a q-analog of the determinant with respect to our statistic. It plays a key role for a determinantal expressionof those polynomials. We further show that bigrassmannian determinant satisfies weighted condensation as a generalization of Dodgson,
Jacobi-Desnanot and Robbins-Rumsey (1986).

1. Introduction
The purpose of this article is to introduce two new ideas, signed bigrassmannian polynomials and bigrassmannian determinant as an application of
linear algebra for enumerative combinatorics. We begin with explaining our
motivation.
1.1. Reading’s problem (2002): bigrassmannian statistic. Permutation statistics has been of great importance in enumerative combinatorics;
in particular, Mahonian and Eulerian statistics, such as inversions and descent numbers, are fundamental in the theory. Here what we deal with is acertain new statistic β, which we call bigrassmannian statistic. Reading [11]suggested the following problem:
Problem 1.1. Let β(w) be the number of join-irreducible (equivalently, bigrassmannian) permutations P
weakly below a permutation w in Bruhat order.
Find its generating function w∈Sn q β(w) .
He gave examples of such generating functions for smaller n’s:
1+q
1 + 2q + 2q 3 + q 4
1 + 3q + q 2 + 4q 3 + 2q 4 + 2q 5 + 2q 6 + 4q 7 + q 8 + 3q 9 + q 10

(S2 )
(S3 )
(S4 )

Mathematics Subject Classification. Primary 20F55; Secondary 05A05, 11C20, 20B30.
Key words and phrases. Bigrassmannian permutations, Bruhat order, Permutation statistics, Robbins-Rumsey determinant, Symmetric Groups, Tournaments, Vandermondedeterminant.
159

160

M. KOBAYASHI

Unfortunately, we failed to find any patterns of these coefficients nor factorsof such polynomials. Instead, in this article, we study the following signed
statistic (as signed Mahonian or signed Eulerian statistics):
X
Bn (q) =(−1)ℓ(w) q β(w)w∈Snwhere ℓ(w) is the number of inversions; let us call {Bn (q) | n = 1, 2, 3, . . . }signed bigrassmannian polynomials. Fortunately, we could find satisfactory
descriptions of such polynomials. It turned out that it is also worthwhile
to study these polynomials with a connection to tournaments and Vandermonde determinant. Since each Bn (q) is a signed sum over the symmetricgroup, it is natural to come to this idea:
Main idea. Use the determinant to find Bn (q).
The determinant is usually a function which outputs a scalar. For our
purpose to find Bn (q), we introduce its q-analog (Section 4); we call it
bigrassmannian determinant.
As main results, we will prove three theorems:• Theorem 3.11: a factorization of Bn (q).
• Theorem 4.4: a determinantal expression of Bn (q).
• Theorem 4.6: weighted condensation for bigrassmannian determinant.
In addition, we observe a corollary after each of these theorems.
1.2. Overview. In Section 2, we review some classic results on tournaments
and Vandermonde determinant as mentioned above. These facts will playa fundamental role in the sequel. In Section 3, we introduce β-statistic
for tournaments as well as permutations. Then, we find factors of Bn (q)using weighted Vandermonde determinant. Section 4 continues to study
Bn (q) (from a little different aspect); we give a definition of bigrassmannian
determinant for square matrices as a q-analog of the original one. This new
idea leads to a determinantal expression of Bn (q) as we shall see. Further,
we prove that bigrassmannian determinant satisfies weighted condensation.
It slightly generalizes the construction of Robbins-Rumsey’s λ-determinants[13]. We end with some comments for future work in Section 5.
2. Tournaments and Vandermonde determinant
We begin with combinatorics of tournaments and Vandermonde determinant.

DETERMINANTS AND SIGNED BIGRASSMANNIAN POLYNOMIALS

161

2.1. Tournaments.
Definition 2.1. A tournament is a complete digraph with vertices labeledby 1, 2, . . . , n. We denote by Tn the set of all tournaments.
Example 2.2. Here are eight elements in T3 :

2
2o

✁✁
✁✁

1❂

❂❂
❂
/3

1
✁@ ❂❂❂❂
✁

✁✁

3

1
✁@ ❂❂❂❂
✁
✁✁

/3
2
1
✁@ ^❂❂❂❂
✁
✁✁
/3
2

2o

✁✁
✁✁

2o

✁✁
✁✁

1❂

❂❂
❂

3

2

1 ^❂

❂❂
❂

3

2o

✁✁
✁✁

1 ^❂

❂❂
❂
/3

1
✁@ ^❂❂❂❂✁✁✁

3

Since there are two choices of direction for each pair (i, j) such that 1 ≤ i <j ≤ n, we have |Tn | = 2n(n−1)/2 in total.
In what follows, the letter G means an element of Tn unless otherwise
specified (G is for Graph).
Definition 2.3. An inversion of G is a directed edge j → i with j > i. The
length ℓ(G) is the number of inversions of G. An upset of an inversion j → i
is the vertex j. Define ωG (j) to be the outdegree of j.
2.2. Cycle and transitivity. Below, we just say a “cycle” to mean a 3cycle (which is the only kind of cycles we treat).
Definition 2.4. Let (i, j, k) be a triple such that i < j < k. Suppose i, j, kform a cycle in G. Say the cycle is positive if k → j → i → k; it is negative
if i → j → k → i. Besides, say G is transitive if it does not contain any
cycles.
Observe that precisely six tournaments in Example 2.2 are transitive.
2.3. Permutations. By Sn we mean the symmetric group on [n] = {1, 2, . . . , n}.
The set of inversions of w ∈ Sn is
N (w) = {(i, j) ∈ [n] × [n] | i < j and w−1 (i) > w−1 (j)}.
Define the length ℓ(w) to be |N (w)|. Let G(w) be the tournament such thatj → i is an inversion of G(w) ⇐⇒ (i, j) ∈ N (w). Say the tournament G(w)is induced from a permutation w ∈ Sn . Let us make sure the following:
Fact 2.5. Bressoud [2, Exercise 2.4.2] There is a bijection between Sn andtransitive tournaments in Tn .
Thanks to this result, we naturally view Sn ⊆ Tn in what follows. In
particular, ℓ(G(w)) = ℓ(w).

162

M. KOBAYASHI

2.4. Vandermonde determinant.
Definition 2.6. Let x1 , . . . , xn and λ be commutative variables. The n-th
Vandermond λ-determinant isY
Vn (x, λ) =(xi + λxj ).
1≤i<j≤nThis is a polynomial in xi ’s (the bold letter x means such variables for
short) and λ. We must explain why we used the word “determinant”: Following Robbins-Rumsey [13], we recursively define a determinant-like function | |λ for square matrices as follows. First, we formally define | |λ for
the 0 by 0 matrix to be 1 and for a 1 by 1 matrix (a11 ) to be a11 itself. Now
let A be an n by n matrix for n ≥ 2. Let Aji denote the matrix that remains
when we delete the i-th row and j-th column of A. If we wish to delete
more than one row (column), the numbers of the deleted rows (columns) arelisted as subscripts (superscripts). The λ-determinant of A is
|A|λ =|A11 |λ |Ann |λ + λ|A1n |λ |An1 |λ
|A1n
1n |λ

(a rational function of λ)provided | |λ of all minors of A are nonzero. In particular, λ = −1 recovers
the original determinant (going back to Dodgson and Desnanot-Jacobi).
From this point of view, we can understand Vn (x, λ) as the λ-determinantof the Vandermonde matrix: Vn (x, λ) = |xn−ij |λ .
Q
ω(j)Definition 2.7. The Vandermonde monomial for G is ρ(G) = λℓ(G) j∈[n] xj .
Proposition 2.8. We haveVn (x, λ) =

X

ρ(G).

G∈Tn

Proof. To a tournament Q
G, assign a monomial with the choices of xi or
λxj from each factor of i<j (xi + λxj ). Then λ in the monomial counts
inversions and xj records the outdegree.
Now, split the sum into two parts, transitive or not:X
X
X
ρ(G) =
ρ(G) +
ρ(G).
G∈Tn

G∈Sn

G∈Tn \Sn

Fact 2.9.
X

= 0.

ρ(G)

G∈Tn \Sn

Proof. See Bressoud [2, Exercise 2.4.4].

λ=−1



DETERMINANTS AND SIGNED BIGRASSMANNIAN POLYNOMIALS

163

3. Signed bigrassmannian statistic
3.1. Bigrassmannian statistic.
Definition
P 3.1. Define the bigrassmannian statistic for a tournament G asβ(G) = j→i (j − i).
j>iTable 1 shows this (and inversion) statistic over S4 .
Remark. This statistic is named after the bigrassmannian permutations;
say w ∈ Sn is bigrassmannian if there exists a unique pair (i, j) ∈ [n − 1] ×[n − 1] such that w−1 (i) > w−1 (i + 1) and w(j) > w(j + 1). We refer toLascoux-Schützenberger [10], Geck-Kim [7], Reading [11] and the author [9]for combinatorics of these permutations.
Define Bruhat order ≤ on Sn as the transitive closure of the following
binary relation: v → w meaning w = vtij , for some i < j, tij a transpositionand ℓ(v) < ℓ(w). Let B(w) = {u bigrassmannian | u ≤ w} and set β(w) =|B(w)|. The author [9] showed thatXβ(w) =(j − i).
(i,j)∈N (w)Thus, we can compute β simply as weighted enumeration of inversions:β(3412) = (3 − 1) + (3 − 2) + (4 − 1) + (4 − 2) = 8,
for example (Figure 1). From this point of view, our definition above is anatural extension of β for tournaments. This statistic implicitly appearedalso in the Gessel-Viennot’s
lattice path counting context [2, Theorem 3.7]
Pn
as the quantity i=1 i(i − w(i)):
Proposition 3.2. For each w ∈ Sn , we havePP(1) β(w) = ni=1 (i − w(i))2 /2 = ni=1 i(i − w(i)).
(2) β(w) = β(w−1 ).

Table 1. statistics of ℓ and β over S4
1234
1243
1324
1342
1423
1432

ℓ
0
1
1
2
2
3

β
0
1
1
3
3
4

2134
2143
2314
2341
2413
2431

ℓ
1
2
2
3
3
4

β
1
2
3
6
5
7

3124
3142
3214
3241
3412
3421

ℓ
2
3
3
4
4
5

β
3
5
4
7
8
9

4123
4132
4213
4231
4312
4321

ℓ β
3 6
4 7
4 7
5 9
5 9
6 10

164

M. KOBAYASHI

Figure 1. Bruhat order of bigrassmannian permutation in S4
2341 ❳❳❳❳❳❢❢❢❢✉ 3412 ■❳■❳❳❳❳❢❳❢❳❢❳❢❳❢❢❢❢ 4123 ■■
❳❢
❢
❳
❢
❳
✉
❳
❢
❳❳❳✉❳✉❳
❢
❳❳❳❳❳
■
■ ❢❢
✉✉
❢❢❢❢
❳❳❳❳❳ ■■■❳❳❢❳❢❳❢❳❢❢❢■❢■■✉✉✉❢❢❢❢❢❢❢❢❢✉✉✉❢❢❢❳❢❢
❳❳❳❳
❳❳❳
❢
❢
2314 ❳❳❳❳❳
3124
1342
1423
■■■
■■■
■■■ ❢❢❢❢❢❢❢❢❢✉❳❳❳❳❳ ✉
✉
✉
✉
✉
❢
❳
❳✉❳❳
■■■
■■
✉
✉
❢❢■❢■
✉✉✉ ❳❳❳❳❳❳❳❳❳■✉✉✉❢❢❢❢❢❢❢❢❢ ■
✉✉✉
❢
2134

1324

1243

Proof. (1) See [9] for the first equality. It follows that
n
n
n
X
1X
1X 2
2
2
β(w) =(i − w(i)) =(i − 2iw(i) + w(i) ) =i(i − w(i)).
2
2
i=1

i=1

i=1
−1
Next, (2) follows from the facts that (a) u 7→ u is an order-preserving

automorphism in Bruhat order on Sn , (b) u is bigrassmannian ⇐⇒ so is
u−1 ; we do not go into details here because the proof is not so importantfor our discussions below.
Definition 3.3. Let x1 , . . . , xn , λ and q be commutative variables. TheQω(j)weighted Vandermonde monomial for G is χ(G) = λℓ(G) q β(w) j∈[n] xj .
Definition 3.4. The n-th weighted Vandermonde determinant isY(xi + λq j−i xj ).
Vn (x, λ, q) =1≤i<j≤n

Example 3.5.
V3 (x, λ, q) = (x1 + λqx2 )(x1 + λq 2 x3 )(x2 + λqx3 )= x21 x2 + λqx1 x22 + λqx21 x3 + (λ2 + λ)q 2 x1 x2 x3+ λ2 q 3 x22 x3 + λ2 q 3 x1 x23 + λ3 q 4 x2 x23 .
Proposition 3.6. We haveVn (x, λ, q) =

X

χ(G).

G∈Tn

Proof. The idea is similar to Proposition 2.8.

Lemma 3.7.
X

G∈Tn \Sn

= 0.

χ(G)
x1 =···=xn =1,λ=−1

DETERMINANTS AND SIGNED BIGRASSMANNIAN POLYNOMIALS165

To prove this lemma, we need a further definition and proposition.
Definition 3.8. For i < j < k, define a map Cijk : Tn → Tn as follows: if
i, j, k form a cycle in G, then Cijk (G) is the tournament with all three edges
in the cycle reversed and all other edges unchanged. If i, j, k do not form acycle in G, then simply set Cijk (G) := G.
Observe that Cijk is an involution.
Proposition 3.9. Let i < j < k. If i, j, k form a cycle in G, then ℓ(Cijk (G)) ∈{ℓ(G) − 1, ℓ(G) + 1} and β(Cijk (G)) = β(G).
Proof. A positive cycle contains two inversions whereas a negative cycle
contains one. The map Cijk interchanges these so that lengths differ by one.
However, β is invariant because of the equality k − i = (k − j) + (j − i). 
Proof of Lemma 3.7. Consider the lexicographic order on {(i, j, k) ∈ [n]3 |i < j < k}. We will construct a perfect matching on the set Tn \ Sn .
First, choose all tournaments G from Tn such that (1, 2, 3) is a cycle in
G. It is either positive or negative; hence G ↔ C123 (G) gives a matching.
Next, choose all tournaments H from the remaining tournaments such that(1, 2, 4) is a cycle in H. Again, H ↔ C124 (H) gives a matching. Continue
this procedure up to (n−2, n−1, n). We certainly exhausted all tournaments
in Tn \Sn with the perfect matching constructed. As shown above, each pair
has lengths of opposite parity and the same β. Thus x1 = · · · = xn = 1 and
λ = −1 yield zero.

3.2. Signed bigrassmannian polynomials.
Definition 3.10. Let n be a positive integer. The n-th signed bigrassmannian polynomial isX(−1)ℓ(w) q β(w) .
Bn (q) =w∈Sn

Theorem 3.11. For all n ≥ 1, we haveBn (q) =n−1
Y(1 − q k )n−k .

k=1

Proof. As before, split Vn (x, λ, q) into two parts:
YX(xi + λq j−i xj ) = Vn (x, λ, q) =χ(G) +
1≤i<j≤nG∈Sn

X

G∈Tn \Sn

χ(G).

166

M. KOBAYASHI

With x1 = · · · = xn = 1 and λ = −1, the second sum vanishes as shownin Lemma 3.7. As a result, we obtainXY(−1)ℓ(w) q β(w)(1 − q j−i ) =1≤i<j≤nw∈Snor
Bn (q) =n−1
Y(1 − q k )n−k .

k=1Corollary 3.12. For n ≥ 3, we haveX(−1)ℓ(w) β(w) = 0.
w∈SnIn other words, the β-statistic is sign-balanced.
Proof. Note that Bn (q) has a factor (1 − q)n−1 with n − 1 ≥ 2. Differentiate
it once and let q = 1. Then we get zero, as required.

Example 3.13. (cf. Reading’s examples in Introduction)
B2 (q) = 1 − q,
B3 (q) = (1 − q)2 (1 − q 2 ) = 1 − 2q + 2q 3 − q 4 ,B4 (q) = (1 − q)3 (1 − q 2 )2 (1 − q 3 )= 1 − 3q + q 2 + 4q 3 − 2q 4 − 2q 5 − 2q 6 + 4q 7 + q 8 − 3q 9 + q 10 .
4. Bigrassmannian determinant
4.1. Definition. Next we want to understand Bn (q) as a new sort of adeterminant as mentioned in Introduction. From now on, we assume that
A = (aij ) = (aij (q)) is an n by n matrix with entries being complex rational
functions in q 1/2 (i.e., elements of C(q 1/2 )). The reason why we introduce
q 1/2 and q −1 will be clearer in the next subsection.
Definition 4.1. The bigrassmannian determinant of A isbdet(A) =Xw∈Snℓ(w) β(w)

(−1)

q

n
Y

aiw(i) .

i=1

We formally define bdet of the 0 by 0 matrix to be 1.

DETERMINANTS AND SIGNED BIGRASSMANNIAN POLYNOMIALSFor example, bdet(a11 ) = a11 , bdet



a11 a12a21 a22

167= a11 a22 − qa12 a21 and
a11 a12 a13
bdet  a21 a22 a23  = a11 a22 a33 − qa12 a21 a33 − qa11 a23 a32
a31 a32 a33
+ q 3 a12 a23 a31 + q 3 a13 a21 a32 − q 4 a13 a22 a31 .

4.2. Matrix deformation. We now give a more explicit description of the
bigrassmannian determinant in terms of the original one. For this purpose,
let us introduce a special term: a deformation of A = (aij ) is a new matrix
f A := (fij (q)aij ) for some indexed family of rational functions f = {fij (q) ∈C(q 1/2 ) | (i, j) ∈ [n] × [n]}. Note that the operation aij 7→ fij (q)aij may not
be C(q 1/2 )-linear in any rows nor columns. Hence it is in general difficult
to predict how determinants change under such an operation. However, as
seen below, there are some nice cases:
2

Definition 4.2. Let b = {bij (q)} = {q (i−j) /2 }. The bigrassmannian deformation of A is bA.
Proposition 4.3. det(bA) = bdet(A).
Proof. By Proposition 3.2, we havedet(bA) =

X

ℓ(w)

(−1)

=

2

q (i−w(i)) /2 aiw(i)

i=1

w∈Sn

X

n
Y

ℓ(w) β(w)

(−1)

w∈Sn

q

n
Y

aiw(i)

i=1= bdet(A).
Theorem 4.4 (a determinantal expression of Bn (q)). We have2

Bn (q) = det(q (i−j) /2 ).
2

Proof. Bn (q) = bdet(1)ni,j=1 = det(b1) = det(q (i−j) /2 ).
Observe determinantal expressions of B3 (q) and B4 (q):1
q 1/2 q 4/2
det  q 1/2
1
q 1/2  = (1 − q)2 (1 − q) andq 4/2 q 1/2
1



168

M. KOBAYASHI

1

 q 1/2det 
 q 4/2
q 9/2


q 1/2 q 4/2 q 9/2
1
q 1/2 q 4/2  = (1 − q)3 (1 − q 2 )2 (1 − q 3 ).
q 1/2
1
q 1/2 q 4/2 q 1/2
1

We should now recognize that different deformations may give the same
determinant: given a family f , there possibly exists g such that g 6= f anddet(f A) = det(gA) for all matrices A. In particular, this is the case for b:
Let b′ = {b′ij } = {q i(i−j) } and b′′ = {b′′ij } = {q j(j−i) } (here we need q −1 ).
Then det(bA) = det(b′ A) = det(b′′ A) as shown just below; since we could
not find any references mentioning this little invariance, we here record it
as a Corollary.
Corollary 4.5. (little invariance of the determinant)2

det(q (i−j) /2 aij ) = det(q i(i−j) aij ) = det(q j(j−i) aij ).
Proof. We only prove the first equality.
nYXi(i−j)ℓ(w)q i(i−w(i)) ai,w(i)det(qaij ) =
(−1)
i=1

w∈Sn

=

X

w∈Sn

ℓ(w) β(w)

(−1)

q

n
Y

2

ai,w(i) = det(q (i−j) /2 aij ).

i=1

Such “equivalent” deformations may be useful for evaluating and under2
standing combinatorial determinants (interpret q (i−j) /2 as area of the triangle (i, i), (i, j) and (j, j) in Z2 ); see Bressoud [2, Section 3.3], Gessel-Viennot[8] and Stembridge [14], for details on Schur functions and nonintersecting
lattice path counting by determinants. We will develop this idea in subsequent publications.
4.3. Weighted condensation. Our next task is to prove weighted condensation for bigrassmannian determinants; this is a natural idea as an analogyof the original determinant (and Robbins-Rumsey [13]). Let A be an n by
n matrix with n ≥ 2. Recall that Aji denotes the submatrix with the i-th
row and j-th column deleted.
Theorem 4.6.
1nn−1
bdet(A)bdet(A1nbdet(A1n )bdet(An1 ).
1n ) = bdet(A1 )bdet(An ) − q

Some comments before the proof: Let A = (aij ), C = bA = (cij ) and2
cij = q (i−j) /2 aij . For simplicity, we use | | for the original determinant.
We will confirm the following five statements.

DETERMINANTS AND SIGNED BIGRASSMANNIAN POLYNOMIALS

169

1n | = bdet(A1n ).
(1) |C1n1n(2) |C11 | = bdet(A11 ).
(3) |Cnn | = bdet(Ann ).
(4) |Cn1 | = q (n−1)/2 bdet(A1n ).
(5) |C1n | = q (n−1)/2 bdet(An1 ).

Once we do this, then the conclusion follows from condensation for theoriginal determinant:
1n|C||C1n| = |C11 ||Cnn | − |Cn1 ||C1n |.
1n | = bdet(A1n ): an (i, j)-entry of C 1n is c
Proof. (1) |C1ni+1,j+1 .
1n1n
2((i+1)−(j+1)) /2
1n| = |ci+1,j+1 |n−2
ai+1,j+1 ||C1ni,j=1 = |q2

= |q (i−j) /2 ai+1,j+1 | = bdet(A1n1n ).
(2) |C11 | = bdet(A11 ): an (i, j)-entry of C11 is ci+1,j+1 .
2((i+1)−(j+1)) /2
ai+1,j+1 ||C11 | = |ci+1,j+1 |n−1i,j=1 = |q2

= |q (i−j) /2 ai+1,j+1 | = bdet(A11 ).
(3) |Cnn | = bdet(Ann ):this is similar to (2).
(4) |Cn1 | = q (n−1)/2 bdet(A1n ): an (i, j)-entry of Cn1 is ci,j+1 .
2(i−(j+1)) /2
ai,j+1 )|Cn1 | = |ci,j+1 |n−1i,j=1 = det(q2= |q ((i−j) −2(i−j)+1)/2 ai,j+1 | = q −

P

i+

P

j (n−1)/2q

2|q (i−j) /2 ai,j+1 |= q (n−1)/2 bdet(A1n ).
(5) |C1n | = q (n−1)/2 bdet(An1 ): this is similar to (4).

Now we see an immediate consequence which is, however, not so obvious
from the definition of Bn (q).
Corollary 4.7. Signed bigrassmannian polynomials can be defined recurBn−1 (q)2
sively as follows: B1 (q) = 1, B2 (q) = 1 − q and Bn (q) =(1 − q n−1 )Bn−2 (q)for n ≥ 3.
Proof. Apply the weighted condensation to A = (1)ni,j=1 . All four determinants in the numerator are Bn−1 (q) while the denominator is Bn−2 (q). 170

M. KOBAYASHI

5. Concluding remarks
In this article, we introduced two new ideas, signed bigrassmannian polynomials and bigrassmannian determinant. We made use of tournaments aswell as Vandermonde determinant to find Bn (q). Then we introduced bdet
as a q-analog of determinant as q → 1 recovers the original one. Thanks
to formulas of β-statistic, we obtained a determinantal expression of Bn (q).
Moreover, we established weighted condensation as an analogyof RobbinsP
Rumsey. After all, we did not find the unsigned statistic w∈Sn q β(w) . Now
an easy guess is to use the permanent instead. We leave this problem here
for our future research.
We end with some more comments for subsequent work.
• What is missing in our discussion is an alternating sign matrix(ASM) [3, 12]. Since inversions and bigrassmannian statistics also
make sense for ASMs, we want to generalize some of our results tothese matrices (note: we can extend β for ASMs as the rank functionof a distributive lattice. For example, what can we say about bdet
for ASMs which are not permutations?
• We can also define “λq-determinant” by replacing λ with λq n−1 inRobbins-Rumsey condensation (provided all such minors
Q are nonzero).
Then we would obtain polynomials of the form (1 + λq k )n−k ,say Bn (λ, q). Then we can show as Corollary 4.7 that polynomials {Bn (λ, q)} satisfies
Bn (λ, q) =Bn−1 (λ, q)2(1 + λq n−1 ).
Bn−2 (λ, q)

Recently, there appeared such recursions and polynomials in the literature on Aztec diamonds, perfect matchings and domino tilings;
see Brualdi-Kirkland [4], Ciucu [5] and Elkies-Kuperberg-LarsenPropp [6], for example. It would be nice to give an explicit connection between such work and our results.
• As we mentioned Bruhat order, symmetric groups are Coxeter groupsof type A. It makes sense to speak of a signed bigrassmannian statistic even in other situations: let (W, S, ≤) be a finite Coxeter systemwith Coxeter generators S specified and ≤ Bruhat order. Defineℓ(w) = min{l ≥ 0 | w = s1 · · · sl , si ∈ S} and the sign of w tobe (−1)ℓ(w) . Say w is bigrassmannian if there exists a unique pair(s1 , s2 ) ∈ S × S such that ℓ(s1 w) < ℓ(w) and ℓ(ws2 ) < ℓ(w). Define
B(w) = {u bigrassmannian | u ≤ w} and β(w) = |B(w)| in the samePway. Find a statistic w∈W q β(w) .

DETERMINANTS AND SIGNED BIGRASSMANNIAN POLYNOMIALS

171

Figure 2. Rothe diagram for 35241
◦

◦

•

◦

◦

◦

◦

◦

◦

•

◦

•

◦

◦

◦

◦

◦

◦

•

◦

•

◦

◦

◦

◦

• We can think that each permutation
Pw gives a partition of an integerβ(w) with ℓ(w) parts as β(w) =(i,j)∈N (w) (j − i); see AndrewsEriksson [1] for the theory of integer partitions. Then, it is natural to come to the following idea: Rothe diagram for w is the set{(i, j) ∈ [n] × [n] | i < w−1 (j) and j < w(i)}. As is well-known,
the cardinality of this set is ℓ(w). Figure 2 shows an example; sevencircles which does not cross any lines are elements of Rothe diagram
for w = 35241 (with β(w) = 15). Is there any formula to compute βfrom Rothe diagrams?
Acknowledgement
The author thanks the anonymous referee for careful reading and advisorycomments.
References[1] G. E. Andrews and K. Eriksson, Integer partitions, Cambridge University Press,
Cambridge, 2004.
[2] D. Bressoud, Proofs and confirmations, The story of the alternating sign matrix
conjecture, Cambridge University Press, Cambridge, 1999.
[3] D. Bressoud and J. Propp, How the alternating sign matrix conjecture was solved,
Notices Amer. Math. Soc. 46 (1999), no. 6, 637–646.
[4] R. Brualdi and S. Kirkland, Aztec diamonds and digraphs, and Hankel determinantsof Schröder numbers, J. Comb. Th. Ser. B 94 (2005), no. 2, 334–351.
[5] M. Ciucu, A complementation theorem for perfect matchings of graphs having acellular completion, J. Comb. Th. Ser. A 81 (1998), no. 1, 34–68.

172

M. KOBAYASHI[6] N. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices anddomino tilings, Part I and II, J. Alg. Comb. 1 (1992), no. 2, 111–132 and no. 3,
219–234.
[7] M. Geck and S. Kim, Bases for the Bruhat-Chevalley order on all finite Coxeter
groups, J. Algebra 197 (1997), no. 1, 278–310.
[8] I. Gessel and G. Viennot, Binomial determinants, paths, and hook length formulae.
Adv. Math. 58 (1985), no. 3, 300–321.
[9] M. Kobayashi, Enumeration of bigrassmannian permutations below a permutation in
Bruhat order, Order 28 (2011), no. 1, 131–137.
[10] A. Lascoux and M-P. Schützenberger, Treillis et bases des groupes de Coxeter(French), Electron. J. Combin. 3 (1996), no. 2, Research paper 27, 35 pp.
[11] N. Reading, Order dimension, strong Bruhat order and lattice properties for posets,
Order 19 (2002), no. 1, 73–100.
[12] D. Robbins, the story of 1, 2, 7, 42, 429, 7436, . . . , Math. Intelligencer 13 (1991), no.
2, 12–19.
[13] D. Robbins and H. Rumsey, Determinants and alternating sign matrices, Adv. Math.
62 (1986), no. 2, 169–184.
[14] J. Stembridge, Nonintersecting paths, Pfaffians, and plane partitions, Adv. Math. 83(1990), no. 1, 96–131.
Masato Kobayashi
Graduate School of Science and Engineering Department of Mathematics
Saitama University, 255 Shimo-Okubo, Saitama 338-8570, Japan.
e-mail address: kobayashi@math.titech.ac.jp(Received May 28, 2013 )(Revised October 4, 2013 )