A STRAIGHTENING FORMULA FOR QUANTIZED CODETERMINANTS

By R. M. Green

Mathematical Institute, 24–29 St. Giles’, Oxford OX1 3LB, U.K.

0. Introduction

J.A. Green [6, §4] introduces codeterminants, which are products of pairs of natural basis elements of the Schur algebra S(n, r). These are shown to be parametrised by pairs of row-semistandard tableaux of shape λ, where λ ∈ Λ(n, r). If both the tableaux are standard, and the composition λ is dominant, then the codeterminant is said to be standard. The set of standard codeterminants forms a free Z-basis for the integral form of the classical Schur algebra. An algorithm for expressing an arbitrary codeterminant as a sum of standard ones has been described in [9].

It is natural to ask whether these results quantize. In this paper, we prove that they do. The Schur algebra has a quantum analogue, the so-called q-Schur algebra, S_{q}(n, r), which is defined over the ring Z[q, q^{−1}]. We will also be working with the v-Schur algebra, which is A ⊗ S_{q}(n, r), where A = Z[v, v^{−1}] and v^{2} = q. An algorithm to compute products in these algebras was established in [7]. We define codeterminants for these algebras in an analogous way to Green [6], and after a careful analysis of certain products in S_{v}(n, r), we state and prove a straightening formula for them, and exhibit a free basis of codeterminants for S_{q}(n, r).

The rest of this paper falls into three sections. §1 consists of definitions and a summary of some of the important results in [7]. In §2, we show that any codeterminant can be expressed as a Z[q, q^{−1}]-linear sum of codeterminants of dominant shape. In §3, we prove a quantum analogue of the straightening formula for codeterminants. This is a procedure for expressing any codeterminant of dominant shape as a Z[q, q^{−1}]-linear sum of standard codeterminants. This was proved by Woodcock [9] in the classical case. We use some of the techniques in that paper to prove the quantum analogue, but some steps are considerably more delicate and require new methods.

1. Preliminaries 1.1 The Classical Schur Algebra

The classical Schur algebra, S(n, r) has a basis consisting of certain elements ξ_{i,j} which are defined (as in Green [5, §2.3]) as follows.

Let I(n, r) be the set of all ordered r-tuples of elements from the set n := {1, …, n}. (Elements of I(n, r) will be denoted by bold letters or by using the symbol ℓ, to avoid confusion with integers. The elements of i ∈ I will be denoted by i_{1}, i_{2} etc.) The symmetric group S_{r} acts on the set I = I(n, r) on the right by place permutation via

(i_{1}, …, i_{r}).π := (i_{(1)π}, …, i_{(r)π}).

It also acts on the set I × I as (i, j)π = (iπ, jπ). We write i ∼ j if i and j are in the same S_{r}-orbit of I, and (i, j) ∼ (i′, j′) if (i, j) and (i′, j′) are in the same S_{r}-orbit of I × I. The subscripts i and j of the element ξ_{i,j} lie in I(n, r), and we identify ξ_{i,j} and ξ_{i′,j′} if and only if (i, j) ∼ (i′, j′). The set of all ξ_{i,j}, as (i, j) ranges over a transversal Ω of all S_{r}-orbits of I × I can be shown (see e.g. [5, §2.3]) to be a basis for S(n, r). We will usually write ξ_{l} as shorthand for ξ_{l,l}.

Schur’s product rule for the basis {ξ_{i,j}} is given by

ξ_{i,j}ξ_{k,l} = ∑_{p,q∈Ω} Z(i, j, k, l, p, q)ξ_{p,q},

where Z(i, j, k, l, p, q) := |{s ∈ I : (i, j) ∼ (p, s) and (k, l) ∼ (s, q)}|.

The basis for S(n, r) described above can be thought of in a different way, this time indexed by the set Θ_{r} of n × n matrices with nonnegative integer entries summing to r. A typical basis element will be denoted by e_{A}, where A is the matrix in question.

Let i = (i_{1}, …, i_{r}) and j = (j_{1}, …, j_{r}) be elements of I. The correspondence between the two bases is given by

ξ_{i,j} = e_{A},

where the (x, y)-entry of the matrix A is given by the number of pairs (i_{s}, j_{s}) such that i_{s} = x and j_{s} = y.

1.2 The parameters q and v

Following Du [4], we define A := Z[v, v^{−1}], and q = v^{2}. It will often be the case in the proofs that follow that it is easier initially to work over A and deduce the corresponding results involving Z[q, q^{−1}] from them. The reason for this is that the basis {e_{A}} for S_{q}(n, r) is free over the ring Z[v, v^{−1}], and hence over Z[q, q^{−1}]. The motivation behind casting the results into the form involving q is that when the q-Schur algebra is studied in its own right, it is often the case that we do not need to introduce v, which is a square root of q. We will use the notation S_{v}(n, r) when we wish to emphasise the fact that we are working over A.

Sometimes we will write v^{∗} to denote some integer power of v, but usually no attempt will be made to keep track of the exact value of this quantity, because it isn’t important for the purposes of the proof. The value of v^{∗} may change from line to line during the proof.

1.3 The q-Schur algebra, S_{q}(n, r)

We now define (following [4] or [1, Proposition 1.2]) the q-Schur algebra, S_{q}(n, r), to be the Q(v)-vector space with basis {e_{A} : A ∈ Θ_{r}} with associative multiplication given by

e_{A}e_{A′} = ∑_{A′′∈Θ_{r}} g_{A,A′,A′′}e_{A′′},

where the structure constants g_{A,A′,A′′} are certain polynomials in Z[q] arising from the geometry of flags.

Du [4] remarks that this algebra is canonically isomorphic to the q-Schur algebra defined by Dipper and James, by exhibiting the following correspondence between basis elements e_{A} and basis elements ϕ_{λμ}^{d} as defined by Dipper and James in [3]. Here, the elements λ and μ lie in Λ(n, r), which is the set of compositions of r into n parts, and d ∈ D_{λμ}, which is the set of distinguished W_{λ}–W_{μ} double coset representatives for the Young subgroups W_{λ} and W_{μ} of S_{r}, the symmetric group on r letters. Suppose λ = (λ_{1}, …, λ_{n}) and μ = (μ_{1}, …, μ_{n}). For each α ∈ n, we define I_{α} to be the subset of n given by

I_{α} := {λ_{1} + ⋯ + λ_{α−1} + 1, λ_{1} + ⋯ + λ_{α−1} + 2, …, λ_{1} + ⋯ + λ_{α}}.

Similarly, we define J_{α} to be the analogous subset of n corresponding to μ and α. Given a Dipper-James basis element, ϕ_{λμ}^{d}, we define a corresponding matrix A via

A_{αβ} := |d(J_{β}) ∩ I_{α}|.

This procedure sets up the required isomorphism by sending ϕ_{λμ}^{d} to e_{A}. It should be noted that λ corresponds to the sums of the rows of A, and μ to the sums of the columns of A.

In this paper, we will prefer to think of these basis elements e_{A} as elements ξ_{i,j} (as in the classical case), where the e_{A} and ξ_{i,j} are identified as in §1.1.

1.4 Coxeter Groups and Hecke Algebras

We consider W = S_{r}, the symmetric group on r letters, as a Coxeter group with generators S = {s_{1}, …, s_{r−1}} (where s_{i} is the transposition (i, i + 1)) and defining relations

s_{i}^{2} = 1;
s_{i}s_{j} = s_{j}s_{i} if |i − j| > 1;
s_{i}s_{j}s_{i} = s_{j}s_{i}s_{j} if |i − j| = 1.

This makes (W, S) into a Coxeter system, and W into a Coxeter group.

Define the length of w ∈ W, denoted by ℓ(w), to be the smallest r for which an expression w = s_{i_{1}} ⋯ s_{i_{r}} exists. Such a minimal expression for w is called a reduced expression. It is well-known that the length of w is also given by the cardinality of the set

{⟨i, j⟩ : i < j, (i)w > (j)w}.

Thus we have the following identities:

