# Q-rook placements and Jordan forms of upper-triangular nilpotent matrices.

1 Introduction

In the beautiful paper Variations on the Triangular Theme, Kirillov (1995) studied various structures on the set of triangular matrices. Denote by [G.sub.n]([F.sub.q]), the group of n by n upper-triangular matrices over the field [F.sub.q] having q elements, and let [g.sub.n]([F.sub.q]) = Lie([G.sub.n]([F.sub.q])) denote the corresponding Lie algebra of n by n upper-triangular nilpotent matrices over [F.sub.q]. It is known, for example, that the conjugacy classes of [G.sub.n]([F.sub.q]) are in bijection with the adjoint orbits in [g.sub.n]([F.sub.q]). To study the adjoint orbits we consider the Jordan canonical form. Each matrix X [member of] [g.sub.n]([F.sub.q]) is similar to a block diagonal matrix consisting of elementary Jordan blocks with eigenvalue zero:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If the Jordan canonical form of X has block sizes [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n] [greater than or equal to] 0, then X is said to have Jordan type [lambda], where [lambda] is a partition of n. The Jordan type of X depends only on its adjoint orbit, so the similarity classes of nilpotent matrices are indexed by the partitions of n.

Let [g.sub.n,[lambda]] ([F.sub.q]) [subset or equal to] [g.sub.n]([F.sub.q]) be the set of matrices of fixed Jordan type [lambda]. It was shown by Springer that [g.sub.n,[lambda]]([F.sub.q]) an algebraic manifold with [f.sup.[lambda]] irreducible components, each of which has the same dimension [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Here, [f.sup.[lambda]] is the number of standard Young tableaux of shape [lambda], and [n.sub.[lambda]] is given in Equation 9. Let

[F.sub.[lambda]](q) = [absolute value of [g.sub.n,[lambda]]([F.sub.q])] (1)

be the number of matrices of Jordan type [lambda]. We note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The cases [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are readily computed, since the matrix ofJordan type ([1.sup.n]) is the matrix of rank zero, and the matrices of Jordan type (n) are the matrices of rank n - 1.

In Section 2, we present a simple recurrence equation for [F.sub.[lambda]](q) (see Proposition 2). As a consequence of the recurrence equation, it follows that [F.sub.[lambda]](q) is a polynomial in q with nonnegative integer coefficients, deg [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and the coefficient of the highest degree term in [F.sub.[lambda]](q) is [f.sup.[lambda]].

A connection with q-Rook placements

In their study of a formula of Frobenius, Garsia and Remmel (1986) introduced the q-rook polynomial

[R.sub.k](q,B) = [summation over (c[member of]C(B,k)] [q.sup.inv](c), (2)

which is a sum over the set C(B, k) of non-attacking placements of k rooks on the Ferrers board B, and inv(c), defined in Equation 11, is the number of inversions of c. In the case when B = [[delta].sub.n] is the staircase-shaped board, Garsia and Remmel showed that [R.sub.k](q, [[delta].sub.n]) = [S.sub.n,n-k](q) is a q-Stirling number of the second kind. These numbers are defined by the recurrence

[S.sub.n,k](q)= [q.sup.k-1][S.sub.n-1,k-1](q) + [[k].sub.q][S.sub.n-1,k](q) for 0 [less than or equal to] k [less than or equal to] n, (3)

with initial conditions [S.sub.0,0](q) = 1, and [S.sub.n,k](q) = 0 for k < 0 or k > n.

It was shown by Solomon (1990) that non-attacking placements of k rooks on rectangular m x n boards are naturally associated to m by n matrices with rank k over Fq. By identifying a Ferrers board B inside an n by n grid with the entries of an n by n matrix, Haglund (1998) generalized Solomon's result to the case of non-attacking placements of k rooks on Ferrers boards, and obtained a formula for the number of n by n matrices with rank k whose support is contained in the Ferrers board region. As a special case of Haglund's formula, the number of nilpotent matrices of rank k is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Now, a matrix in [g.sub.n,[lambda]]([F.sub.q]) has rank n - l([lambda]), where l([lambda]) is the number of parts of [lambda], so the number of matrices in [g.sub.n]([F.sub.q]) with rank k is

[P.sub.k](q) = [summation over ([lambda][??]n: l([lambda])=n-k)] [F.sub.[lambda]](q). (5)

Given Equations 4 and 5, it is natural to ask whether it is possible to partition the placements C([[delta].sub.n], k) into disjoint subsets so that the sum over each subset of placements gives [F.sub.[lambda]](q). The goal of this paper is to study the connection between upper-triangular nilpotent matrices over [F.sub.q] and non-attacking q-rook placements on the staircase-shaped board [[delta].sub.n].

Section 3 forms the heart of this paper. Inspired by Equation 7 for [F.sub.[lambda]](q), we define a graph Z closely related to Young's lattice. The main result is Theorem 9, which states that there is a weight-preserving bijection between rook placements and paths in Z. As a result, we obtain a formula for [F.sub.[lambda]](q) as a sum over certain weighted q-rook placements (see Corollary 10), which can be viewed as a generalization of Haglund's formula in Equation 4.

There is a well-known bijection between rook placements on the staircase-shaped board [[delta].sub.n] with k rooks, and set partitions of {1, ..., n} with n - k blocks. In Section 4, we describe how paths in Z gives a new bijection between these sets, and how this gives a definition of a lattice of compositions which appears to be new. Finally, in Section 5, we mention some further problems to pursue. In this article, the proofs are either omitted or briefly sketched. Full details can be found in the preprint Yip (2013).

2 The recurrence equation for [F.sub.[lambda]](q)

We define a partition [lambda] of a nonnegative integer n, denoted by [lambda] [??] n, is a non-increasing sequence of nonnegative integers [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [A.sub.n] [greater than or equal to] 0 with [absolute value of [lambda]] = [[summation].sup.n.sub.i=1] [[lambda].sub.i] = n. If [lambda] has k positive parts, write l([lambda]) = k. Represent a partition [lambda] by its Ferrers diagram in the English notation, which is an array of [[lambda].sub.i] boxes in row i, with the boxes justified upwards and to the left. Let [[lambda]'.sub.j] denote the size of the jth column of [lambda].

Example 1 The partition

[lambda] = (4, 2, 2,1) [??] 9 has diagram [ILLUSTRATION OMITTED]

and columns [[lambda]'.sub.1] = 4, [[lambda]'.sub.2] = 3, [[lambda]'.sub.3] = 1, [[lambda]'.sub.4] = 1.

Young's lattice Y is the lattice of partitions ordered by the inclusion of their Ferrers diagrams. In particular, write [mu] [??] [lambda] if [mu] [subset or equal to] [lambda] and [absolute value of [lambda]] = [absolute value of [mu]] + 1. In other words, [mu] is covered by [lambda] in Y if the Ferrers diagram of [lambda] can be obtained by adding a box to the Ferrers diagram of [mu]. If this box is added in the ith row and jth column of the diagram, assign a weight [c.sub.[mu][lambda]](q) to the edge between [mu] and [lambda], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

See Figure 1 for an illustration.

The following recurrence formula for FA(q) can be found in Borodin (1995), where he considers the matrices as particles of a certain mass. An elementary proof of a different flavour is outlined below.

Proposition 2 Let [lambda] [??] n. The number of n by n upper-triangular nilpotent matrices over [F.sub.q] of Jordan type [lambda] is

[F.sub.[lambda]](q) = [summation over ([mu][??][lambda])] [c.sub.[mu][lambda]](q)[F.sub.[mu]](q), with [F.sub.0](q) = 1.

Proof: Proceed by induction on n. Given [lambda] [??] n, first notice that any matrix in [g.sub.n,[lambda]]([F.sub.q]) has a leading principal submatrix of type [mu] where [mu] [??] [lambda]. Furthermore, let [J.sub.[mu]] denote the Jordan matrix which is the direct sum of elementary nilpotent Jordan blocks of sizes [[mu].sub.1], ..., [[mu].sub.k]. There are [c.sub.[mu][lambda]](q) matrices of Jordan type [lambda] having [J.sub.[mu]] as its leading principal submatrix, and by similarity, this result continues to hold if the matrix [J.sub.[mu]] is replaced by any matrix Y of Jordan type [mu]. Summing over all [mu] [??] [lambda] gives the desired formula.

[FIGURE 1 OMITTED]

The formula for [F.sub.[lambda]](q) in Proposition 2 can be rephrased as a sum over the set P([lambda]) of paths in the Young lattice Y from the empty partition 0 to [lambda]. Suppose

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a path in Y, where the weight of the path

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

is the product of the weights on it edges. Then Proposition 2 is equivalent to the statement

[F.sub.[lambda]](q) = [summation over ([??][member of]P([lambda])] w([??]). (8)

Example 3 There are tWo partitions of4 With 2 parts, namely (3, 1) and (2, 2). There are three paths from 0 to (3, 1), giving

[F.sub.(3,1)](q) = (q - 1) x (q - 1)q x [q.sup.2] + (q - 1) x q x (q - 1)[q.sup.2] + x ([q.sup.2] - 1) x (q - 1)[q.sup.2] = [(q - 1).sup.2] (3[q.sup.3] + [q.sup.2]),

and there are tWo paths from 0 to (2, 2), giving

[F.sub.(2,2)](q) = (q - 1) x q x (q - 1)q + ([q.sup.2] - 1) x (q - 1)q = [(q - 1).sup.2] (2[q.sup.2] + q).

Two observations about [F.sub.[lambda]](q) now follow readily from Proposition 2. For [lambda] [??] n, let

[n.sub.[lambda]] = [summation over (i [greater than or equal to] 1)] (i - 1) [[lambda].sub.i]. (9)

Suppose [??] : 0 [right arrow] [[lambda].sup.(1)] [right arrow] [[lambda].sup.(2)] [right arrow] ... [[lambda].sup.(n)] = [lambda] is a path in Y such that [[lambda].sup.(r)] is obtained

by adding a box to [[lambda].sup.(r-1)] in row i and column j. Then deg [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In particular, each polynomial w([??]) arising from a path [??] [member of] P([lambda]) has the same degree, so

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Moreover, each w([??]) is monic, so the coefficient of the highest degree term in [F.sub.[lambda]](q) is the number of paths in Y from 0 to [lambda], which is the number [f.sup.[lambda]] of standard Young tableaux of shape [lambda].

Second, the edge weight [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] corresponding to the rth step in the path [??] contributes a factor of q - 1 to w([??]) if and only if the rth box added along the path is in column j [greater than or equal to] 2. Therefore, the multiplicity of q - 1 in each w([pi]) is n - [[lambda]'.sub.1] = n - l([lambda]), and so, the multiplicity of q - 1 in [F.sub.[lambda]](q) is n - l([lambda]).

3 Jordan canonical forms and q-rook polynomials

A board B is a subset of an n by n grid of squares. We follow Haglund (1998), and index the squares following the convention for the entries of a matrix. A Ferrers board is a board B where if a square s [member of] B, then all squares lying north and/or east of s is also in B. Let [[delta].sub.n] denote the staircase-shaped board with n columns of sizes 0, 1, ..., n - 1. Let area(B) be the number of squares in B, so area [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in particular.

A placement of k rooks on a board B is non-attacking if there is at most one rook in each row and each column of B. Let C(B, k) be the set of non-attacking placements of k rooks on B. For a placement [gamma] [member of] C(B, k), let ne([gamma]) be the number of squares in B lying directly north or directly east of a rook. Also define the inversion of the placement to be the number

inv([gamma]) = area(B) - k - ne([gamma])- (11)

See Example 4 for an illustration. As noted in Garsia and Remmel (1986), the statistic inv([gamma]) is a generalization of the number of inversions of a permutation, since permutations can be identified with non-attacking placements of rooks on a square-shaped board. In terms of the rook placement, inv([gamma]) is the number of squares left blank.

Define the weight of a rook placement [gamma] [member of] C(B, k) by

w([gamma]) = [(q - 1).sup.k] [q.sup.ne([gamma])]. (12)

Example 4 We use x to mark a rook and use * to mark squares lying directly north or directly east of a rook. (These squares shall be referred to as the north-east squares of the placement.) The following illustration is a non-attacking placement of four rooks on the staircase-shaped board [[delta].sub.7].

[ILLUSTRATION OMITTED]

This rook placement has ne([gamma]) = 11, inv([gamma]) = 6, and weight w([gamma]) = [(q - 1).sup.4][q.sup.11].

For k [greater than or equal to] 0, the q-rook polynomial of a Ferrers board B is defined in (Garsia and Remmel, 1986, I.4) by

[R.sub.k](q, B) = [summation over (c[member of]C)(B,k)] [q.sup.inv(c)]. (13)

The following result is due to (Haglund, 1998, Theorem 1).

Proposition 5 If B is a Ferrers board, then the number [P.sub.B,k](q) of n by n matrices of rank k with support contained in B is

[P.sub.B,k](q) = [(q - 1).sup.k] [q.sup.area(B)-k][R.sub.k]([q.sup.-1], B).

Looking ahead, it will be convenient to consider Theorem 5 in the following equivalent form:

[P.sub.B,k](q) = [summation][(q - 1).sup.k][q.sup.ne([gamma])] = [summation over [gamma][member of]C(B,k)] w([gamma]). (14)

Example 6 There are seven non-attacking placements on (4 with two rooks:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

This gives [P.sub.2](q) = [(q - 1).sup.2](3[q.sup.3] + 3[q.sup.2] + q).

Recall that if [lambda] - n is obtained from [mu] by adding a box in row i and column j, then the edge in Y from [mu] to [lambda] has weight

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

Thus each edge weight is a sum of terms of the form [(q - 1).sup.d][q.sup.e] where d = 1 - [[delta].sub.j1]([[delta].sub.j1] denotes the Kronecker delta function), and e [member of] [Z.sub.[greater than or equal to]0]. This observation inspires the following definitions.

Based on the Young lattice Y, we construct a graph Z (see Figure 2). The vertices of Z are partitions. If there is an edge from [alpha] to [lambda] in Y of weight [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then in Z the edge is replaced by [[mu]'.sub.j-1] - [[mu]'.sub.j] edges with weights

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A primitive path [pi]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a path in the graph Z. The weight w([pi]) of a primitive path is the product of its edge weights.

Let PP ([lambda]) denote the set of primitive paths from 0 to A. Then each path in Young's lattice corresponds to a set of primitive paths, and

[F.sub.[lambda]](q) = [summation over ([pi][member of]PP([lambda]))] w([pi]) (18)

Remark 7 Let [mu] [??] [n.sup.-1] where l([mu]) = l. Let [pi]': 0 [right arrow] [[lambda].sup.(1)] [right arrow] [[lambda].sup.(2)] [right arrow] ... [right arrow] [[lambda].sup.(n-1)] = [mu] be a primitive path. If [lambda] is obtained by adding a box to the first column of [mu], then there is a unique way to extend the primitive path n' by one edge, and by Equation 17, that edge has weight

Furthermore, consider all possible [lambda] which can be obtained by adding a box to [mu] in a column j [greater than or equal to] 2. Then by Equation 17, there are

[l([mu]')+1.summation over (j=2)] [[mu]'.sub.j-1] - [[mu]'.sub.j] = l

ways to extend the primitive path n' by one edge.

In summary, the out-degree of [mu] in Z is l + 1. Moreover, the weights

[q.sup.[absolute value of [mu]]-l], (q - 1) [q.sup.[absolute value of [mu]]-l] (q - 1)[q.sup.[absolute value of [mu]]-l+1] ... (q - 1) [q.sup.[absolute value of [mu]]-1],

for the edges have unique degrees [absolute value of [mu]] - l [less than or equal to] d [less than or equal to] [absolute value of [mu]]. This observation is crucial for the proof of the next lemma.

Lemma 8 Let n [greater than or equal to] 1 and 0 [less than or equal to] k [less than or equal to] n - 1. Suppose [gamma] [member of] C([[delta].sub.n], k) is a rook placement with columns [[gamma].sup.(1)], ..., [[gamma].sup.(n)]. Then the sequence of weights w([[gamma].sup.(1)], ..., w([[gamma].sup.(n)]) deterrmines a unique primitive pat [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [[epsilon].sub.r] = w([[gamma].sup.(r)])-Moreover, l([[pi].sup.(n)]) = n - k.

[FIGURE 2 OMITTED]

Proof: Proceed by induction on n + k. Suppose [gamma] [member of] C([[delta].sub.n], k) and let y' be the placement consisting of the first n - 1 columns of [gamma]. By induction, the sequence [[epsilon].sub.1] = w([[gamma].sup.(1)]), ..., [[epsilon].sub.n-1] = w([[gamma].sup.(n-1)]) determines a unique primitive path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. There are two cases to consider; y' has either k or k - 1 rooks.

If [gamma]' has k rooks, then the column [[gamma].sup.(n)] then has k north-east squares only and weight [q.sup.k] = [q.sup.[absolute value of [mu]]-l]. By the previous remark, there is a unique way to extend the primitive path corresponding to [gamma]' by adding a box to the first column of [[pi].sup.(n-1)], and that edge has weight [q.sup.[absolute value of [mu]]-l].

In the second case, if [gamma]' has k - 1 rooks, then there are n - 1 - k available boxes in column [[gamma].sup.(n)] to place a rook. The placement of the rook uniquely determines the degree of the weight w([[gamma].sup.(n)]) of the column, which ranges from k + 1, ..., n - 1. From the remark, there are precisely l = n - 1 - k edges emanating from [mu] in Z with weights having degrees [absolute value of [mu]] - l + 1, ..., [absolute value of [mu]].

Let PP(n, n - k) = {n [member of] PP([lambda]) | [lambda] [??] n and l([lambda]) = n - k} be the set of primitive paths in Z from 0 to a partition with n - k parts. Define a map [THETA]: C([[delta].sub.n], k) [right arrow] PP(n, n k) as follows. Suppose a rook placement [gamma] has columns [[gamma].sup.(1)], ..., [[gamma].sup.(n)]. Let [THETA]([gamma]) be the primitive path

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 9 The map: C([[delta].sub.n], k) [right arrow] PP(n, n - k) is a weight- preserving bijection.

It follows from Theorem 9 that we may associate a partition type to each rook placement on [[delta].sub.n]. The partition type of a rook placement [gamma] is the partition at the endpoint of the primitive path [THETA]([gamma]). Let C([lambda]) be the set of rook placements of partition type [lambda]. As a Corollary, we obtain a formula for [F.sub.[lambda]](q) as a sum over rook placements, and the equation can be viewed as a generalization of Haglund's result in Equation 4.

Corollary 10 Let [lambda] [??] n be a partition with l([lambda]) = n - k parts. Then

[F.sub.[lambda]](q) = [summation over ([gamma][member of]C([lambda]))] [(q - 1).sup.k][q.sup.ne([gamma])].

Proof: The result follows from Equation 18 and the bijection [THETA] in Theorem 9.

Example 11 There are four primitive paths from 0 to [lambda] = (3, 1).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Respectively, they correspond to the following rook placements, each having partition type (3,1).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore,

[F.sub.(3,1)](q) = [(q - 1).sup.2](3[q.sup.3] + [q.sup.2]).

4 A refinement to compositions

A set partition is a set [sigma] = {[B.sub.1], ..., [B.sub.k]} of nonempty disjoint subsets of [N.sub.n] such that [[union].sup.k.sub.i=1][B.sub.i] = [N.sub.n]. The [B.sub.i]s are the blocks of [sigma]. Let [PI](n, k) be the set of set partitions of [N.sub.n] with k blocks. We adopt the convention of listing the blocks in order so that min [B.sub.i] < min [B.sub.j] if i < j. This allows us to represent a set partition with a diagram similar to that of a Young tableau; the ith row of the diagram consists of the elements in block [B.sub.i] listed in increasing order. A composition [sigma] of a nonnegative integer n is a sequence of positive integers ([[alpha].sub.1], ..., [[alpha].sub.k]) such that [absolute value of [alpha]] = [[summation].sup.k.sub.i=1][[alpha].sub.i] = n. If [alpha] has k positive parts, write l([alpha]) = k. A set partition [sigma] = {[B.sub.1], ..., [B.sub.k]} has composition type [alpha] if [alpha] = ([absolute value of [B.sub.1]], ..., [absolute value of [B.sub.k]]).

The number of set partitions of [N.sub.n] with k blocks is the Stirling number [S.sub.n,n-k](1) (see Equation 3). In addition, [S.sub.n,n-k](1) is also the number of placements of k rooks on the staircase board [[delta].sub.n]. This follows from the following well-known bijection (see Stanley (1999)); given a placement [gamma] [member of] C([[delta].sub.n], k), construct a set partition of [N.sub.n] where the integers i and j are in the same block if and only if there is a rook in square (i, j) [member of] [gamma].

We shall give another bijection [PSI]: C([[delta].sup.n], k) [right arrow] n(n, n - k) that arises from the primitive paths in the graph Z. Let [gamma] [member of] C([[delta].sub.n], k) be a rook placement. Construct a diagram for a set partition using the following procedure (also see Example 14).

* Let [[lambda].sup.(1)] be the diagram with a single box labelled 1 placed in the first row and the first column.

* For k [greater than or equal to] 2, if the weight of the kth column in [gamma] has degree d, then place the box labelled k in the (k - d)th row of [[lambda].sup.(k-1)], and rearrange the rows of the diagram into a partition shape [[lambda].sup.(k)], so that the rows of the same length have first column entries in increasing order.

Note that if [pi] = [THETA]([gamma]) is the primitive path in Z which corresponds to the placement [gamma], then [[pi].sup.(k)] = [[lambda].sup.(k)]. Let [[lambda].sup.(n)] be the partition shape of the diagram after the nth box has been placed. Let order ([[lambda].sup.(n)]) be the diagram of the set partition resulting from ordering the rows of [[lambda].sup.(n)] so that the first column entries are increasing. Define [PSI]([gamma]) = order ([[lambda].sup.(n)]).

Proposition 12 [PSI]: C([[delta].sub.n], k) [right arrow] [PI](n, n - k) is a bijection.

The composition type of a rook placement [gamma] [member of] C([[delta].sub.n], k) is the composition type of [PSI](y). Let C([alpha]) be the set of rook placements with composition type [alpha]. For a composition a of n with l([alpha]) = n - k parts, define

[F.sub.[alpha]](q) = [summation over (c[member of]C([alpha])) [(q - 1).sup.k][q.sup.ne(c)]. (19)

Let rearr([alpha]) be the partition resulting from the rearrangement of the parts of the composition [alpha] so that they are nondecreasing.

Corollary 13 Let [lambda] [??] n. Then

[F.sub.[lambda]](q) = [summation over ([lambda]=rearr([alpha]))] [F.sub.[alpha]](q).

We extend the definition of [n.sub.[lambda]] to compositions and let [n.sub.[alpha]] = [[summation].sub.i[greater than or equal to]1] (i - 1)[[alpha].sub.i]. Then deg [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the multiplicity of the factor q - 1 in [F.sub.[alpha]](q) is n = l([alpha]), and the coefficient of the highest degree term is the number of set partitions whose diagrams are increasing along rows and columns.

Example 14 Consider the rook placement [gamma] [member of] C([[delta].sub.8], 5):

[ILLUSTRATION OMITTED]

q-Rook placements and Jordan forms of upper-triangular nilpotent matrices

The set partition diagrams [[lambda].sup.(1)], ..., [[lambda].sup.(n)] correspond to the following primitive path in Z.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The edge weights of this primitive path are the same as the column weights in the rook placement. Ordering the rows of the diagram of the endpoint of the primitive path so that the entries in the first column are increasing gives the set partition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, the rook placement [gamma] has partition type [lambda] = (3, 3, 2) and composition type [alpha] = (3, 2,3).

Remark 15 We can define a lattice X of compositions by requiring that each path from 0 to a encodes a rook configuration of composition type [alpha]. The paper of Bjorner and Stanley (2005) considers two different lattices of compositions, but X is different from the two presented in their paper. It may be interesting to investigate the combinatorial properties of X, particularly as paths in X are equivalent to set partitions, and they are known to play a crucial role in the supercharacter theory of unipotent upper-triangular matrices (see Thiem (2010) for example).

5 Closing remarks

5.1 Inverse Kostka-polynomials

Let [P.sub.[lambda]](x; t) denote the Hall-Littlewood function indexed by the partition [lambda], and let [m.sub.[mu]](x) denote the monomial symmetric function indexed by [mu]. See (Macdonald, 1995, Ch. III) for definitions. For [lambda], [mu] [??] n, the transition coefficients [L.sub.[lambda],[mu]](t) are defined by

[P.sub.[lambda]](x; t) = [summation over ([mu])] [L.sub.[lambda],[mu]](t)[m.sub.[mu]] (x). (20)

The recurrence formula for [F.sub.[lambda]](q) in Proposition 2 is essentially the same as the one for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (Macdonald, 1995, Equation 5.9'), so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It would be interesting to see if other entries in the transition matrix can be obtained as sums over rook placements on boards of another shape.

5.2 Matrices satisfying [X.sup.2] = 0

Kirillov and Melnikov (1995) considered the number [A.sub.n](q) of n by n upper- triangular matrices over [F.sub.q] satisfying [X.sup.2] = 0. In their first characterization of these polynomials, they considered the number [A.sup.r.sub.n](q) of matrices of a given rank r, so that [A.sub.n](q) = [[summation].sub.r[greater than or equal to]0] [A.sup.r.sub.n](q), and observed that [A.sup.r.sub.n](q) satisfies the recurrence

[A.sup.r.sub.n](q) = [q.sup.r][A.sup.r.sub.n-1](q) + ([q.sup.n-r] - [q.sup.r]) [A.sup.r.sub.n](q), [A.sup.0.sub.n](q) = 1.

We may think of [A.sub.n](q) as the sum of [F.sub.[lambda]](q) over [lambda] [??] n with at most two columns, so Proposition 2 is, in a sense, a generalization of this recurrence.

It was also conjectured by Kirillov and Melnikov that the same sequence of polynomials arise in a number of different ways. Ekhad and Zeilberger (1996) proved that one of the conjectured alternate definitions of [A.sub.n](q), namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

is a sum over all s [member of] [-n - 1, n + 1] which satisfy s [equivalent to] n + 1 mod 2 and s [equivalent to] [(-1).sup.n] mod 3, and [c.sub.n+1,s] are entries in the signed Catalan triangle, is indeed the same as [A.sub.n](q). It would be interesting to see what other combinatorics may arise from considering the sum of [F.sub.[lambda]](q) over [lambda] [??] n with at most k columns for a fixed k.

Acknowledgements

I would like to thank Jim Haglund and Alexandre Kirillov for their invaluable guidance.

References

A. Bjorner and R. P. Stanley. An analogue of young's lattice for compositions. 2005.

A. M. Borodin. Limit jordan normal form of large triangular matrices over a finite field. Funct. Anal. Appl., 29(4):279-281, 1995.

S. Ekhad and D. Zeilberger. The number of solutions of [x.sup.2] =0 in triangular matrices over gf (q). Elec. J. Comb., 3, 1996.

A. Garsia and J. B. Remmel. q-counting rook configurations and a formula of frobenius. J. Combin. Theory Ser. A, 41 246-275, 1986.

J. Haglund. q-rook polynomials and matrices over finite fields. Adv. in Appl. Math., 20:450-487, 1998.

A. A. Kirillov. Variations on the triangular theme. Amer. Math. Soc. Transl., 169(2):43-73, 1995.

A. A. Kirillov and A. Melnikov. On a remarkable sequence of polynomials. Semin. Congr. 2, Soc. Math. France, pages 35-42, 1995.

I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford University Press, 1995.

L. Solomon. The bruhat decomposition, tits system and iwahori ring for the monoid of matrices over a finite field. Geom. Dedicata., 36:15-49, 1990.

R. P. Stanley. Enumerative Combinatorics. Cambridge University Press, 1999.

N. Thiem. Branching rules in the ring of superclass functions of unipotent upper-triangular matrices. J. Algebraic. Combin., 2:267-298, 2010.

M. Yip. q-rook placements and jordan forms of upper-triangular nilpotent matrices. 2013.

Martha Yip

University of Pennsylvania, 209 South 33rd St., Philadelphia PA 19104, USA

In the beautiful paper Variations on the Triangular Theme, Kirillov (1995) studied various structures on the set of triangular matrices. Denote by [G.sub.n]([F.sub.q]), the group of n by n upper-triangular matrices over the field [F.sub.q] having q elements, and let [g.sub.n]([F.sub.q]) = Lie([G.sub.n]([F.sub.q])) denote the corresponding Lie algebra of n by n upper-triangular nilpotent matrices over [F.sub.q]. It is known, for example, that the conjugacy classes of [G.sub.n]([F.sub.q]) are in bijection with the adjoint orbits in [g.sub.n]([F.sub.q]). To study the adjoint orbits we consider the Jordan canonical form. Each matrix X [member of] [g.sub.n]([F.sub.q]) is similar to a block diagonal matrix consisting of elementary Jordan blocks with eigenvalue zero:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If the Jordan canonical form of X has block sizes [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [[lambda].sub.n] [greater than or equal to] 0, then X is said to have Jordan type [lambda], where [lambda] is a partition of n. The Jordan type of X depends only on its adjoint orbit, so the similarity classes of nilpotent matrices are indexed by the partitions of n.

Let [g.sub.n,[lambda]] ([F.sub.q]) [subset or equal to] [g.sub.n]([F.sub.q]) be the set of matrices of fixed Jordan type [lambda]. It was shown by Springer that [g.sub.n,[lambda]]([F.sub.q]) an algebraic manifold with [f.sup.[lambda]] irreducible components, each of which has the same dimension [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Here, [f.sup.[lambda]] is the number of standard Young tableaux of shape [lambda], and [n.sub.[lambda]] is given in Equation 9. Let

[F.sub.[lambda]](q) = [absolute value of [g.sub.n,[lambda]]([F.sub.q])] (1)

be the number of matrices of Jordan type [lambda]. We note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The cases [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are readily computed, since the matrix ofJordan type ([1.sup.n]) is the matrix of rank zero, and the matrices of Jordan type (n) are the matrices of rank n - 1.

In Section 2, we present a simple recurrence equation for [F.sub.[lambda]](q) (see Proposition 2). As a consequence of the recurrence equation, it follows that [F.sub.[lambda]](q) is a polynomial in q with nonnegative integer coefficients, deg [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and the coefficient of the highest degree term in [F.sub.[lambda]](q) is [f.sup.[lambda]].

A connection with q-Rook placements

In their study of a formula of Frobenius, Garsia and Remmel (1986) introduced the q-rook polynomial

[R.sub.k](q,B) = [summation over (c[member of]C(B,k)] [q.sup.inv](c), (2)

which is a sum over the set C(B, k) of non-attacking placements of k rooks on the Ferrers board B, and inv(c), defined in Equation 11, is the number of inversions of c. In the case when B = [[delta].sub.n] is the staircase-shaped board, Garsia and Remmel showed that [R.sub.k](q, [[delta].sub.n]) = [S.sub.n,n-k](q) is a q-Stirling number of the second kind. These numbers are defined by the recurrence

[S.sub.n,k](q)= [q.sup.k-1][S.sub.n-1,k-1](q) + [[k].sub.q][S.sub.n-1,k](q) for 0 [less than or equal to] k [less than or equal to] n, (3)

with initial conditions [S.sub.0,0](q) = 1, and [S.sub.n,k](q) = 0 for k < 0 or k > n.

It was shown by Solomon (1990) that non-attacking placements of k rooks on rectangular m x n boards are naturally associated to m by n matrices with rank k over Fq. By identifying a Ferrers board B inside an n by n grid with the entries of an n by n matrix, Haglund (1998) generalized Solomon's result to the case of non-attacking placements of k rooks on Ferrers boards, and obtained a formula for the number of n by n matrices with rank k whose support is contained in the Ferrers board region. As a special case of Haglund's formula, the number of nilpotent matrices of rank k is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

Now, a matrix in [g.sub.n,[lambda]]([F.sub.q]) has rank n - l([lambda]), where l([lambda]) is the number of parts of [lambda], so the number of matrices in [g.sub.n]([F.sub.q]) with rank k is

[P.sub.k](q) = [summation over ([lambda][??]n: l([lambda])=n-k)] [F.sub.[lambda]](q). (5)

Given Equations 4 and 5, it is natural to ask whether it is possible to partition the placements C([[delta].sub.n], k) into disjoint subsets so that the sum over each subset of placements gives [F.sub.[lambda]](q). The goal of this paper is to study the connection between upper-triangular nilpotent matrices over [F.sub.q] and non-attacking q-rook placements on the staircase-shaped board [[delta].sub.n].

Section 3 forms the heart of this paper. Inspired by Equation 7 for [F.sub.[lambda]](q), we define a graph Z closely related to Young's lattice. The main result is Theorem 9, which states that there is a weight-preserving bijection between rook placements and paths in Z. As a result, we obtain a formula for [F.sub.[lambda]](q) as a sum over certain weighted q-rook placements (see Corollary 10), which can be viewed as a generalization of Haglund's formula in Equation 4.

There is a well-known bijection between rook placements on the staircase-shaped board [[delta].sub.n] with k rooks, and set partitions of {1, ..., n} with n - k blocks. In Section 4, we describe how paths in Z gives a new bijection between these sets, and how this gives a definition of a lattice of compositions which appears to be new. Finally, in Section 5, we mention some further problems to pursue. In this article, the proofs are either omitted or briefly sketched. Full details can be found in the preprint Yip (2013).

2 The recurrence equation for [F.sub.[lambda]](q)

We define a partition [lambda] of a nonnegative integer n, denoted by [lambda] [??] n, is a non-increasing sequence of nonnegative integers [[lambda].sub.1] [greater than or equal to] [[lambda].sub.2] [greater than or equal to] ... [greater than or equal to] [A.sub.n] [greater than or equal to] 0 with [absolute value of [lambda]] = [[summation].sup.n.sub.i=1] [[lambda].sub.i] = n. If [lambda] has k positive parts, write l([lambda]) = k. Represent a partition [lambda] by its Ferrers diagram in the English notation, which is an array of [[lambda].sub.i] boxes in row i, with the boxes justified upwards and to the left. Let [[lambda]'.sub.j] denote the size of the jth column of [lambda].

Example 1 The partition

[lambda] = (4, 2, 2,1) [??] 9 has diagram [ILLUSTRATION OMITTED]

and columns [[lambda]'.sub.1] = 4, [[lambda]'.sub.2] = 3, [[lambda]'.sub.3] = 1, [[lambda]'.sub.4] = 1.

Young's lattice Y is the lattice of partitions ordered by the inclusion of their Ferrers diagrams. In particular, write [mu] [??] [lambda] if [mu] [subset or equal to] [lambda] and [absolute value of [lambda]] = [absolute value of [mu]] + 1. In other words, [mu] is covered by [lambda] in Y if the Ferrers diagram of [lambda] can be obtained by adding a box to the Ferrers diagram of [mu]. If this box is added in the ith row and jth column of the diagram, assign a weight [c.sub.[mu][lambda]](q) to the edge between [mu] and [lambda], where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

See Figure 1 for an illustration.

The following recurrence formula for FA(q) can be found in Borodin (1995), where he considers the matrices as particles of a certain mass. An elementary proof of a different flavour is outlined below.

Proposition 2 Let [lambda] [??] n. The number of n by n upper-triangular nilpotent matrices over [F.sub.q] of Jordan type [lambda] is

[F.sub.[lambda]](q) = [summation over ([mu][??][lambda])] [c.sub.[mu][lambda]](q)[F.sub.[mu]](q), with [F.sub.0](q) = 1.

Proof: Proceed by induction on n. Given [lambda] [??] n, first notice that any matrix in [g.sub.n,[lambda]]([F.sub.q]) has a leading principal submatrix of type [mu] where [mu] [??] [lambda]. Furthermore, let [J.sub.[mu]] denote the Jordan matrix which is the direct sum of elementary nilpotent Jordan blocks of sizes [[mu].sub.1], ..., [[mu].sub.k]. There are [c.sub.[mu][lambda]](q) matrices of Jordan type [lambda] having [J.sub.[mu]] as its leading principal submatrix, and by similarity, this result continues to hold if the matrix [J.sub.[mu]] is replaced by any matrix Y of Jordan type [mu]. Summing over all [mu] [??] [lambda] gives the desired formula.

[FIGURE 1 OMITTED]

The formula for [F.sub.[lambda]](q) in Proposition 2 can be rephrased as a sum over the set P([lambda]) of paths in the Young lattice Y from the empty partition 0 to [lambda]. Suppose

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a path in Y, where the weight of the path

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

is the product of the weights on it edges. Then Proposition 2 is equivalent to the statement

[F.sub.[lambda]](q) = [summation over ([??][member of]P([lambda])] w([??]). (8)

Example 3 There are tWo partitions of4 With 2 parts, namely (3, 1) and (2, 2). There are three paths from 0 to (3, 1), giving

[F.sub.(3,1)](q) = (q - 1) x (q - 1)q x [q.sup.2] + (q - 1) x q x (q - 1)[q.sup.2] + x ([q.sup.2] - 1) x (q - 1)[q.sup.2] = [(q - 1).sup.2] (3[q.sup.3] + [q.sup.2]),

and there are tWo paths from 0 to (2, 2), giving

[F.sub.(2,2)](q) = (q - 1) x q x (q - 1)q + ([q.sup.2] - 1) x (q - 1)q = [(q - 1).sup.2] (2[q.sup.2] + q).

Two observations about [F.sub.[lambda]](q) now follow readily from Proposition 2. For [lambda] [??] n, let

[n.sub.[lambda]] = [summation over (i [greater than or equal to] 1)] (i - 1) [[lambda].sub.i]. (9)

Suppose [??] : 0 [right arrow] [[lambda].sup.(1)] [right arrow] [[lambda].sup.(2)] [right arrow] ... [[lambda].sup.(n)] = [lambda] is a path in Y such that [[lambda].sup.(r)] is obtained

by adding a box to [[lambda].sup.(r-1)] in row i and column j. Then deg [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In particular, each polynomial w([??]) arising from a path [??] [member of] P([lambda]) has the same degree, so

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Moreover, each w([??]) is monic, so the coefficient of the highest degree term in [F.sub.[lambda]](q) is the number of paths in Y from 0 to [lambda], which is the number [f.sup.[lambda]] of standard Young tableaux of shape [lambda].

Second, the edge weight [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] corresponding to the rth step in the path [??] contributes a factor of q - 1 to w([??]) if and only if the rth box added along the path is in column j [greater than or equal to] 2. Therefore, the multiplicity of q - 1 in each w([pi]) is n - [[lambda]'.sub.1] = n - l([lambda]), and so, the multiplicity of q - 1 in [F.sub.[lambda]](q) is n - l([lambda]).

3 Jordan canonical forms and q-rook polynomials

A board B is a subset of an n by n grid of squares. We follow Haglund (1998), and index the squares following the convention for the entries of a matrix. A Ferrers board is a board B where if a square s [member of] B, then all squares lying north and/or east of s is also in B. Let [[delta].sub.n] denote the staircase-shaped board with n columns of sizes 0, 1, ..., n - 1. Let area(B) be the number of squares in B, so area [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in particular.

A placement of k rooks on a board B is non-attacking if there is at most one rook in each row and each column of B. Let C(B, k) be the set of non-attacking placements of k rooks on B. For a placement [gamma] [member of] C(B, k), let ne([gamma]) be the number of squares in B lying directly north or directly east of a rook. Also define the inversion of the placement to be the number

inv([gamma]) = area(B) - k - ne([gamma])- (11)

See Example 4 for an illustration. As noted in Garsia and Remmel (1986), the statistic inv([gamma]) is a generalization of the number of inversions of a permutation, since permutations can be identified with non-attacking placements of rooks on a square-shaped board. In terms of the rook placement, inv([gamma]) is the number of squares left blank.

Define the weight of a rook placement [gamma] [member of] C(B, k) by

w([gamma]) = [(q - 1).sup.k] [q.sup.ne([gamma])]. (12)

Example 4 We use x to mark a rook and use * to mark squares lying directly north or directly east of a rook. (These squares shall be referred to as the north-east squares of the placement.) The following illustration is a non-attacking placement of four rooks on the staircase-shaped board [[delta].sub.7].

[ILLUSTRATION OMITTED]

This rook placement has ne([gamma]) = 11, inv([gamma]) = 6, and weight w([gamma]) = [(q - 1).sup.4][q.sup.11].

For k [greater than or equal to] 0, the q-rook polynomial of a Ferrers board B is defined in (Garsia and Remmel, 1986, I.4) by

[R.sub.k](q, B) = [summation over (c[member of]C)(B,k)] [q.sup.inv(c)]. (13)

The following result is due to (Haglund, 1998, Theorem 1).

Proposition 5 If B is a Ferrers board, then the number [P.sub.B,k](q) of n by n matrices of rank k with support contained in B is

[P.sub.B,k](q) = [(q - 1).sup.k] [q.sup.area(B)-k][R.sub.k]([q.sup.-1], B).

Looking ahead, it will be convenient to consider Theorem 5 in the following equivalent form:

[P.sub.B,k](q) = [summation][(q - 1).sup.k][q.sup.ne([gamma])] = [summation over [gamma][member of]C(B,k)] w([gamma]). (14)

Example 6 There are seven non-attacking placements on (4 with two rooks:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (15)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

This gives [P.sub.2](q) = [(q - 1).sup.2](3[q.sup.3] + 3[q.sup.2] + q).

Recall that if [lambda] - n is obtained from [mu] by adding a box in row i and column j, then the edge in Y from [mu] to [lambda] has weight

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (17)

Thus each edge weight is a sum of terms of the form [(q - 1).sup.d][q.sup.e] where d = 1 - [[delta].sub.j1]([[delta].sub.j1] denotes the Kronecker delta function), and e [member of] [Z.sub.[greater than or equal to]0]. This observation inspires the following definitions.

Based on the Young lattice Y, we construct a graph Z (see Figure 2). The vertices of Z are partitions. If there is an edge from [alpha] to [lambda] in Y of weight [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then in Z the edge is replaced by [[mu]'.sub.j-1] - [[mu]'.sub.j] edges with weights

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

A primitive path [pi]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is a path in the graph Z. The weight w([pi]) of a primitive path is the product of its edge weights.

Let PP ([lambda]) denote the set of primitive paths from 0 to A. Then each path in Young's lattice corresponds to a set of primitive paths, and

[F.sub.[lambda]](q) = [summation over ([pi][member of]PP([lambda]))] w([pi]) (18)

Remark 7 Let [mu] [??] [n.sup.-1] where l([mu]) = l. Let [pi]': 0 [right arrow] [[lambda].sup.(1)] [right arrow] [[lambda].sup.(2)] [right arrow] ... [right arrow] [[lambda].sup.(n-1)] = [mu] be a primitive path. If [lambda] is obtained by adding a box to the first column of [mu], then there is a unique way to extend the primitive path n' by one edge, and by Equation 17, that edge has weight

Furthermore, consider all possible [lambda] which can be obtained by adding a box to [mu] in a column j [greater than or equal to] 2. Then by Equation 17, there are

[l([mu]')+1.summation over (j=2)] [[mu]'.sub.j-1] - [[mu]'.sub.j] = l

ways to extend the primitive path n' by one edge.

In summary, the out-degree of [mu] in Z is l + 1. Moreover, the weights

[q.sup.[absolute value of [mu]]-l], (q - 1) [q.sup.[absolute value of [mu]]-l] (q - 1)[q.sup.[absolute value of [mu]]-l+1] ... (q - 1) [q.sup.[absolute value of [mu]]-1],

for the edges have unique degrees [absolute value of [mu]] - l [less than or equal to] d [less than or equal to] [absolute value of [mu]]. This observation is crucial for the proof of the next lemma.

Lemma 8 Let n [greater than or equal to] 1 and 0 [less than or equal to] k [less than or equal to] n - 1. Suppose [gamma] [member of] C([[delta].sub.n], k) is a rook placement with columns [[gamma].sup.(1)], ..., [[gamma].sup.(n)]. Then the sequence of weights w([[gamma].sup.(1)], ..., w([[gamma].sup.(n)]) deterrmines a unique primitive pat [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [[epsilon].sub.r] = w([[gamma].sup.(r)])-Moreover, l([[pi].sup.(n)]) = n - k.

[FIGURE 2 OMITTED]

Proof: Proceed by induction on n + k. Suppose [gamma] [member of] C([[delta].sub.n], k) and let y' be the placement consisting of the first n - 1 columns of [gamma]. By induction, the sequence [[epsilon].sub.1] = w([[gamma].sup.(1)]), ..., [[epsilon].sub.n-1] = w([[gamma].sup.(n-1)]) determines a unique primitive path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. There are two cases to consider; y' has either k or k - 1 rooks.

If [gamma]' has k rooks, then the column [[gamma].sup.(n)] then has k north-east squares only and weight [q.sup.k] = [q.sup.[absolute value of [mu]]-l]. By the previous remark, there is a unique way to extend the primitive path corresponding to [gamma]' by adding a box to the first column of [[pi].sup.(n-1)], and that edge has weight [q.sup.[absolute value of [mu]]-l].

In the second case, if [gamma]' has k - 1 rooks, then there are n - 1 - k available boxes in column [[gamma].sup.(n)] to place a rook. The placement of the rook uniquely determines the degree of the weight w([[gamma].sup.(n)]) of the column, which ranges from k + 1, ..., n - 1. From the remark, there are precisely l = n - 1 - k edges emanating from [mu] in Z with weights having degrees [absolute value of [mu]] - l + 1, ..., [absolute value of [mu]].

Let PP(n, n - k) = {n [member of] PP([lambda]) | [lambda] [??] n and l([lambda]) = n - k} be the set of primitive paths in Z from 0 to a partition with n - k parts. Define a map [THETA]: C([[delta].sub.n], k) [right arrow] PP(n, n k) as follows. Suppose a rook placement [gamma] has columns [[gamma].sup.(1)], ..., [[gamma].sup.(n)]. Let [THETA]([gamma]) be the primitive path

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Theorem 9 The map: C([[delta].sub.n], k) [right arrow] PP(n, n - k) is a weight- preserving bijection.

It follows from Theorem 9 that we may associate a partition type to each rook placement on [[delta].sub.n]. The partition type of a rook placement [gamma] is the partition at the endpoint of the primitive path [THETA]([gamma]). Let C([lambda]) be the set of rook placements of partition type [lambda]. As a Corollary, we obtain a formula for [F.sub.[lambda]](q) as a sum over rook placements, and the equation can be viewed as a generalization of Haglund's result in Equation 4.

Corollary 10 Let [lambda] [??] n be a partition with l([lambda]) = n - k parts. Then

[F.sub.[lambda]](q) = [summation over ([gamma][member of]C([lambda]))] [(q - 1).sup.k][q.sup.ne([gamma])].

Proof: The result follows from Equation 18 and the bijection [THETA] in Theorem 9.

Example 11 There are four primitive paths from 0 to [lambda] = (3, 1).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Respectively, they correspond to the following rook placements, each having partition type (3,1).

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore,

[F.sub.(3,1)](q) = [(q - 1).sup.2](3[q.sup.3] + [q.sup.2]).

4 A refinement to compositions

A set partition is a set [sigma] = {[B.sub.1], ..., [B.sub.k]} of nonempty disjoint subsets of [N.sub.n] such that [[union].sup.k.sub.i=1][B.sub.i] = [N.sub.n]. The [B.sub.i]s are the blocks of [sigma]. Let [PI](n, k) be the set of set partitions of [N.sub.n] with k blocks. We adopt the convention of listing the blocks in order so that min [B.sub.i] < min [B.sub.j] if i < j. This allows us to represent a set partition with a diagram similar to that of a Young tableau; the ith row of the diagram consists of the elements in block [B.sub.i] listed in increasing order. A composition [sigma] of a nonnegative integer n is a sequence of positive integers ([[alpha].sub.1], ..., [[alpha].sub.k]) such that [absolute value of [alpha]] = [[summation].sup.k.sub.i=1][[alpha].sub.i] = n. If [alpha] has k positive parts, write l([alpha]) = k. A set partition [sigma] = {[B.sub.1], ..., [B.sub.k]} has composition type [alpha] if [alpha] = ([absolute value of [B.sub.1]], ..., [absolute value of [B.sub.k]]).

The number of set partitions of [N.sub.n] with k blocks is the Stirling number [S.sub.n,n-k](1) (see Equation 3). In addition, [S.sub.n,n-k](1) is also the number of placements of k rooks on the staircase board [[delta].sub.n]. This follows from the following well-known bijection (see Stanley (1999)); given a placement [gamma] [member of] C([[delta].sub.n], k), construct a set partition of [N.sub.n] where the integers i and j are in the same block if and only if there is a rook in square (i, j) [member of] [gamma].

We shall give another bijection [PSI]: C([[delta].sup.n], k) [right arrow] n(n, n - k) that arises from the primitive paths in the graph Z. Let [gamma] [member of] C([[delta].sub.n], k) be a rook placement. Construct a diagram for a set partition using the following procedure (also see Example 14).

* Let [[lambda].sup.(1)] be the diagram with a single box labelled 1 placed in the first row and the first column.

* For k [greater than or equal to] 2, if the weight of the kth column in [gamma] has degree d, then place the box labelled k in the (k - d)th row of [[lambda].sup.(k-1)], and rearrange the rows of the diagram into a partition shape [[lambda].sup.(k)], so that the rows of the same length have first column entries in increasing order.

Note that if [pi] = [THETA]([gamma]) is the primitive path in Z which corresponds to the placement [gamma], then [[pi].sup.(k)] = [[lambda].sup.(k)]. Let [[lambda].sup.(n)] be the partition shape of the diagram after the nth box has been placed. Let order ([[lambda].sup.(n)]) be the diagram of the set partition resulting from ordering the rows of [[lambda].sup.(n)] so that the first column entries are increasing. Define [PSI]([gamma]) = order ([[lambda].sup.(n)]).

Proposition 12 [PSI]: C([[delta].sub.n], k) [right arrow] [PI](n, n - k) is a bijection.

The composition type of a rook placement [gamma] [member of] C([[delta].sub.n], k) is the composition type of [PSI](y). Let C([alpha]) be the set of rook placements with composition type [alpha]. For a composition a of n with l([alpha]) = n - k parts, define

[F.sub.[alpha]](q) = [summation over (c[member of]C([alpha])) [(q - 1).sup.k][q.sup.ne(c)]. (19)

Let rearr([alpha]) be the partition resulting from the rearrangement of the parts of the composition [alpha] so that they are nondecreasing.

Corollary 13 Let [lambda] [??] n. Then

[F.sub.[lambda]](q) = [summation over ([lambda]=rearr([alpha]))] [F.sub.[alpha]](q).

We extend the definition of [n.sub.[lambda]] to compositions and let [n.sub.[alpha]] = [[summation].sub.i[greater than or equal to]1] (i - 1)[[alpha].sub.i]. Then deg [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the multiplicity of the factor q - 1 in [F.sub.[alpha]](q) is n = l([alpha]), and the coefficient of the highest degree term is the number of set partitions whose diagrams are increasing along rows and columns.

Example 14 Consider the rook placement [gamma] [member of] C([[delta].sub.8], 5):

[ILLUSTRATION OMITTED]

q-Rook placements and Jordan forms of upper-triangular nilpotent matrices

The set partition diagrams [[lambda].sup.(1)], ..., [[lambda].sup.(n)] correspond to the following primitive path in Z.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The edge weights of this primitive path are the same as the column weights in the rook placement. Ordering the rows of the diagram of the endpoint of the primitive path so that the entries in the first column are increasing gives the set partition

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, the rook placement [gamma] has partition type [lambda] = (3, 3, 2) and composition type [alpha] = (3, 2,3).

Remark 15 We can define a lattice X of compositions by requiring that each path from 0 to a encodes a rook configuration of composition type [alpha]. The paper of Bjorner and Stanley (2005) considers two different lattices of compositions, but X is different from the two presented in their paper. It may be interesting to investigate the combinatorial properties of X, particularly as paths in X are equivalent to set partitions, and they are known to play a crucial role in the supercharacter theory of unipotent upper-triangular matrices (see Thiem (2010) for example).

5 Closing remarks

5.1 Inverse Kostka-polynomials

Let [P.sub.[lambda]](x; t) denote the Hall-Littlewood function indexed by the partition [lambda], and let [m.sub.[mu]](x) denote the monomial symmetric function indexed by [mu]. See (Macdonald, 1995, Ch. III) for definitions. For [lambda], [mu] [??] n, the transition coefficients [L.sub.[lambda],[mu]](t) are defined by

[P.sub.[lambda]](x; t) = [summation over ([mu])] [L.sub.[lambda],[mu]](t)[m.sub.[mu]] (x). (20)

The recurrence formula for [F.sub.[lambda]](q) in Proposition 2 is essentially the same as the one for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (Macdonald, 1995, Equation 5.9'), so that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It would be interesting to see if other entries in the transition matrix can be obtained as sums over rook placements on boards of another shape.

5.2 Matrices satisfying [X.sup.2] = 0

Kirillov and Melnikov (1995) considered the number [A.sub.n](q) of n by n upper- triangular matrices over [F.sub.q] satisfying [X.sup.2] = 0. In their first characterization of these polynomials, they considered the number [A.sup.r.sub.n](q) of matrices of a given rank r, so that [A.sub.n](q) = [[summation].sub.r[greater than or equal to]0] [A.sup.r.sub.n](q), and observed that [A.sup.r.sub.n](q) satisfies the recurrence

[A.sup.r.sub.n](q) = [q.sup.r][A.sup.r.sub.n-1](q) + ([q.sup.n-r] - [q.sup.r]) [A.sup.r.sub.n](q), [A.sup.0.sub.n](q) = 1.

We may think of [A.sub.n](q) as the sum of [F.sub.[lambda]](q) over [lambda] [??] n with at most two columns, so Proposition 2 is, in a sense, a generalization of this recurrence.

It was also conjectured by Kirillov and Melnikov that the same sequence of polynomials arise in a number of different ways. Ekhad and Zeilberger (1996) proved that one of the conjectured alternate definitions of [A.sub.n](q), namely

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

is a sum over all s [member of] [-n - 1, n + 1] which satisfy s [equivalent to] n + 1 mod 2 and s [equivalent to] [(-1).sup.n] mod 3, and [c.sub.n+1,s] are entries in the signed Catalan triangle, is indeed the same as [A.sub.n](q). It would be interesting to see what other combinatorics may arise from considering the sum of [F.sub.[lambda]](q) over [lambda] [??] n with at most k columns for a fixed k.

Acknowledgements

I would like to thank Jim Haglund and Alexandre Kirillov for their invaluable guidance.

References

A. Bjorner and R. P. Stanley. An analogue of young's lattice for compositions. 2005.

A. M. Borodin. Limit jordan normal form of large triangular matrices over a finite field. Funct. Anal. Appl., 29(4):279-281, 1995.

S. Ekhad and D. Zeilberger. The number of solutions of [x.sup.2] =0 in triangular matrices over gf (q). Elec. J. Comb., 3, 1996.

A. Garsia and J. B. Remmel. q-counting rook configurations and a formula of frobenius. J. Combin. Theory Ser. A, 41 246-275, 1986.

J. Haglund. q-rook polynomials and matrices over finite fields. Adv. in Appl. Math., 20:450-487, 1998.

A. A. Kirillov. Variations on the triangular theme. Amer. Math. Soc. Transl., 169(2):43-73, 1995.

A. A. Kirillov and A. Melnikov. On a remarkable sequence of polynomials. Semin. Congr. 2, Soc. Math. France, pages 35-42, 1995.

I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford University Press, 1995.

L. Solomon. The bruhat decomposition, tits system and iwahori ring for the monoid of matrices over a finite field. Geom. Dedicata., 36:15-49, 1990.

R. P. Stanley. Enumerative Combinatorics. Cambridge University Press, 1999.

N. Thiem. Branching rules in the ring of superclass functions of unipotent upper-triangular matrices. J. Algebraic. Combin., 2:267-298, 2010.

M. Yip. q-rook placements and jordan forms of upper-triangular nilpotent matrices. 2013.

Martha Yip

University of Pennsylvania, 209 South 33rd St., Philadelphia PA 19104, USA

Printer friendly Cite/link Email Feedback | |

Author: | Yip, Martha |
---|---|

Publication: | DMTCS Proceedings |

Article Type: | Report |

Geographic Code: | 1USA |

Date: | Jan 1, 2013 |

Words: | 5159 |

Previous Article: | A parking function setting for nabla images of Schur functions. |

Next Article: | On the poset of weighted partitions. |

Topics: |