ℓ(s_{i}w) = \{ \begin{matrix}ℓ(w) + 1 & if iw < (i + 1)w; \\ ℓ(w) − 1 & if iw > (i + 1)w; \end{matrix}
ℓ(ws_{i}) = \{ \begin{matrix}ℓ(w) + 1 & if iw^{−1} < (i + 1)w^{−1}; \\ ℓ(w) − 1 & if iw^{−1} > (i + 1)w^{−1}. \end{matrix}

We now introduce the Hecke algebra H(W) corresponding to the Coxeter group W. This has basis elements T_{w} parametrised by w ∈ W, and the following multiplication rules:

T_{s}T_{w} = \{ \begin{matrix}T_{sw} & if ℓ(sw) > ℓ(w); \\ qT_{sw} + (q − 1)T_{w} & if ℓ(sw) < ℓ(w). \end{matrix}

The existence of this algebra structure is proved in [8, §7]. It follows from the relations that if w = s_{i_{1}} ⋯ s_{i_{r}} is reduced, then T_{w} = T_{s_{1}} ⋯ T_{s_{r}}. It

also follows that if ℓ(uw) = ℓ(u) + ℓ(w) then T_{uw} = T_{u}T_{w}.

Notice that when q is replaced by 1, the algebra H = H(W) is canonically isomorphic to the group algebra of W.

The following property of Hecke algebras will be used in this paper. Lemma 1.1 Let d ∈ W. Then

T_{d}. ( ∑_{w∈W} T_{w}) = q^{ℓ(d)}. ( ∑_{w∈W} T_{w}) .

Proof This is well-known (see [2, §3.2]) and follows by induction on ℓ(d).

Let W′ be a subgroup of a Coxeter group W. Define

x_{W′} := ∑_{w∈W′} T_{w}.

1.5 Tensor Space

Let V be the Q(v)-vector space with basis {e_{1}, …, e_{n}}. Following [4], we make T^{r}(V) = V^{⊗r} into a right H-module by defining e_{i_{1}} ⊗ ⋯ ⊗ e_{i_{r}}.T_{p,p+1} as

\{ \begin{matrix}ve_{i_{1}} ⊗ ⋯ ⊗ e_{i_{p+1}} ⊗ e_{i_{p}} ⊗ ⋯ ⊗ e_{i_{r}} & if i_{p} < i_{p+1}; \\ v^{2}e_{i_{1}} ⊗ ⋯ ⊗ e_{i_{r}} & if i_{p} = i_{p+1}; \\ ve_{i_{1}} ⊗ ⋯ ⊗ e_{i_{p+1}} ⊗ e_{i_{p}} ⊗ ⋯ ⊗ e_{i_{r}} + (v^{2} − 1)e_{i_{1}} ⊗ ⋯ ⊗ e_{i_{r}} & if i_{p} > i_{p+1}. \end{matrix}

We will also write u_{i} for e_{i_{1}} ⊗ ⋯ ⊗ e_{i_{r}}, where i is the element of I(n, r) given by (i_{1}, …, i_{r}).

Define the function m : I(n, r) → Z by

m(i) := |{⟨a, b⟩ : 1 ≤ a < b ≤ r : i_{a} > i_{b}}|.

We will write [u_{i}] for v^{−m(i)}u_{i}.

The action of H can now be re-expressed as follows. Let s = (p, p + 1). Then

[u_{i}].T_{s} = \{ \begin{matrix}q[u_{i.s}] & if i_{p} ≤ i_{p+1}; \\ [u_{i.s}] + (q − 1)[u_{i}] & if i_{p} > i_{p+1}. \end{matrix}

The action of T_{s}^{−1} is also easy to describe:

[u_{i}].T_{s}^{−1} = \{ \begin{matrix}q^{−1}[u_{i.s}] & if i_{p} ≥ i_{p+1}; \\ [u_{i.s}] + (q^{−1} − 1)[u_{i}] & if i_{p} < i_{p+1}. \end{matrix}

1.6 Tensor Matrix Space

Consider the Q(v)-vector space with basis {u_{i,j} : i, j ∈ I(n, r)}. This has an associative multiplication defined on it by u_{i,j}u_{k,l} := δ_{j,k}u_{i,l}. We call the resulting algebra tensor matrix space, and denote it by T^{r}(M_{n}), because it is canonically isomorphic to the r-th tensor power of the matrix ring M_{n}(Q(v)) via the map σ defined by

σ(u_{i,j}) = e_{i_{1}j_{1}} ⊗ ⋯ ⊗ e_{i_{r}j_{r}}.

The algebra T^{r}(M_{n}) has another basis, which we shall call the quantized basis, consisting of the set {[u_{i,j}] : i, j ∈ I(n, r)}. The element [u_{i,j}] is defined to be v^{−m(i)−m(j)}u_{i,j} where the function m is as in 1.5.

It was shown in [7, Lemma 3.1] that T^{r}(M_{n}) admits a right H-module structure which we now describe. Let T_{s} = T_{(p,p+1)}. Then:

[u_{i,j}].T_{s} = \{ \begin{matrix}q[u_{i.s,j.s}] & if i_{p} ≤ i_{p+1} and j_{p} ≤ j_{p+1};  (1) \\ [u_{i.s,j.s}] + (q − 1)[u_{i,j}] & if i_{p} > i_{p+1} and j_{p} > j_{p+1};  (2) \\ [u_{i.s,j.s}] + (q − 1)[u_{i,j.s}] & if i_{p} > i_{p+1} and j_{p} ≤ j_{p+1};  (3) \\ q[u_{i.s,j.s}] + (q − 1)[u_{i,j}] − (q − 1)[u_{i,j.s}] & if i_{p} ≤ i_{p+1} and j_{p} > j_{p+1}.  (4) \end{matrix}

From this, the action of T_{(p,p+1)}^{−1} immediately follows. We find that [u_{i,j}].T_{s}^{−1} is given by

q^{−1}[u_{i.s,j.s}]  if i_{p} ≥ i_{p+1} and j_{p} ≥ j_{p+1};  (5)
[u_{i.s,j.s}] + (q^{−1} − 1)[u_{i,j}]  if i_{p} < i_{p+1} and j_{p} < j_{p+1};  (6)
[u_{i.s,j.s}] + (q^{−1} − 1)[u_{i,j.s}]  if i_{p} < i_{p+1} and j_{p} ≥ j_{p+1};  (7)
q^{−1}[u_{i.s,j.s}] + (q^{−1} − 1)[u_{i,j}] − (q^{−1} − 1)[u_{i,j.s}] if i_{p} ≥ i_{p+1} and j_{p} < j_{p+1}.  (8)

Note

Notice that this action specialises (when q and v are replaced by 1) to permutation, and that any basis element occurring with nonzero coefficient in u_{a,b}.T_{w} is of form u_{c,d} where a ∼ c and b ∼ d.

1.7 Parabolic subgroups

Consider a Coxeter system (W, S). For any subset I ⊂ S, we can define a subgroup W_{I} of W, generated by the set I. This is called a parabolic subgroup of W. Parabolic subgroups have various important properties (see [8, Theorem 5.5]); the most important of these for our purposes is the following.

Let I ⊂ S. If w = s_{i_{1}} ⋯ s_{i_{r}} (s_{i} ∈ S) is a reduced expression, and w ∈ W_{I}, then all s_{i} ∈ I. In particular, the function ℓ agrees with the length function ℓ_{I} on W_{I}, and W_{I} ∩ S = I.

We say that a typical basis element u_{i,j} of T^{r}(M_{n}) is of parabolic form if the stabilizer of j under the action of S_{r} on I(n, r) is a parabolic subgroup. We will also say in this case that the element j is of parabolic form. An equivalent way of looking at this is that if 1 ≤ a < b < c ≤ r and j_{a} = j_{c}, then j_{a} = j_{b} = j_{c}.

1.8 Two orders

Let A and B be ordered sets. Then the Hebrew lexicographic order on A × B is given by ⟨a, b⟩ < ⟨c, d⟩ if and only if b < d or (b = d and a < c). The elements of a sequence (i_{1}, …, i_{m}) in A × B are said to appear in Hebrew lexicographic order if i_{1} ≤ ⋯ ≤ i_{r} with respect to this order.

A basis element u_{i,j} of T^{r}(M_{n}) is said to be H-relaxed if the elements of the sequence (⟨i_{1}, j_{1}⟩, …, ⟨i_{r}, j_{r}⟩) appear in Hebrew-lexicographic order.

Let A and B be ordered sets. Then the relaxed order on A×B is given by ⟨a, b⟩ < ⟨c, d⟩ if and only if b < d or (b = d and a > c). The elements of a sequence (i_{1}, …, i_{m}) in A × B are said to appear in relaxed order if i_{1} ≤ ⋯ ≤ i_{r} with respect to this order.

A basis element u_{i,j} of T^{r}(M_{n}) is said to be relaxed if the elements of the sequence (⟨i_{1}, j_{1}⟩, …, ⟨i_{r}, j_{r}⟩) appear in the relaxed order.

Examples Let j = (1, 1, 1, 1, 3, 3, 3, 7, 7, 7).

If i = (1, 4, 6, 7, 2, 4, 5, 3, 3, 4) then u_{i,j} is H-relaxed.
If i′ = (7, 6, 4, 1, 5, 4, 2, 4, 3, 3) then u_{i′,j} is relaxed.

Note

Under the canonical identifications, these definitions of relaxed and H-relaxed agree with those in [7, §3].

1.9 Quantized codeterminants and combinatoric definitions

A quantized codeterminant, or q-codeterminant, is an element e_{A}e_{A′} of the q-Schur algebra S_{q}(n, r) which is a nonzero product of two natural basis elements e_{A} and e_{A′}. (The quantized codeterminant is determined by the matrices A and A′, and not solely by the element of S_{q}(n, r) which is equal to it.)

The above discussion shows that this definition specialises (when q is replaced by 1) to the classical definition of codeterminants. We will show in this paper that the quantized codeterminants as defined above exhibit some of the important properties of their classical counterparts.

In keeping with the classical literature on codeterminants, we will tend to follow the notation of [6]. We therefore need to make a few more definitions, many analogous to the ones in [6], before motivating the main results of this paper.

It is convenient to introduce

Λ = Λ(n, r) := {λ = (λ_{1}, …, λ_{n}) : λ_{ν} ∈ N_{0} for all ν ∈ n, and ∑_{ν=1}^{n} λ_{ν} = r}

and

Λ^{+} = Λ^{+}(n, r) := {λ ∈ Λ(n, r) : λ_{1} ≥ ⋯ ≥ λ_{n}}.

(Here, N_{0} is the set of natural numbers, including 0.)

An element λ of Λ is called a weight, and is dominant if λ ∈ Λ^{+}. There is an obvious correspondence between elements of Λ^{+} and partitions of r into not more than n parts.

The lexicographic order on Λ is defined as follows. μ ≻ λ if for some c, μ_{a} = λ_{a} for all a < c, and μ_{c} > λ_{c}.

The weight wt(i) of an element i ∈ I(n, r) is the element α ∈ Λ given by α_{ν} = |{ρ ∈ r : i_{ρ} = ν}| for all ν ∈ n. If i, j ∈ I, it is clear that i ∼ j if and only if wt(i) = wt(j).

For each λ ∈ Λ^{+} we define the basic λ-tableau T^{λ} by writing the integers 1, …, r into a Young diagram row by row, starting with the top row, and filling each row from left to right. To each i ∈ I we now associate the λ-tableau T_{i}^{λ} = iT^{λ}. For example, let n = 4, r = 7, λ = (4, 2, 1, 0). Then

T^{λ} = 1 5 7 2 6 3 4 ,

and

T_{i}^{λ} = i_{1} ; i_{5} ; i_{7} i_{2} ; i_{6} i_{3} i_{4} .

If λ ∈ Λ^{+} and i ∈ I, the λ-tableau T_{i}^{λ} is said to be standard if the elements in each row increase weakly from left to right, and the elements in each column increase strictly from top to bottom. We define

I_{λ} := I_{λ}(n, r) = {i ∈ I : T_{i}^{λ} is standard}.

We say a λ-tableau T_{i}^{λ} is row-semistandard if the elements in each row increase weakly from left to right, and define the set

I′_{λ} := I′_{λ}(n, r) = {i ∈ I : T_{i}^{λ} is row-semistandard}.

It is clear that in a standard tableau, all the entries equal to s must appear in the first s rows, by an easy induction on s. There is exactly one element of I, denoted by ℓ = ℓ(λ), for which T_{ℓ}^{λ} is standard and wt(ℓ) = λ. (The entries in the s-th row of the tableau T_{ℓ}^{λ} are all equal to s.)

The elements of I can be lexicographically ordered as follows: i ⪰ j if and only if i = j or, if ρ is minimal subject to the condition that i_{ρ} ≠ j_{ρ}, then i_{ρ} < j_{ρ}.

It is clear for any p ∈ I that p ∼ ℓ(wt(p)). Thus, any basis element ξ_{a,b} can be written as ξ_{i,ℓ(μ)} where μ = wt(b), or as ξ_{ℓ(ν),j} where ν = wt(a). The product ξ_{a,b}ξ_{c,d} will be zero unless b ∼ c, and hence wt(b) = wt(c), so it is easy to see that a general codeterminant can be written as

Y_{i,j}^{λ} := ξ_{i,ℓ(λ)}ξ_{ℓ(λ),j},

where i, j ∈ I and λ ∈ Λ. We say that Y_{i,j}^{λ} is a codeterminant of shape λ. If, in addition, λ ∈ Λ^{+} and i and j lie in I_{λ}, we call the codeterminant Y_{i,j}^{λ} a standard codeterminant. It should be noted that if b ∼ c then ξ_{a,b}ξ_{c,d} is nonzero, because it specialises when q is replaced by 1 to an element of S(n, r) which can be seen to be nonzero using Schur’s product rule.

It is convenient to introduce the following elements of Z[q], as in [2].

a) For an nonnegative integer n, [n]_{q} := 1 + q + ⋯ + q^{n−1}.

b) Define [n]_{q}! := [1]_{q}[2]_{q} ⋯ [n]_{q}.

Let a, b ∈ I(n, r). Then the element P_{a,b} ∈ Z[q] is defined to be

∏_{i,j=1}^{n}[c_{ij}]_{q}!,

where c_{ij} is the multiplicity of ⟨i, j⟩ in the family {⟨a_{1}, b_{1}⟩, …, ⟨a_{r}, b_{r}⟩}. If t = u_{a,b} then P_{t} := P_{a,b}.

1.10 Computation of products in S_{v}(n, r)

In [7, §3], it was shown how to embed the algebra S_{v}(n, r) into T^{r}(M_{n}), and, since T^{r}(M_{n}) has a convenient multiplication defined on it, this was shown to give an algorithm for computing products in S_{v}(n, r). We summarise the most important results in [7] for use in this paper, although the notation differs somewhat.

Let A be a basis matrix for S_{v}(n, r). Define the integer

m_{A} := ∑_{i,j,k} A_{i,k}A_{j,k},

where the sum is taken over all i, j, k ∈ {1, …, n} subject to the condition i < j. Define the integer

s_{A} := ∑_{1≤i,j,k,l≤n} A_{i,j}A_{k,l},

where the sum is taken with the restrictions that i ≥ k and j < l.

Proposition 1.2 Let W denote the Coxeter group of type A_{r−1}. Suppose u_{i,j} is Hrelaxed. Let (i′, j) be the unique relaxed element satisfying

(i, j) ∼ (i′, j).

(i) The linear map γ : S_{v}(n, r) → T^{r}(M_{n}) given by

γ(ξ_{i,j}) := v^{s_{A}−m_{A}}u_{i,j}.\frac{x_{W}}{P_{i,j}}

is a monomorphism of algebras. (It should be noted there are many ways of expressing a basis element ξ_{i,j}, and that this formula is only valid when the subscripts i and j occurring satisfy the condition that u_{i,j} is H-relaxed. Each basis element can be expressed in this form in a unique way.)

(ii) im(γ) coincides with the largest H-submodule of T^{r}(M_{n}) affording the ind representation of H (i.e. the representation mapping all T_{s_{i}} to q.) We shall later refer to this submodule as the ind submodule. Working over the field Q(v), this submodule is given by T^{r}(M_{n}).x_{W} .

(iii) Let ξ_{i,j} = e_{A}. The coefficient of u_{i,j} in γ(e_{A}) is v^{s_{A}−m_{A}}. The coefficient of u_{i′,j} in γ(e_{A}) is v^{s_{A}}. There are no other relaxed or H-relaxed basis elements which appear with nonzero coefficients in γ(e_{A}).

Proof The elements [A] ∈ S_{v}(n, r) used in [7] satisfy e_{A} = v^{s_{A}}[A], as was shown in [7, §3].

The assertions of (i) now follow from [7, Theorem 3.9]. The assertions of (ii) follow from [7, Lemma 3.8 (a)]. For the proof of (iii), see [7, Corollary 3.7].

In some of the proofs in this paper, we will use the technique of proving that an element w ∈ W satisfies a certain property P by “induction on left subwords of w.” The idea is as follows. Let s_{i_{1}} ⋯ s_{i_{m}} be any fixed reduced expression for w. We then prove by induction on p (where 1 ≤ p ≤ m) that the element w_{p} defined by s_{i_{1}} ⋯ s_{i_{p}} satisfies the property P; this then proves that w has the required property. It is immediate from the properties of Coxeter groups that if w is a right coset representative of minimial length with respect to some parabolic subgroup of W, then so are all its left subwords. It is also immediate that if w lies in some parabolic subgroup W_{P} of W, then so do all its left subwords.

Proposition 1.3

Suppose that j_{a} ≤ j_{b} when a < b. Then j is of parabolic form, with stabiliser W_{J}, and (i) If u_{a,j} occurs with nonzero coefficient in u_{i,j}.T_{w} for some w then (a, j) ∼ (i, j). (ii) If w ∉ W_{J}, then the coefficient of u_{a,j} in u_{i,j}.T_{w} is zero for all a ∈ I(n, r).

Now suppose u_{i,j} is H-relaxed, and let W_{P} be the parabolic subgroup which is the stabiliser of (i, j). Let W_{J} be the parabolic subgroup which is the stabiliser of j. Let e_{A} be the basis element of S_{q}(n, r) corresponding to ξ_{i,j}. The following two remarks now hold. (iii) Suppose (a, j) ∼ (i, j). Then the coefficient of u_{a,j} in γ(ξ_{i,j}) is v^{s_{A}−m} where

m := |{⟨c, d⟩ : j_{c} = j_{d}, a_{c} < a_{d}}|.

(iv) Suppose w ∈ D_{P} ∩ W_{J}. Then u_{i,j}.T_{w} = v^{ℓ(w)}u_{i.w,j.w}. Proof

Observe that any basis element occurring with nonzero coefficient in u_{i,j}.T_{w} is of form u_{a,j.w}. This follows by induction on left subwords of w. Also observe that if w ∈ W_{J} then u_{i,j}.T_{w} is of form u_{a,j} where (a, j) ∼ (i, j), also by induction on left subwords of w. This is enough to prove (i) and (ii).

The assertions (iii) and (iv) follow from [7, Lemma 3.6] and its proof.

2. Hecke algebras and codeterminants of dominant shape Lemma 2.1 Let t = u_{a,b} (where a, b ∈ I(n, r)) be a basis element of T^{r}(M_{n}) of parabolic form. Then

y := t.\frac{x_{W}}{P_{t}}

lies in S_{v}(n, r). Moreover, if t is expressed as an A-linear sum of elements ξ_{i,j}, then all elements occurring with nonzero coefficients in the sum satisfy i ∼ a and j ∼ b. Proof Lemma 1.1 shows that

T_{d}x_{W} = q^{ℓ(d)}x_{W} ,

where W is the Coxeter group of type A_{r−1}. We now find that y lies in the ind submodule of T^{r}(M_{n}), and hence in S_{v}(n, r) by Proposition 1.2 (ii). This proves that t is a Q(v)-linear combination of elements ξ_{i,j}. Thanks to Proposition 1.2 (iii), it is now enough to show that the coefficients of the relaxed basis elements occurring in y lie in A, because that will force the coefficient of each ξ_{i,j} to lie in A.

Define W_{J} to be the parabolic subgroup of W generated by the (p, p + 1) satisfying b_{p} = b_{p+1}. Let t_{0} be the unique element of form u_{a′,b} satisfying (a′, b) ∼ (a, b) and the condition that if b_{p} = b_{p+1} then a′_{p} ≤ a′_{p+1}. Let W_{I} be the parabolic subgroup of S_{r} stabilising t_{0}. There exists a unique w ∈ D_{I} ∩ W_{J} such that a′.w = a. Then we see by induction on left subwords of w that u_{a′,b}.T_{w} = v^{∗}u_{a,b}, as required. By substituting t_{0} for t in the definition of y, and by using the observation that if a ∈ A then v^{m}a ∈ A for any m ∈ Z, we find that it is enough to prove the lemma in the case where t = t_{0}, because P_{t} = P_{t_{0}}.

We now assume t = t_{0} and define the parabolic subgroup W_{I} to be generated by all (p, p + 1) such that a′_{p} = a′_{p+1} and b_{p} = b_{p+1}. Let D_{I} be the set of distinguished right coset representatives corresponding to W_{I}, that is, the set

D_{I} = {w ∈ W : ℓ(sw) > ℓ(w) for all s ∈ I}.

By using a reversed version of [8, Proposition 1.10], we find that for any w ∈ W, there exists a unique a ∈ W_{I} and b ∈ D_{I} such that w = ab and ℓ(w) = ℓ(a) + ℓ(b). Each element of D_{I} is the unique element of minimal length in its right coset. It follows that

x_{W} = x_{I} ( ∑_{u∈D_{I}} T_{u}) .

The Poincaré polynomial W (z) associated to the Coxeter system (W, S) is defined to be

W (z) := ∑_{n≥0} a_{n}z^{n} = ∑_{w∈W} z^{ℓ(w)},

where a_{n} := |{w ∈ W : ℓ(w) = n}|. We know (see for example, [8, §3.15]) that the Poincaré polynomial of a Coxeter group of type A_{l} is

∏_{i=1}^{l} ∑_{k=0}^{i} z^{k},

and we also know that W_{I}, being a parabolic subgroup of a Coxeter group of type A, is canonically isomorphic to a direct product of such groups of smaller rank. Its Poincaré polynomial is therefore a product of expressions such as those given above. By substituting z = q, we obtain the scalar by which ∑_{u∈W_{I}} T_{u} acts, and we find that

t.x_{I} = P_{t}.t.

This means that

y = t. ( ∑_{u∈D_{I}} T_{u}) ,

and hence, since the action of H on T^{r}(M_{n}) is defined over A, that the coefficients of any basis elements occurring in y, in particular the relaxed ones, lie in A.

The last assertion follows from Proposition 1.2 (iii) and the Note at the end of §1.6.

Definition Let i, j ∈ I(n, r) be given by i = (i_{1}, …, i_{r}) and j = (j_{1}, …, j_{r}). Then the element τ_{i,j} ∈ T^{r}(M_{n}) is defined as

τ_{i,j} := u_{i,j}.\frac{x_{W}}{P_{i,j}} .

If j is of parabolic form, we know from Lemma 2.1 that τ_{i,j} can be considered to lie in S_{v}(n, r).

Note that if the u_{i,j} constructed above is H-relaxed, then τ_{i,j} is equal to ξ_{i,j} multiplied by a certain power of v.

Also note that Lemma 2.1 tells us that each element τ_{i,j} is of form

∑ c_{i′,j′}ξ_{i′,j′},

where the elements c_{i′,j′} lie in A, and the indices i′ and j′ satisfy i′ ∼ i and j′ ∼ j.

During the proofs that follow, we shall need a way of testing whether two elements of H are equal to each other. To do this, we construct a right H-module M with the property that there exist certain elements m ∈ M such that if h_{1}, h_{2} ∈ H and m.h_{1} = m.h_{2} then h_{1} = h_{2}. By linearity, it is enough to show that if m.h = 0 then h = 0.

Lemma 2.2 Let V be a Q(v)-vector space of dimension r with basis e_{1}, …, e_{r}. We make M := V^{⊗r} into a right H-module in the usual way (i.e. via the tensor space action defined in 1.5). Let h ∈ H. Then:

(i) if m := e_{1} ⊗ ⋯ ⊗ e_{r}, then m.h = 0 ⇒ h = 0; (ii) if m_{π} := e_{(1)π} ⊗ ⋯ ⊗ e_{(r)π}, where π ∈ S_{r}, then m_{π}.h = 0 ⇒ h = 0. Proof We first prove (i). Let m and m_{π} be defined as in the statement of the Lemma. By using induction on ℓ(π), we find that m.T_{π} = v^{ℓ(π)}m_{π}. If π ≠ π′ then m_{π} ≠ m_{π′}; in fact, the set {m_{π} : π ∈ S_{r}} is linearly independent in V^{⊗r}. However, {T_{w} : w ∈ S_{r}} is known to be a basis for H. Since v is invertible, we now find that if m.h = 0, then h = 0.

We now prove (ii). We know from the above argument that m.T_{π} = v^{ℓ(π)}m_{π}. Assuming that m_{π}.h = 0, then m.(v^{−ℓ(π)}T_{π}h) = 0. Now (i) shows that v^{−ℓ(π)}T_{π}h = 0, and, since v and T_{π} are both invertible, that h = 0. This completes the proof.

We now need to introduce a family of bases for H, of which the usual basis {T_{w}} is an example. The motivation behind doing this is that by picking the correct basis, it is possible to deduce certain results concerning the coefficients of basis elements in the τ_{i,j} which were introduced earlier. This will be important later.

For convenience, we now choose, once and for all, a “favourite” reduced expression ρ(w) for each element w ∈ W. Definition Let j ∈ I(n, r) be of parabolic form, let W_{J} be its associated parabolic subgroup, and let D_{J} be the associated set of distinguished right coset representatives. To each element w ∈ D_{J}, we will associate an element D_{w}^{j} ∈ H which specialises as q is replaced by 1 to w in the group algebra.

Suppose ρ(w) = s_{i_{1}} ⋯ s_{i_{m}}. Earlier, we showed how S_{r} acts on I(n, r) on the right. For each integer t such that 1 ≤ t ≤ m we define an element h_{t} of H as follows. Consider j′ := j.s_{i_{1}} ⋯ s_{i_{t−1}}. Because w is a distinguished right coset representative, it must be the case that j′_{i_{t}} ≠ j′_{i_{t+1}}. (This follows from the length identities in 1.4, the definition of distinguished right coset representatives, and the fact that any left subword of a distinguished right coset representative is another distinguished right coset representative.) Writing T_{i_{t}} instead of T_{s_{i_{t}}} (for typographical convenience), we find that if j′_{i_{t}} > j′_{i_{t+1}} then h_{t} := T_{i_{t}}^{−1}, otherwise h_{t} := T_{i_{t}}. We then define D_{w}^{j} to be h_{1}h_{2} ⋯ h_{m}.

Remark

If 1 ≤ a < b ≤ n, then e_{b} ⊗ e_{a}.T_{s}^{−1} = v^{−1}e_{a} ⊗ e_{b} and e_{a} ⊗ e_{b}.T_{s} = ve_{b} ⊗ e_{a}. Define, for any i ∈ I(n, r),

m(i) := |{⟨a, b⟩ : 1 ≤ a < b ≤ r, i_{a} > i_{b}}|.

(For example, if i = ((1)π, …, (r)π) as in the statement of Lemma 2.2 (ii), then m(i) = ℓ(π).)

If s = (p, p + 1) and j_{p} ≤ j_{p+1} then u_{i,j}.T_{s} is a linear combination of elements u_{i′,j.s} (see §1.6, (1) and (3)). If j_{p} ≥ j_{p+1} then u_{i,j}.T_{s}^{−1} is a linear combination of elements u_{i′,j.s} (see §1.6, (5) and (7)).

The crucial property of the element D_{w}^{j} is as follows:

v^{m(j)}e_{j_{1}} ⊗ ⋯ ⊗ e_{j_{r}}.D_{w}^{j} = v^{m(j.w)}e_{(j_{1})w} ⊗ ⋯ ⊗ e_{(j_{r})w}.

This can be seen by induction on left subwords of w.

It is also follows that basis elements occurring with nonzero coefficients in u_{i,j}.D_{w}^{j} are of form u_{i′,j.w}.

Example

Let j = (4, 4, 1, 2). Then the parabolic subgroup W_{J} is generated by s_{1} = (1, 2). A routine check shows that the element w ∈ S_{4} given by

( \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 4 & 3 & 1 \end{matrix} )

lies in D_{J}. The element j.w ∈ I is equal to (2, 4, 1, 4). A reduced expression ρ(w) for w is given by s_{3}s_{2}s_{1}s_{3}. The element D_{w}^{j} ∈ H is now given by T_{3}T_{2}^{−1}T_{1}^{−1}T_{3}^{−1}. (It will be seen later that the element D_{w}^{j} is independent of the reduced expression chosen for w.)

We now compare the elements D_{w}^{j} with their counterparts T_{w}. To do this, it is convenient to define an element R(j) ∈ I(r, r) (N.B.—not necessarily in I(n, r)) which is in some sense a “refinement” of j. We will then act various D_{w}^{j} on this R(j), and appeal to Lemma 2.2 to relate them to the usual basis consisting of the T_{w}. Definition Let i ∈ I(n, r) be of parabolic form. Then the element R(i) is the unique element of I(r, r) satisfying the following properties:

(i) R(i) = ((1)π, …, (r)π) for some π ∈ S_{r}; (ii) if 1 ≤ a < b ≤ r and i_{a} < i_{b} (respectively i_{a} > i_{b}) then R(i)_{a} < R(i)_{b} (respectively

R(i)_{a} > R(i)_{b}); (iii) if 1 ≤ a < b ≤ r and i_{a} = i_{b} then R(i)_{a} < R(i)_{b}. Example Let n = 4, r = 8 and i = (1, 1, 1, 4, 4, 4, 3, 3). Then R(i) = (1, 2, 3, 6, 7, 8, 4, 5). Remarks Note that m(R(i)) = m(i) for any i ∈ I(n, r) of parabolic form. Also note that

v^{m(R(i))}e_{R(i)_{1}} ⊗ ⋯ ⊗ e_{R(i)_{r}}.D_{w}^{i} = v^{m(R(i).w)}e_{R(i)_{(1)w}} ⊗ ⋯ ⊗ e_{R(i)_{(r)w}}.

Together with Lemma 2.2, this shows that the element D_{w}^{j} is in fact independent of the reduced expression we were using for w.

We can say more than this: if W_{I} is the parabolic subgroup associated with i, and u ∈ W_{I}, then

v^{m(R(i))}e_{R(i)_{1}} ⊗ ⋯ ⊗ e_{R(i)_{r}}.T_{u}D_{w}^{i} = v^{m(R(i).uw)}e_{R(i)_{(1)uw}} ⊗ ⋯ ⊗ e_{R(i)_{(r)uw}}.

This follows from the definitions of R(i) and D_{w}^{i}: all the actions are essentially permutations, but with powers of v introduced to keep track of the changing value of the m function (which can be thought of as “length”).

Lemma 2.3 Let j ∈ I(n, r) be of parabolic form, with associated parabolic subgroup W_{J}. Then: (i)

( ∑_{u∈W_{J}} T_{u}) ( ∑_{w∈D_{J}} D_{w}^{j}) = q^{−m(j)} ∑_{w∈W} T_{w}.

(ii) The set

{T_{u}D_{w}^{j} : u ∈ W_{J}, w ∈ D_{J}}

is a basis for H. Proof Let π ∈ S_{r} be such that R(j) = ((1)π, …, (r)π). Then

e_{1} ⊗ ⋯ ⊗ e_{r}.T_{π} = v^{m(R(j))}e_{R(j)_{1}} ⊗ ⋯ ⊗ e_{R(j)_{r}}.

It now follows that

v^{m(R(j))}e_{R(j)_{1}} ⊗ ⋯ ⊗ e_{R(j)_{r}}.T_{π}^{−1}. ( ∑_{w∈W} T_{w}) = ∑_{w∈W} v^{ℓ(w)}e_{(1)w} ⊗ ⋯ ⊗ e_{(r)w}.

It also follows from the preceding remarks that

v^{m(R(j))}e_{R(j)_{1}} ⊗ ⋯ ⊗ e_{R(j)_{r}}. ( ∑_{u∈W_{J}} T_{u}) ( ∑_{w∈D_{J}} D_{w}^{j}) = ∑_{w∈W} v^{ℓ(w)}e_{(1)w} ⊗ ⋯ ⊗ e_{(r)w}.

Applying Lemma 2.2 (ii), this shows that

( ∑_{u∈W_{J}} T_{u}) ( ∑_{w∈D_{J}} D_{w}^{j}) = T_{π}^{−1}. ( ∑_{w∈W} T_{w}) ,

where the right-hand side is known to be equal to

q^{−ℓ(π)} ∑_{w∈W} T_{w},

thus establishing (i) since ℓ(π) = m(R(j)) = m(j).

Part (ii) follows easily from the definitions and the Bruhat order relation, because D_{w}^{j} is a linear combination of T_{w} and T_{y} with y < w.

Definition Let z ∈ I(n, r). Define z^{+} to be the element of I(n, r) satisfying z_{i}^{+} = f(z_{i}) for all i and for f ∈ S_{n} of minimal length subject to the condition that wt(z^{+}) ∈ Λ^{+}(n, r). (Such an f is uniquely defined, as will be illustrated in the following example.) Example Let n = 5, r = 9 and z = (1, 1, 2, 2, 2, 2, 4, 4, 4), so that wt(z) = (2, 4, 0, 3, 0). Then the permutation

( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 4 & 2 & 5 \end{matrix} )

works in the above definition of f, and

z^{+} = (3, 3, 1, 1, 1, 1, 2, 2, 2),

with

wt(z^{+}) = (4, 3, 2, 0, 0).

Note that wt(z) is a permutation of wt(z^{+}), and that wt(z) ∈ Λ^{+}. This will always be the case, and in fact wt(z^{+}) = f.wt(z). There is exactly one such f of minimal length, showing why f and z^{+} are well-defined.

Lemma 2.4 Let z ∈ I(n, r) be such that i < j ⇒ z_{i} ≤ z_{j}. In particular, z is of parabolic form; let the associated parabolic subgroup be W_{Z}. Then:

(i) τ_{z,z^{+}}τ_{z^{+},z} = v^{∗}τ_{z,z}; (ii) There exists u ∈ S_{v}(n, r) satisfying u.ξ_{z^{+},z} = v^{∗}ξ_{z}. Proof It is immediate that if z is of parabolic form, then so is z^{+}, and the stabiliser of z^{+} is precisely W_{Z}. We then know from the remarks following the definition of the τ_{i,j} that τ_{z^{+},z} = v^{∗}ξ_{z^{+},z}, for some integer ∗, and that τ_{z,z} = v^{∗}ξ_{z,z} for some integer ∗. Furthermore, we know that τ_{z,z^{+}} corresponds to some element in S_{v}(n, r). This establishes the proof of (ii) assuming (i), so it remains to prove (i).

To prove (i), it is enough, by the results of Proposition 1.2, to prove that the only relaxed basis element occurring in τ_{z,z^{+}}τ_{z^{+},z} is that corresponding to τ_{z,z}, and that it occurs with a coefficient which is a power of v.

The only relaxed basis element occurring with nonzero coefficient in τ_{z^{+},z} which can contribute to a relaxed basis element in the product is u_{z^{+},z}. This follows from Proposition 1.3 and the fact that τ_{z^{+},z} = v^{∗}.ξ_{z^{+},z}. Proposition 1.3 (iii) tells us that the coefficient of u_{z^{+},z} is a power of v.

The problem now reduces further—it is now enough to show that if u_{a,z^{+}} occurs in τ_{z,z^{+}} with nonzero coefficient then a = z and the coefficient is a power of v.

Using Lemma 2.3 (i), the definition of τ, and the action of T_{y} (where y ∈ W_{Z}) on u_{z,z^{+}}, we find that

τ_{z,z^{+}} = v^{∗}.u_{z,z^{+}}. ( ∑_{w∈D_{Z}} D_{w}^{z^{+}}) .

From our study of the properties of D_{w}^{z^{+}}, we see that any basis element occurring with nonzero coefficient in u_{z,z^{+}}D_{w}^{z^{+}}, where w is as in the above sum, is of form u_{b,z^{+}.w}. The implication of this is that the only basis elements of the desired form come from the case w = 1 in the sum. This is enough to complete the proof of the Lemma.

Remark on Lemma 2.4 In the classical case, this result is obvious (see [9]).

Proposition 2.5 Any codeterminant is a Z[q, q^{−1}]-linear combination of codeterminants of dominant shape. Proof We know that u.ξ_{z^{+},z} = ξ_{z} for some u ∈ S_{v}(n, r), because v is a unit. Since

S_{v}(n, r) ≅ S_{q}(n, r) ⊕ v.S_{q}(n, r)

as a Z[q, q^{−1}] module, we can take u to be in S_{q}(n, r), by omitting irrelevant terms.

Since u.ξ_{z^{+},z} = u.ξ_{z^{+}}.ξ_{z^{+},z}, we see that u.ξ_{z^{+}} is a Z[q, q^{−1}]-linear combination of basis elements of the form ξ_{a,z^{+}}. It now follows that ξ_{z} is a Z[q, q^{−1}]-linear combination of codeterminants of shape z^{+}, i.e. of dominant shape.

Now consider an arbitrary codeterminant, Y_{i,j}^{wt(z)}, where z can be taken to be as in the statement of Lemma 2.4 (and so in particular, z = ℓ(wt(z))). This is equal to ξ_{i,z}ξ_{z}ξ_{z,j}. Using the first part of the proof, we can now rewrite this as

∑_{a} μ_{a} (ξ_{i,z}ξ_{a,z^{+}}) (ξ_{z^{+},z}ξ_{z,j}) ,

where the coefficients μ_{a} lie in Z[q, q^{−1}]. Expanding the parentheses using the product algorithm, we can finally rewrite the sum as a Z[q, q^{−1}]-linear combination of codeterminants of dominant shape, as required.

3. The Quantized Straightening Formula The next main result will be the proof of the quantum analogue of Woodcock’s straight-

ening formula for codeterminants. The aim is to express an arbitrary codeterminant as a linear combination of standard codeterminants. Proposition 2.5 shows that it is enough to be able to express an arbitrary codeterminant of dominant shape as a linear combination of standard codeterminants.

Let λ ∈ Λ^{+}(n, r), ℓ = ℓ(λ) and i ∈ I′_{λ}\I_{λ}. Note that ℓ is of parabolic form; denote the associated parabolic subgroup by W_{L}. We shall construct another element j ∈ I(n, r) by analysis of the tableau T = T_{i}^{λ}, in exactly the same way as Woodcock [9]. (The symbols i, j and λ will remain fixed throughout the next few lemmas.)

Denote by [λ] the Young diagram of λ, considered as a subset of N^{2}. By the choice of i, T cannot be standard, and so we know there is some (b, c) ∈ [λ] satisfying T (b, c) ≥ T (b+1, c). Let (b, c) be lexicographically minimal with respect to this property. Denote by [λ]_{a} the a-th row of [λ], and define X_{a} and Y_{a} so that [λ]_{a} = X_{a} ˙∪ Y_{a} (a ∈ n), where

X_{a} = [λ]_{a}, Y_{a} = ∅, if a < b;
X_{b} = {⟨b, h⟩ : 1 ≤ h < c}  Y_{b} = [λ]_{b}\X_{b};
X_{a} = {x ∈ [λ]_{a} : T (x) ≤ T (y) for all y ∈ Y_{a−1}}, Y_{a} = [λ]_{a}\X_{a}, if a > b.

Put ν_{a} = |X_{a} ˙∪ Y_{a−1}| for a ∈ n + 1, and define X_{n+1} = Y_{0} = ∅. Let a_{1}, …, a_{m} be the elements of {a ∈ n + 1 : ν_{a} ≠ 0}, ordered so that α < β ⇒ ν_{a_{α}} ≥ ν_{a_{β}}.

Note that m ≤ n: this is clear if X_{b} = ∅. If X_{b} ≠ ∅, each entry of T in X_{b+1} is at least b + 1 by the minimality of (b, c). By induction, each of the elements of Y_{a} is at least a + 1, so Y_{n} = ∅.

We are now ready to define j ∈ I by the property

T_{j}^{λ}(x) = α if x ∈ X_{a_{α}} ˙∪ Y_{a_{α}−1}.

Let μ = wt(j). By the choice of ordering on the a_{α}, we have μ ∈ Λ^{+}, and in fact μ ≻ λ since ν_{α} = λ_{α} if α < b, while ν_{b+1} > λ_{b}.

We also define j′ ∈ I by the property that

T_{j′}^{λ}(x) = α if x ∈ X_{α} ˙∪ Y_{α−1}.

Note that we may choose the ordering on a_{1}, …, a_{m} above in such a way that j^{′+} = j.

Example Suppose n = 6, r = 18 and

T_{i}^{λ} = 1 2 3 5 1 2 3 6 1 3 3 1 3 5 2 3 2 2 .

Then

T_{j}^{λ} = 1 3 2 4 1 3 2 5 1 2 2 1 2 4 1 2 1 1

and

T_{j′}^{λ} = 1 2 3 4 1 2 3 5 1 3 3 1 3 4 1 3 1 1 .

The element j is given by

(\underbrace{1, 1, 1, 1, 1, 1, 1}_{X_{1}}, \underbrace{3, 3}_{X_{2}}, \underbrace{2, 2, 2}_{Y_{2}}, \underbrace{2, 2, 2}_{X_{3}}, \underbrace{4}_{Y_{3}}, \underbrace{4}_{X_{4}}, \underbrace{5}_{Y_{4}}),

where the sections of j corresponding to each nonempty X_{a} and Y_{a} have been marked. Similarly, the element j′ is given by

(\underbrace{1, 1, 1, 1, 1, 1, 1}_{X_{1}}, \underbrace{2, 2}_{X_{2}}, \underbrace{3, 3, 3}_{Y_{2}}, \underbrace{3, 3, 3}_{X_{3}}, \underbrace{4}_{Y_{3}}, \underbrace{4}_{X_{4}}, \underbrace{5}_{Y_{4}}).

The weights λ and μ are given by

λ = (7, 5, 4, 2, 0, 0)

and

μ = (7, 6, 2, 2, 1, 0).

The following lemma is very useful for reducing questions about q-codeterminants to questions about their classical analogues. Lemma 3.1 Suppose a, b, d, e ∈ I(n, r). Assume that a_{1} ≤ ⋯ ≤ a_{r} and b_{1} ≤ ⋯ ≤ b_{r} (which implies that ⟨a, b⟩ and ⟨b, a⟩ are H-relaxed).

(i) Write

ξ_{a,b}ξ_{d,e} = ∑_{a′∼a} c_{a′,e}ξ_{a′,e}.

Then the elements c_{a′,e} lie in N[q]. (ii) Write

ξ_{e,d}ξ_{b,a} = ∑_{e′∼e} c′_{e′,a}ξ_{e′,a}.

Then the elements c′_{e′,a} lie in N[q]. Proof It is clear from the definition of the multiplication in the q-Schur algebra given in [1, Proposition 1.2] that a product of two basis elements is a Z[q]-combination of other basis elements. To prove both parts of the lemma, it therefore suffices to show that the coefficients occurring lie in N[v, v^{−1}].

We know from [3, Theorem 1.11] that there is an anti-automorphism of the q-Schur algebra which sends an element ξ_{i,j} to ξ_{j,i}. (Details are given in §3.5.) This implies that it is enough to prove (i), because (ii) is an immediate consequence of it.

We now concentrate on (i). We may assume that ⟨d, e⟩ is an H-relaxed pair. Define A to be the matrix satisfying e_{A} = ξ_{d,e} and define s_{A} and m_{A} as in §1.10. The parabolic subgroup of W which is the stabiliser of e is denoted by W_{e}, and we write D_{d,e} for the set of distinguished right coset representatives corresponding to the parabolic subgroup which is the stabiliser of the pair ⟨d, e⟩.

Any relaxed basis element u_{i,j} occurring in the product Π_{0} := ξ_{a,b}ξ_{d,e} must have j = e and i ∼ a. Now Proposition 1.2 implies that the coefficient of u_{i,j} in Π_{0} is the same as the coefficient in the product ξ_{a,b}x_{d,e}, where x_{d,e} ∈ T^{r}(M_{n}) is given by

x_{d,e} := v^{s_{A}−m_{A}}u_{d,e}. ( ∑_{w∈W_{e}∩D_{d,e}} T_{w}) .

Because we assumed that ⟨d, e⟩ was H-relaxed, we find by induction on left subwords of w and iteration of equation (1) in §1.6 that if T_{w} is one of the elements in the sum, then

u_{d,e}.T_{w} = v^{∗}u_{dw,ew},

for some integer denoted by ∗. It follows that x_{d,e} is an N[v, v^{−1}] combination of basis elements of tensor matrix space.

Now consider e_{B} = ξ_{a,b} as an element of tensor matrix space. We find from Proposition 1.2 that

ξ_{a,b} = v^{s_{B}−m_{B}}u_{a,b}. ( ∑_{w∈D_{a,b}} T_{w}) .

We find that for each w in the sum,

u_{a,b}.T_{w} = v^{∗}u_{aw,bw}.

This is proved using the hypotheses on the pair ⟨a, b⟩, induction on left subwords of w, and iteration of equation (1) in §1.6. An argument similar to the one in the preceding paragraph shows that ξ_{a,b} is an N[v, v^{−1}]-combination of basis vectors of tensor matrix space.

It is now immediate from Proposition 1.2 (iii) that the elements c_{a′,e} lie in N[v, v^{−1}], which completes the proof.

Definitions Let Π_{0} be the element of S_{q}(n, r) given by

ξ_{i,j′}ξ_{j′,l},

and let Π_{1} be the element of S(n, r) given by the same expression.

Let Π_{2} be the element of S(n, r) given by

ξ_{i,j}ξ_{j,l}.

Lemma 3.2 Express Π_{0} in terms of the basis elements of the q-Schur algebra {ξ_{a,b}} (where the pairs ⟨a, b⟩ are H-relaxed) by writing

Π_{0} = ∑_{i′∈I′_{λ}} c_{i′,l}ξ_{i′,l},

where c_{i′,l} ∈ Z[q]. Then c_{i,l} is a power of q and i′ ⪰ i whenever c_{i′,l} is nonzero. Proof Note that the product Π_{0} = ξ_{i,j′}ξ_{j′,l} satisfies the hypotheses of Lemma 3.1 (ii). Write c′_{i′,l} for the integer which is the specialisation as q is replaced by 1 of c_{i′,l}. It is now enough in the light of Lemma 3.1 to prove that the coefficient c′_{i,l} in Π_{1} is 1 and that i′ ⪰ i whenever c′_{i′,l} ≠ 0, because c′_{i,l} is equal to 1 if and only if c_{i,l} is a (nonnegative) power of q, and c′_{i′,l} is nonzero if and only if c_{i′,l} is nonzero. (This is true because the coefficients in the statement of Lemma 3.1 all lie in N[q].)

It is immediate from Schur’s product rule and the construction of j and j′ that Π_{1} and Π_{2} are equal. The element Π_{2} was studied in [9], where it was proved that the coefficient of ξ_{i,l} in Π_{2} was equal to 1 and that any basis element ξ_{i′,l} appearing in Π_{2} satisfied i′ ⪰ i.

The proof now follows.

Lemma 3.3 The element Π_{0} can be written as an A-linear sum of q-codeterminants of shape μ. Proof We see from Lemma 2.4 (i) that

τ_{j′,j}τ_{j,j′} = v^{∗}τ_{j′,j′}

for some integer denoted by ∗. It follows that we can write

Π_{0} = ξ_{i,j′}ξ_{j′,l} = ξ_{i,j′}ξ_{j′,j′}ξ_{j′,l} = v^{∗} (ξ_{i,j′}τ_{j′,j}) (τ_{j,j′}ξ_{j′,l}) .

Now we expand each pair of parentheses in terms of the basis ξ_{a,b} to obtain an A-linear sum of q-codeterminants of shape μ = wt(j).

Lemma 3.4 Let λ ∈ Λ^{+}(n, r), ℓ = ℓ(λ), and i ∈ I′_{λ}\I_{λ}. Then there exist elements c_{i′,ℓ} ∈ A and j ∈ I(n, r) such that μ = wt(j) ∈ Λ^{+}, μ ≻ λ, and

ξ_{i,ℓ} = q^{∗}Π_{0} + ∑_{{i′∈I{′ \atop λ} \atop i′≻i}} c_{i′,ℓ}ξ_{i′,ℓ}.

Thus

ξ_{i,ℓ} = ∑_{{a∼i \atop b∼ℓ}} c′_{a,b}Y_{a,b}^{μ} + ∑_{{i′∈I{′ \atop λ} \atop i′≻i}} c_{i′,ℓ}ξ_{i′,ℓ},

where the scalars c and c′ lie in A. Proof The elements j and μ are constructed from i and λ as previously, where it was also shown that μ ∈ Λ^{+} and μ ≻ λ. The first assertion follows from rearranging the expression for Π_{0} given by Lemma 3.2, and using the fact that the coefficient of ξ_{i,ℓ} is a power of q (i.e. a unit). The second assertion follows from the first by re-expressing Π_{0} as an A-linear sum of codeterminants of shape μ, as explained in Lemma 3.3.

We require the following well-known property of q-Schur algebras in the proof of the main result. Proposition 3.5 There is an anti-isomorphism ∗ : S_{q}(n, r) → S_{q}(n, r) given by either

\begin{aligned}(ϕ_{λ,μ}^{d})^{∗} & = ϕ_{μ,λ}^{d^{−1}}, \\ (e_{A})^{∗} & = e_{A^{⊤}}, \\ or (ξ_{a,b})^{∗} & = ξ_{b,a}. \end{aligned}

Thus (Y_{a,b}^{ν})^{∗} = Y_{b,a}^{ν}.

Proof For the proof of this with respect to the ϕ, see [3, Theorem 1.11]. The other two equivalent definitions follow from the equivalence of the three bases.

The last assertion is immediate from the definition of codeterminants.

Definition Following [9], we define

B := {(λ, i, j) : λ ∈ Λ^{+}, i, j ∈ I′_{λ}},

and we partially order B by (λ, i, j) ⪯ (μ, i′, j′) if and only if λ ≺ μ or (λ = μ, i ⪯ i′ and j ⪯ j′).

We can now state and prove the main theorem. Theorem 3.6 (the Straightening Formula for Quantized Codeterminants)

Let Y_{i,j}^{λ} be any codeterminant. Then Y_{i,j}^{λ} is a Z[q, q^{−1}]-linear combination of standard codeterminants. Proof By Proposition 2.5, it is enough to prove the theorem in the case where λ ∈ Λ^{+}. Since

S_{v}(n, r) ≅ S_{q}(n, r) ⊕ v.S_{q}(n, r)

as a Z[q, q^{−1}] module, and all codeterminants Y_{a,b}^{μ} lie in S_{q}(n, r), we see that it is enough to prove the result that Y_{i,j}^{λ} is an A-linear combination of standard codeterminants.

Suppose Y_{i,j}^{λ} is not standard. It is enough to show that we can write it as an A-linear combination of codeterminants corresponding to elements of B which are strictly higher in the partial order on B, and then use induction on the poset (B, ⪯).

Assume first that i ∉ I_{λ}. Construct the elements j ∈ I(n, r) and μ ∈ Λ^{+} as in Lemma 3.4, and set ℓ = ℓ(λ).

By definition, Y_{i,j}^{λ} = ξ_{i,ℓ} × ξ_{ℓ,j}. We now substitute for ξ_{i,ℓ} using the formula in Lemma 3.4 to obtain

Y_{i,j}^{λ} = (∑_{{a∼i \atop b∼ℓ}} c′_{a,b}Y_{a,b}^{μ} × ξ_{ℓ,j}) + ( ∑_{{i′∈I{′ \atop λ} \atop i′≻i}} c_{i′,ℓ}ξ_{i′,ℓ}ξ_{ℓ,j}) ,

where the scalars c and c′ all lie in A. Next, we can rewrite the expression in the left-hand set of parentheses using the fact that

Y_{a,b}^{μ}ξ_{ℓ,j} = ξ_{a,ℓ(μ)}(ξ_{ℓ(μ),b}ξ_{ℓ,j}),

and then expanding the product ξ_{ℓ(μ),b}ξ_{ℓ,j} as a sum of basis elements ξ_{ℓ(μ),d}. Finally we can write the product Y_{a,b}^{μ}ξ_{ℓ,j} as an A-linear sum of codeterminants Y_{a,d}^{μ}. This gives

Y_{i,j}^{λ} = (∑_{{a∼i \atop d∼j}} c′′_{a,d}Y_{a,d}^{μ}) + ( ∑_{{i′∈I{′ \atop λ} \atop i′≻i}} c_{i′,ℓ}Y_{i′,j}^{ℓ}) ,

where the scalars c′′ and c all lie in A.

Note that we have now succeeded in expressing Y_{i,j}^{λ} as the sum of codeterminants corresponding to strictly higher elements of B, as required.

The other case, where i ∈ I_{λ} but j ∉ I_{λ} follows by symmetry by using Proposition 3.5 followed by the preceding argument, then Proposition 3.5 again. This completes the proof.

Corollary 3.7 The set of standard codeterminants forms a free Z[q, q^{−1}]-basis of S_{q}(n, r). Proof The cardinality of this set is \binom{n^{2}+r−1}{r}, because it is the same as the cardinality of the corresponding set in the classical case. (See [5, §2] for a proof of the latter.) This is the same as the dimension of S_{q}(n, r). It is also known (see Dipper and James [3, Theorem 1.4]) that the elements e_{A} form a free basis for S_{q}(n, r). It is therefore enough to show that each e_{A} is a Z[q, q^{−1}]-linear combination of standard codeterminants. Theorem 3.6 shows that it is enough to prove that each basis element ξ_{i,j} is a codeterminant. This is clear, because ξ_{i,j} = ξ_{i,j}ξ_{j}.

We end this paper by giving a brief summary of the steps needed to straighten an arbitrary codeterminant, Y_{i′,k′}^{λ′}.

(1) Find the element z ∈ I(n, r) satisfying a < b ⇒ z_{a} ≤ z_{b} and wt(z) = λ′. Use the identity τ_{z,z^{+}}τ_{z^{+},z} = v^{∗}τ_{z,z} of Lemma 2.4 (i) and the techniques of Proposition 2.5 to express the codeterminant as a sum of codeterminants of dominant shape.

(2) Straighten each non-standard codeterminant Y_{i,k}^{λ} arising from the previous procedure. If i ∈ I_{λ} but k ∉ I_{λ}, straighten the codeterminant Y_{k,i}^{λ} instead and use Proposition 3.5 to “turn the results around” at the end.

(3) We may now concentrate on straightening codeterminants of form Y_{i,k}^{λ}, where λ is a dominant weight and i ∉ I_{λ}. Construct the elements j and j′ from i and λ, as described at the beginning of §3. Using the formula for ξ_{i,ℓ} given in Lemma 3.4, and the techniques of the proof of Theorem 3.6, rewrite Y_{i,k}^{λ} as a sum of codeterminants corresponding to strictly higher elements of the poset B.

(4) Iterate parts (2) and (3) until all codeterminants appearing in the sum are standard.

ACKNOWLEDGEMENTS

The work for this paper was done while the author was supported by a grant from the SERC, and was supervised by Professor R.W. Carter at the University of Warwick.

The author thanks the referee for some useful suggestions.

REFERENCES

[1] A.A. Beilinson, G. Lusztig and R. MacPherson, A geometric setting for the quantum deformation of GL_{n}, Duke. Math. J. 61 (1990), 655–677.

[2] R. Dipper and G.D. James, Representations of Hecke algebras and general linear groups, Proc. L.M.S. 52 (1986), 20–52.

[3] R. Dipper and G.D. James, q-tensor space and q-Weyl modules, Trans. A.M.S. 327 (1991), 251–282.

[4] J. Du, A Note on Quantized Weyl Reciprocity at Roots of Unity, Algebra Colloq. 4 (1995), 363–372.

[5] J.A. Green, Polynomial Representations of GL_{n}, Lecture Notes in Mathematics, 830, Springer, Berlin.

[6] J.A. Green, Combinatorics and the Schur algebra, J. Pure Appl. Alg. 88 (1993) 89–106.

[7] R.M. Green, A new setting for the q-Schur algebra, Warwick Preprint 61/1994.

[8] J.E. Humphreys, Reflection Groups and Coxeter Groups, Cambridge University Press, 1990.

[9] D.J. Woodcock, Straightening codeterminants, J. Pure Appl. Alg. 88 (1993) 317–320.