2 Generating function for flags of invariant subspaces

We begin with a brief overview of symmetric functions, focusing on some relevant facts; the primary references are Macdonald [Reference Macdonald29] and Stanley [Reference Stanley38, Chap. 7]. A weak composition of an integer n is a sequence $\alpha =(\alpha _1,\alpha _2,\ldots )$ of nonnegative integers with sum n. A partition of n is a weak composition of n in which the sequence of integers is weakly decreasing. If $\lambda $ is a partition of n, we write $\lambda \vdash n$ . Nonzero terms in the sequence $\lambda $ are called parts of $\lambda $ and the number of parts of $\lambda $ is denoted $\ell (\lambda )$ . It is customary to ignore trailing zeroes in weak compositions and partitions. For instance, the weak compositions $(3,1,2,0,1,0,0,\ldots )$ , $(3,1,2,0,1,0)$ , and $(3,1,2,0,1)$ are all considered equivalent. For a weak composition $\alpha $ , write $|\alpha |$ for the sum $\sum _{i\geq 1}\alpha _i$ .

Let ${\mathbb Q}(t)$ denote the field of rational functions in an indeterminate t. Denote by $\Lambda _{{\mathbb Q}(t)}$ the algebra of formal symmetric functions in infinitely many variables $x=(x_1,x_2,\ldots )$ with coefficients in ${\mathbb Q}(t)$ . The algebra $\Lambda _{{\mathbb Q}(t)}$ admits several natural bases indexed by integer partitions: the monomial symmetric functions $m_\lambda $ , the elementary symmetric functions $e_\lambda $ , the power sum symmetric functions $p_\lambda $ , the complete homogeneous symmetric functions $h_\lambda $ and the Schur functions $s_\lambda $ . The ring of symmetric functions is also equipped with an involutory automorphism $\omega $ which satisfies

(2.1) $$ \begin{align} \omega e_\lambda= h_\lambda;\quad \omega h_\lambda= e_\lambda;\quad \omega s_\lambda= s_{\lambda'}. \end{align} $$

Here, and throughout this paper, $\lambda '$ denotes the partition conjugate to $\lambda $ .

The q-Whittaker functions $W_\lambda (x;t)$ and Hall–Littlewood functions $P_\lambda (x;t)$ are two more bases of $\Lambda _{{\mathbb Q}(t)}$ . Both occur as specializations of a more general class of two-parameter symmetric functions, the Macdonald polynomials $P_\lambda (x;q,t)$ . More precisely, $P_\lambda (x;t)=P_\lambda (x;0,t)$ and $W_\lambda (x;t)=P_\lambda (x;t,0)$ . The ring of symmetric functions is endowed with the Hall scalar product $\langle \cdot , \cdot \rangle $ with respect to which the bases $m_\lambda $ and $h_\lambda $ are dual. The dual basis of the Hall–Littlewood functions $P_\lambda (x;t)$ with respect to the Hall scalar product consists of the transformed Hall–Littlewood functions $H_{\lambda }(x;t)$ . They are related to the q-Whittaker functions (Bergeron [Reference Bergeron7, p. 5]) by

(2.2) $$ \begin{align} \omega H_{\lambda'}(x;t)=W_{\lambda}(x;t). \end{align} $$

One also has the dual identity $\omega P_{\lambda }(x;t)=\widetilde {W}_{\lambda '}(x;t)$ , the latter denoting the dual basis of $W_\lambda (x;t)$ with respect to the Hall scalar product. The modified Hall–Littlewood functions are indexed by integer partitions and defined by $ \tilde {H}_{\lambda }(x;t)=t^{n(\lambda )} H_{\lambda }(x;t^{-1}),$ where $n(\lambda )=\sum _{i\geq 1}(i-1)\lambda _i$ . The modified Hall–Littlewood function also satisfies

$$ \begin{align*} \tilde{H}_\lambda(x;t)=\sum_{\mu}\tilde{K}_{\mu\lambda}(t)s_\mu, \end{align*} $$

where $s_\mu $ denotes a Schur function and $\tilde {K}_{\mu \lambda }(t)$ is a modified Kostka–Foulkes polynomial, defined as the generating polynomial of the cocharge statistic on semistandard tableaux of shape $\mu $ and content $\lambda $ :

$$ \begin{align*} \tilde{K}_{\mu\lambda}(t)=\sum_{\mathcal{T} \in \mathrm{SSYT}(\mu,\lambda)}t^{\mathrm{cocharge{(\mathcal{T})}}}. \end{align*} $$

For prime power q, the specialization $\tilde {K}_{\lambda \mu }(q)$ coincides with the value taken by the character of the irreducible unipotent $\mathrm {GL}_n({\mathbb F}_q)$ -representation indexed by $\lambda $ on the unipotent conjugacy class with Jordan form partition $\mu $ (Lusztig [Reference Lusztig28, Eq. (2.2)]).

For a formal power series F, denote by $p_k[F]$ the series obtained by substituting each indeterminate appearing in F by its kth power. For an arbitrary symmetric function $g\in \Lambda _{{\mathbb Q}(t)}$ , the plethystic substitution $g[F]$ is the series obtained by writing g as a polynomial in the power sum symmetric functions $p_r$ and then substituting $p_r[F]$ for each $p_r$ appearing in g. The reader is referred to Haglund [Reference Haglund19, p. 19] or Haiman [Reference Haiman20, p. 13] for further details on plethystic notation.

For each nonnegative integer n, define the q-analogs $[n]_q:=1+q+\cdots +q^{n-1}\text { and }[n]_q!:=[1]_q[2]_q\cdots [n]_q.$ For a weak composition $\alpha $ of n, the q-multinomial coefficient is defined by

$$ \begin{align*} {n \brack \alpha}_q:=\frac{[n]_q!}{\prod_{i\geq 1}[\alpha_i]_q!}. \end{align*} $$

The above notation for q-multinomial is distinct from the notation ${n \brack \lambda }$ defined in Macdonald [Reference Macdonald29, p. 44, Ex. 1] in terms of hook-lengths and contents of the partition $\lambda $ .

Our objective, in this section, is to show that $\sigma (\mu ,\Delta )$ can be expressed in terms of suitably defined flags of invariant subspaces of $\Delta $ . We begin with a definition.

The collection of $\Delta $ -invariant subspaces of ${\mathbb F}_q^n$ forms a partially ordered set (poset) with respect to inclusion. A lattice is a poset in which each pair of elements has a unique least upper bound (or join) and a unique greatest lower bound (or meet). The above poset on $\Delta $ -invariant subspaces is a lattice with the join and meet operations given by subspace sum and intersection, respectively. Denote this lattice by $\mathcal {L}(\Delta )$ . It is well-known that the lattice $\mathcal {L}(\Delta )$ is self-dual [Reference Brickman and Fillmore9].

For subspaces $U,W\in \mathcal {L}(\Delta )$ let $[U,W]$ denote the interval consisting of all subspaces $S\in \mathcal {L}(\Delta )$ satisfying $U\subseteq S\subseteq W$ . The interval $[U,W]$ is naturally isomorphic to the lattice of invariant subspaces of the induced operator $\hat {\Delta }$ on the quotient $W/U$ defined by $\hat {\Delta }(w+U)=\Delta w+U$ . Therefore every interval in $\mathcal {L}(\Delta )$ is self-dual. The next proposition shows that $X_\alpha (\Delta )$ depends only on the integer partition obtained by sorting the coordinates of $\alpha $ in weakly decreasing order.

Proof. We may assume that the permutation taking $\alpha $ to $\alpha '$ involves only finitely many coordinates. Since each such permutation is obtained by a series of transpositions of adjacent elements, it suffices to prove the proposition when $\alpha '$ is obtained from $\alpha $ by swapping two adjacent coordinates, say $\alpha _i$ and $\alpha _{i+1}$ . Let $\mathcal {F}_\alpha (\Delta )$ denote the collection of all flags counted by $X_\alpha (\Delta )$ . We will construct an explicit bijection between $\mathcal {F}_\alpha (\Delta )$ and $\mathcal {F}_{\alpha '}(\Delta )$ . Consider a flag

$$ \begin{align*}(0)= W_0\subseteq \cdots \subseteq W_{i-1}\subseteq W_i\subseteq W_{i+1}\subseteq\cdots \subseteq W_\ell={\mathbb F}_q^n\end{align*} $$

in $\mathcal {F}_\alpha (\Delta )$ . The interval $[W_{i-1},W_{i+1}]\subseteq \mathcal {L}(\Delta )$ is self-dual and $\dim W_{i+1}/W_{i-1}=\alpha _i+\alpha _{i+1}$ . Self-duality implies the existence of a bijection $\phi :[W_{i-1},W_{i+1}]\to [W_{i-1},W_{i+1}]$ which takes each invariant subspace U with $\dim U/W_{i-1}=\alpha _i$ to a unique invariant subspace $U'$ satisfying $\dim U'/W_{i-1}=\alpha _{i+1}$ . The map

$$ \begin{align*} (W_0,\ldots, W_{i-1}, W_i, W_{i+1},\ldots, W_\ell)\mapsto (W_0,\ldots, W_{i-1}, \phi(W_i), W_{i+1},\ldots, W_\ell) \end{align*} $$

is clearly a bijection between $\mathcal {F}_\alpha (\Delta )$ and $\mathcal {F}_{\alpha '}(\Delta )$ .

To study flags of invariant subspaces it will be convenient to introduce a generating function in infinitely many variables $x=(x_1,x_2,\ldots )$ .

Definition 2.4. For $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ , the invariant flag generating function $F_{\Delta }(x)$ is defined by

(2.3) $$ \begin{align} F_{\Delta}(x):=\sum_{\alpha }X_{\alpha}(\Delta)x^{\alpha}, \end{align} $$

where the sum is taken over all inequivalent weak compositions $\alpha $ of n and $x^{\alpha }$ denotes the product $x_1^{\alpha _1}x_2^{\alpha _2}\cdots $ .

It is important to take the sum over inequivalent weak compositions of n since contributions from compositions obtained from $\alpha $ by padding zeroes would make the coefficient of $x^\alpha $ infinite. The following result is an easy consequence of Proposition 2.3 and the definition of the monomial symmetric function $m_\lambda $ .

Proposition 2.5. For each matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ ,

(2.4) $$ \begin{align} F_\Delta(x)=\sum_{\lambda}X_{\lambda}(\Delta)m_{\lambda}, \end{align} $$

where the sum is taken over all partitions $\lambda $ of n.

The following lemma follows from Kirillov [Reference Kirillov23] where it is stated for unipotent operators.

Our objective now is to determine the invariant flag generating function for an arbitrary matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ . Recall that the action of $\Delta $ on ${\mathbb F}_q^n$ defines an ${\mathbb F}_q[t]$ -module structure on ${\mathbb F}_q^n$ in which the action of t on a column vector v is given by $t\cdot v=\Delta v$ . By the structure theorem for finitely generated modules over a principal ideal domain, this module is isomorphic to a direct sum

(2.5) $$ \begin{align} \bigoplus_{i=1}^k \bigoplus_{j=1}^{\ell_i}\frac{{\mathbb F}_q[t]}{(g_i^{\lambda_{i,j}})}, \end{align} $$

where $g_i(t)\in {\mathbb F}_q[t]$ are distinct monic irreducible polynomials and the sequence $\lambda ^i=(\lambda _{i,1},\lambda _{i,2},\ldots ,\lambda _{i,\ell _i})$ is an integer partition for each $1\leq i\leq k$ . Let $d_i$ denote the degree of $g_i$ for $1\leq i\leq k$ . The submodule $\bigoplus _{j=1}^{\ell _i}{\mathbb F}_q[t]/(g_i^{\lambda _{i,j}})$ is referred to as the $g_i$ -primary component (or $g_i$ -primary part) of the module and corresponds to the maximal invariant subspace of $\Delta $ on which the restriction of $\Delta $ has characteristic polynomial a power of $g_i$ .

The notion of similarity class type can be traced back to the work of Green [Reference Green17] who studied the characters of the finite general linear groups. Considering similarity class types allows for a q-independent classification of conjugacy classes in these groups.

From a combinatorial viewpoint, one advantage of working with types is that several combinatorial invariants of a matrix often depend only on its type. We will soon see that this viewpoint is particularly convenient in the context of invariant flag generating functions. We have the following explicit formula for $F_\Delta (x)$ .

Proposition 2.11. If $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ is a matrix of similarity class type $\tau =\{(d_i,\lambda ^i)\}_{1\leq i\leq k}$ , then

(2.6) $$ \begin{align} F_{\Delta}(x)=\prod_{i=1}^k\tilde{H}_{\lambda^i}(x_1^{d_i},x_2^{d_i},\ldots;q^{d_i})=\prod_{i=1}^k p_{d_i}[\tilde{H}_{\lambda^i}(x;t)]{\Big|_{t=q}}, \end{align} $$

where $p_r$ denotes the power sum symmetric function. Here, the plethystic substitution $p_{d_i}[\tilde {H}_{\lambda ^i}(x;t)]$ is performed before evaluating at $t=q$ .

Proof. Since $\mathcal {L}(\Delta )$ is the product of the invariant subspace lattices corresponding to its primary parts (Brickman and Fillmore [Reference Brickman and Fillmore9, Thm. 1]), we briefly justify the resulting factorization of invariant flag generating functions. Write

$$\begin{align*}{\mathbb F}_q^n = V_1\oplus\cdots\oplus V_k,\qquad \Delta=\Delta_1\oplus\cdots\oplus\Delta_k, \end{align*}$$

where each $V_i$ is $\Delta $ -invariant and $\Delta _i$ denotes the restriction of $\Delta $ to $V_i$ (the primary part of type $\{(d_i,\lambda ^i)\}$ ). Then a subspace W of $ {\mathbb F}_q^n$ is $\Delta $ -invariant if and only if $W=\bigoplus _{i=1}^k (W\cap V_i)$ and each $W\cap V_i$ is $\Delta _i$ -invariant, yielding the lattice isomorphism $\mathcal {L}(\Delta )\cong \mathcal {L}(\Delta _1)\times \cdots \times \mathcal {L}(\Delta _k)$ .

Now let $0=W_0\subseteq W_1\subseteq \cdots \subseteq W_r={\mathbb F}_q^n$ be a $\Delta $ -invariant flag and set $W^{(i)}_j:=W_j\cap V_i$ . Then each $(W^{(i)}_j)_{j=0}^r$ is a $\Delta _i$ -invariant flag (allowing equalities), we have $W_j=\bigoplus _{i=1}^k W^{(i)}_j$ , and

$$\begin{align*}\dim(W_j/W_{j-1})=\sum_{i=1}^k \dim\bigl(W^{(i)}_j/W^{(i)}_{j-1}\bigr)\qquad(1\le j\le r). \end{align*}$$

Consequently the monomial weight of a $\Delta $ -invariant flag factors as the product of the weights of the corresponding $\Delta _i$ -invariant flags, and summing over all flags gives

(2.7) $$ \begin{align} F_\Delta(x)=\prod_{i=1}^k F_{\Delta_i}(x). \end{align} $$

If $g(t)\in {\mathbb F}_q[t]$ is an irreducible polynomial of degree d, then we claim that ${\mathbb F}_q[t]/(g^r)$ is isomorphic to $\mathbb {F}_{q^d}[u]/(u^r)$ . To see this, let $K:={\mathbb F}_q[t]/(g)\cong {\mathbb F}_{q^d}$ and set $R:={\mathbb F}_q[t]/(g^r)$ . Let $u\in R$ denote the image of $g(t)$ ; then $u^r=0$ and $R/(u)\cong K$ . Thus we have the isomorphism

$$\begin{align*}R \cong K[u]/(u^r)\cong {\mathbb F}_{q^d}[u]/(u^r), \end{align*}$$

where u is a new indeterminate.

Under this identification, a $\Delta _i$ -invariant flag is the same as a u-invariant flag in an ${\mathbb F}_{q^{d_i}}$ -vector space. When such a flag is regarded over ${\mathbb F}_q$ , each successive quotient has dimension multiplied by $d_i$ , so the monomial weights in $F_{\Delta _i}(x)$ acquire the substitution $x_j\mapsto x_j^{d_i}$ . Likewise, all q-enumerations over ${\mathbb F}_{q^{d_i}}$ involve $q^{d_i}$ , which explains the parameter change $q\mapsto q^{d_i}$ . In view of Equation (2.5) and Lemma 2.8, this yields

$$ \begin{align*} F_{\Delta_i}= \tilde{H}_{\lambda^i}(x_1^{d_i},x_2^{d_i},\ldots;q^{d_i})=p_{d_i}[\tilde{H}_{\lambda^i}(x;t)]{\Big|_{t=q}}, \end{align*} $$

and the result follows.

The expression for $F_\Delta (x)$ in Proposition 2.11 is a product of symmetric functions where the parameter t is specialized to a prime power q. Rather than specializing the parameter, one can work directly with the parametric versions $\tilde {H}_\lambda (x;t)$ by considering similarity class types instead of matrices. For a similarity class type $\tau =\{(d_1,\lambda ^1),(d_2,\lambda ^2),\ldots ,(d_k,\lambda ^k)\},$ define

(2.8) $$ \begin{align} F_{\tau}(x;t):=\prod_{i=1}^k p_{d_i}[\tilde{H}_{\lambda^i}(x;t)]. \end{align} $$

Given a prime power q and a matrix $\Delta \in {\mathrm M}_n(\mathbb {F}_{q})$ with similarity class type $\tau $ , it is clear that ${F_\Delta (x)=F_{\tau }(x;q)}$ . With this approach statements about matrices can be restated in terms of similarity class types. For instance, instead of the quantity $X_\lambda (\Delta )$ , one considers $X_\lambda (\tau )$ defined as the coefficient of the monomial $m_\lambda $ in $F_\tau (x;t)$ as in Equation (2.8). Although our statements will often involve matrices, it is useful to keep in mind the corresponding statements for similarity class types and we will give such examples.

Remark 2.12. For arbitrary $\tau $ and q, there may be no matrix of similarity class type $\tau $ over ${\mathbb F}_q$ . Indeed, if $\tau =\{(d_1,\lambda ^1),\dots ,(d_k,\lambda ^k)\}$ and

$$\begin{align*}m_d:=\#\{\,i: d_i=d\,\}, \end{align*}$$

then realizing $\tau $ over ${\mathbb F}_q$ requires choosing $m_d$ distinct monic irreducible polynomials of degree d in ${\mathbb F}_q[t]$ for each d that occurs in $\tau $ . When such choices exist, one constructs a matrix of type $\tau $ by taking a block diagonal matrix whose i-th block has rational canonical form with invariant factors determined by $(f_i,\lambda ^i)$ .

For a fixed $\tau $ , a matrix of type $\tau $ exists over ${\mathbb F}_q$ for all sufficiently large prime powers q, since for each fixed degree d the number of monic irreducible polynomials of degree d in ${\mathbb F}_q[t]$ tends to infinity with q (in fact it grows on the order of $q^d/d$ ), so eventually there are enough distinct choices for every d appearing in $\tau $ .

As a small-field obstruction, over ${\mathbb F}_2$ there is only one monic irreducible quadratic, namely $t^2+t+1$ . Hence no matrix over ${\mathbb F}_2$ can have a type requiring two distinct degree- $2$ primary parts, for example $\tau =\{(2,(1)),(2,(1))\}$ .

We now give examples of various symmetric functions which arise as $F_\Delta (x)$ for some $\Delta $ . In Section 4 we will see that a combinatorial interpretation can be given for the coefficients in the q-Whittaker expansions of each of these functions. The next two examples show that the power sum and homogeneous symmetric functions arise as invariant flag generating functions.

The following is a simultaneous generalization of Examples 2.7 and 2.14.

Example 2.15. A matrix is triangulable if it is similar to an upper triangular matrix. Triangulability is characterized by the minimal polynomial being a product of linear factors [Reference Hoffman, Kunze and Algebra21, Sec. 6.4] over ${\mathbb F}_q$ . For such a matrix $\Delta $ , we have $d_i=1$ in the decomposition (2.5) above for $1\leq i\leq k$ . Since $p_1[f]=f$ for any symmetric function f, it follows from Proposition 2.11 that

$$ \begin{align*} F_\Delta(x)=\prod_{i\geq 1} \tilde{H}_{\lambda^i}(x;q). \end{align*} $$

The next example will prove useful later on in the proof of Theorem 4.2.

Example 2.16. Let $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ be a diagonalizable matrix with characteristic polynomial ${\prod _{i=1}^k (x-a_i)^{\nu _i}}$ for some partition $\nu $ of n and distinct elements $a_i\in {\mathbb F}_q(1\leq i\leq k).$ Since $\Delta $ acts by a scalar multiple of the identity on each eigenspace, it follows from Example 2.2 that $F_\Delta (x)=\prod _{i\geq 1}F_{\nu _i}$ where, for each positive integer m,

(2.9) $$ \begin{align} F_m:=\sum_{\lambda \vdash m}{m \brack \lambda}_qm_{\lambda}=W_{(m)}(x;q), \end{align} $$

is a one row q-Whittaker function (see Macdonald [Reference Macdonald29, p. 323, Eq. (4.9); $t\to 0$ ] and [Reference Macdonald29, p. 314, Ex. 1; $t\to 0$ ] for the last equality above). Therefore $ F_\Delta (x)=\prod _{i\geq 1} W_{(\nu _i)}(x;q).$

Our immediate goal is to show that the number of subspaces with a given $\Delta $ -profile can be expressed in terms of $F_\Delta (x)$ . Write $\Delta ^{-1}W$ to denote the inverse image of a subspace W of ${\mathbb F}_q^n$ .

Definition 2.17. Let r be a positive integer and suppose $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ . Given partitions $\lambda =(\lambda _1,\ldots ,\lambda _r)$ and $\nu =(\nu _1,\ldots ,\nu _r)$ , denote by $\phi (\lambda ,\nu ;\Delta )$ the number of flags $W_1\supseteq W_2\supseteq \cdots \supseteq W_r$ of subspaces of ${\mathbb F}_q^n$ such that

$$ \begin{align*} \dim W_i=\lambda_i &\qquad\text{ for } 1\leq i\leq r,\\ \dim (W_i\cap \Delta^{-1}W_i)=\nu_i &\qquad\text{ for } 1\leq i\leq r,\\ W_i \cap \Delta^{-1}W_i\supseteq W_{i+1} &\qquad\text{ for }1\leq i\leq r-1. \end{align*} $$

Note that $\phi (\lambda ,\lambda ;\Delta )$ is just equal to the number of flags $W_1\supseteq W_2\supseteq \cdots \supseteq W_r$ of $\Delta $ -invariant subspaces such that $\dim W_i=\lambda _i$ for $1\leq i\leq r$ . Therefore $\phi (\lambda ,\lambda ;\Delta )$ is equal to $X_\alpha (\Delta )$ for a suitably chosen $\alpha $ .

The following lemma shows that $\sigma (\mu ,\Delta )$ can be expressed in the form $\phi (\lambda ,\nu ;\Delta )$ for suitably chosen $\lambda $ and $\nu $ [Reference Prasad and Ram33, Prop. 4.6].

Lemma 2.18. Given a partition $\mu =(\mu _1,\ldots ,\mu _k)$ , let $m_i=\mu _1+\cdots +\mu _i$ for $1\leq i\leq k$ . We have

$$ \begin{align*} \sigma(\mu,\Delta)=\phi(\pi,\delta;\Delta), \end{align*} $$

where $\pi =(m_k,m_{k-1},\ldots ,m_1)$ and $\delta =(m_k,m_{k-1}-\mu _k,m_{k-2}-\mu _{k-1},\ldots ,m_1-\mu _2)$ .

Theorem 2.19. For each partition $\mu $ and each partition $\lambda $ of n, there exist polynomials $g_{\mu \lambda }(t)\in {\mathbb Z}[t]$ , such that

$$ \begin{align*} \sigma(\mu,\Delta)=\sum_{\lambda \vdash n}g_{\mu \lambda}(q)X_\lambda(\Delta), \end{align*} $$

for every prime power q and every matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ .

Proof. Chen and Tseng [Reference Chen and Tseng11, Lemma 2.7] (see [Reference Aggarwal and Ram3, Lemma 2.7] for a more general result) proved that the quantities $\phi (\pi ,\delta ;\Delta )$ satisfy a recursion in which the base cases are of the form $\phi (\eta ,\eta ;\Delta )$ for partitions $\eta $ of n. For $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ , this recursion involves coefficients that are products of q-binomial coefficients (with possible sign) that depend only on the partitions $\pi ,\delta $ , and n. Since q-binomial coefficients are polynomials with integer coefficients, iterating the recursion a finite number of times to compute $\phi (\pi ,\delta ;\Delta )$ yields an expansion of the form

(2.10) $$ \begin{align} \phi(\pi,\delta;\Delta)=\sum_{\eta\vdash n} c_{\pi,\delta}^{\eta}(q)\,\phi(\eta,\eta;\Delta), \end{align} $$

where each coefficient $c_{\pi ,\delta }^{\eta }(q)\in {\mathbb Z}[q]$ depends only on $\pi ,\delta $ , and n (but not on $\Delta $ ). By Lemma 2.18, the quantity $\sigma (\mu ,\Delta )$ can also be expressed in the form given by the right-hand side of Equation (2.10). Since each $\phi (\eta ,\eta ;\Delta )$ is of the form $X_\lambda (\Delta )$ for some partition $\lambda $ , the result follows.

3 Diagonal operators and q-Whittaker functions

We wish to determine the polynomials $g_{\mu \lambda }(t)$ appearing in Theorem 2.19. This is accomplished by setting up a system of linear equations in Section 4. Diagonalizable operators play a central role in this analysis and we begin by discussing some relevant results.

Note that a diagonalizable matrix of type $\nu $ over ${\mathbb F}_q$ exists if and only if the number of parts of $\nu $ is at most q. The following result was proved in [Reference Ram and Schlosser35, Thm. 4.21].

Theorem 3.2. For each pair $\mu ,\nu $ of integer partitions of n, there exist polynomials $b_{\mu \nu }(t)\in {\mathbb Z}[t]$ such that

$$ \begin{align*} \sigma(\mu,\Delta)=(q-1)^{\sum_{j\geq 2}\mu_j}q^{\sum_{j\geq 2}{\mu_j \choose 2}}b_{\mu\nu}(q), \end{align*} $$

for each prime power q and each diagonal matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ of type $\nu $ .

The polynomials $b_{\mu \nu }(t)$ satisfy the following recurrence relation [Reference Ram and Schlosser35, Cor. 5.2] which was derived by considering the decomposition of the open Schubert cells in the Grassmannian according to subspace profiles with respect to a diagonal operator.

Proposition 3.3. If $\mu ,\nu $ are partitions of the same size with $\nu =(\nu _1,\ldots ,\nu _k),$ then

$$ \begin{align*} b_{\mu\nu}(t)=\sum_{\substack{\rho:\mu/\rho\ \mathrm{is\ a\ horizontal}\\ \mathrm{strip\ of\ size}\ \nu_k}}\theta_{\mu/\rho}(t)b_{\rho \tilde{\nu}}(t) , \end{align*} $$

where $\tilde {\nu }$ denotes the partition obtained by deleting the last part of $\nu $ and

(3.1) $$ \begin{align} \theta_{\mu/\rho}(t):=\frac{[|\mu|-|\rho|]_t!}{[\mu_1-\rho_1]_t!} \prod_{i\geq 1}{\rho_{i}-\rho_{i+1} \brack \mu_{i+1}-\rho_{i+1}}_t. \end{align} $$

Note that $ \theta _{\mu /\rho }(t)=0$ unless the skew diagram $\mu /\rho $ is a horizontal strip (see Macdonald [Reference Macdonald29, p. 5] for the definition).

The polynomials $b_{\mu \nu }(t)$ can also be obtained from a statistic on a suitably defined class of set partitions. The fact that these polynomials can be expressed in terms of both set partition statistics and semistandard tableaux has led to an elementary correspondence between these two classical combinatorial classes [Reference Ram and Schlosser35, Section 2]. This correspondence yields a way to associate a set partition statistic to each Mahonian statistic on multiset permutations. The polynomials $b_{\mu \nu }(t)$ also have several interesting specializations. In particular, when $\mu =(m,m)$ and $\nu =(1^{2m})$ the polynomial $b_{\mu \nu }(t)$ coincides with the Touchard-Riordan generating polynomial for chord diagrams by their number of crossings. For more on this topic and some connections with q-rook theory, the reader is referred to [Reference Ram and Schlosser35]. Here we discuss a connection between these polynomials and q-Whittaker functions.

Though they were originally studied by Macdonald [Reference Macdonald29], the name q-Whittaker was coined by Gerasimov, Lebedev, and Oblezin [Reference Gerasimov, Lebedev and Oblezin14]. As noted earlier, the q-Whittaker functions $W_\lambda (x;t)$ form a basis for $\Lambda _{{\mathbb Q}(t)}$ . They interpolate between the Schur functions and the elementary symmetric functions:

$$ \begin{align*} W_\lambda(x;0)=s_{\lambda}(x), \qquad W_\lambda(x;1)=e_{\lambda'}(x). \end{align*} $$

They also expand positively in the Schur basis,

(3.2) $$ \begin{align} W_{\mu}=\sum_{\lambda}K_{\lambda'\mu'}(t)s_\lambda, \end{align} $$

where $K_{\lambda \mu }(t)$ denotes a Kostka–Foulkes polynomial (Bergeron [Reference Bergeron7, Eq. (3.8)]). In a representation theoretic context, the q-Whittaker functions arise in the setting of the graded Frobenius characteristic of the cohomology ring of Springer fibers. We refer to the survey article of Bergeron [Reference Bergeron7] for more on q-Whittaker functions.

The polynomials $b_{\mu \nu }(t)$ are closely related to the coefficients in the monomial expansion of the q-Whittaker function $W_\lambda $ . More precisely, we have the following proposition [Reference Ram and Schlosser35, Thm. 5.3].

Proposition 3.5. For partitions $\mu $ and $\nu $ ,

$$ \begin{align*} b_{\mu\nu}(t)=\frac{\prod_{i\geq 1}[\nu_i]_t!}{\prod_{i\geq 1}[\mu_i-\mu_{i+1}]_t!}\langle W_\mu,h_\nu\rangle. \end{align*} $$

Remark 3.6. The symmetric functions $\widetilde {W}_\lambda $ defined by

(3.3) $$ \begin{align} \widetilde{W}_\lambda(x;t)=\frac{(1-t)^{-\lambda_1}}{\prod_{i\geq 1}[\lambda_i-\lambda_{i+1}]_t!}W_\lambda[X(1-t)] \end{align} $$

are dual to the q-Whittaker functions with respect to the Hall scalar product (Bergeron [Reference Bergeron7]). We have the following dual of Equation (2.2):

(3.4) $$ \begin{align} \omega P_{\lambda'}(x;t)= \widetilde{W}_\lambda(x;t). \end{align} $$

Proposition 3.7. For each partition $\nu =(\nu _1,\ldots ,\nu _k)$ ,

$$ \begin{align*} \prod_{i=1}^k W_{(\nu_i)} =\sum_{\mu}(1-t)^{|\mu|-\mu_1}b_{\mu\nu}(t)W_{\mu}. \end{align*} $$

Proof. We claim that

(3.5) $$ \begin{align} \langle f,g\rangle=\langle f[X(1-t)], g\left[\frac{X}{1-t}\right]\rangle, \end{align} $$

for symmetric functions f and g. To see this, it suffices to prove the above identity for the power sum basis, $f=p_\lambda $ and $g=p_\mu $ . The claim now follows from the equations,

$$\begin{align*}p_\lambda[X(1-t)]=\prod_{i}(1-t^{\lambda_i})p_{\lambda_i}[X],\qquad p_\mu\!\left[\frac{X}{1-t}\right]=\prod_i\frac{1}{1-t^{\mu_i}}p_{\mu_i}[X], \end{align*}$$

and the fact that $\langle p_\lambda ,p_\mu \rangle =0$ for $\lambda \neq \mu $ . By Proposition 3.5,

$$ \begin{align*} b_{\mu\nu}(t)&=\frac{\prod_{i\geq 1}[\nu_i]_t!}{\prod_{i\geq 1}[\mu_i-\mu_{i+1}]_t!}\langle W_\mu,h_\nu\rangle \\ &=\frac{\prod_{i\geq 1}[\nu_i]_t!}{\prod_{i\geq 1}[\mu_i-\mu_{i+1}]_t!} \langle W_\mu[X(1-t)],h_\nu\left[\frac{X}{1-t}\right]\rangle \\ &=(1-t)^{\mu_1}\prod_{i\geq 1}[\nu_i]_t!\, \langle \widetilde{W}_\mu,\prod_{i=1}^kh_{\nu_i}\left[\frac{X}{1-t}\right]\rangle , \end{align*} $$

where the last equality follows from Equation (3.3). For each positive integer k, we have $h_k=\omega e_k=\omega P_{(1^k)}$ by Macdonald [Reference Macdonald29, p. 209, Eq. 2.8]. Since $\omega P_{(1^k)}=\widetilde {W}_{(k)}$ by Equation (3.4),

$$ \begin{align*} b_{\mu\nu}(t)&=(1-t)^{\mu_1}\prod_{i\geq 1}[\nu_i]_t! \langle \widetilde{W}_\mu,\prod_{i=1}^k\widetilde{W}_{(\nu_i)}\left[\frac{X}{1-t}\right]\rangle \\ &=(1-t)^{\mu_1-|\mu|} \langle \widetilde{W}_\mu,\textstyle\prod_{i=1}^kW_{(\nu_i)}\rangle, \end{align*} $$

again by Equation (3.3). It follows that $(1-t)^{|\mu |-\mu _1}b_{\mu \nu }(t)$ is the coefficient of $W_\mu $ in the q-Whittaker expansion of $\prod _{i=1}^kW_{(\nu _i)}$ .

4 Full profiles

In this section we obtain an explicit formula for $\sigma (\mu ,\Delta )$ when $\mu $ is a partition of n. Arbitrary profiles are considered in Section 5.

Let $a_{\mu \lambda }(t)$ and $\tilde {a}_{ \mu \lambda }(t)$ denote the transition coefficients between the Hall–Littlewood functions and the elementary symmetric functions:

(4.1) $$ \begin{align} e_{\mu}=\sum_{\lambda}a_{\mu\lambda}(t)P_{\lambda}(x;t) \text{ and } P_{\mu}(x;t)=\sum_{\lambda}\tilde{a}_{\mu\lambda}(t)e_{\lambda}. \end{align} $$

It is known that $a_{\mu \lambda }(1)$ is equal to the number of $(0,1)$ -matrices with row sums $\mu $ and column sums $\lambda $ . In fact, one can view the polynomials $a_{\mu \lambda }(t)$ as the generating polynomial for a suitably defined combinatorial statistic on $(0,1)$ -matrices (Macdonald [Reference Macdonald29, p. 211]). On the other hand, the polynomials $\tilde {a}_{\mu \lambda }(t)$ do not have nonnegative coefficients in general and do not appear to have a nice combinatorial description. A very intricate explicit formula for $\tilde {a}_{\mu \lambda }(t)$ was found by Lassalle and Schlosser [Reference Lassalle and Schlosser25, Thm. 7.5] who gave an expression for the more general two-parameter coefficients in the elementary expansion of Macdonald polynomials. Recall that the Kostka numbers $K_{\lambda \mu }$ arise as coefficients in the monomial expansion of the Schur function, $ s_\lambda =\sum _{\mu } K_{\lambda \mu }m_{\mu }.$ The following lemma (Kirillov [Reference Kirillov23, Eq. (0.3)]) expresses the polynomials $a_{\mu \lambda }(t)$ above in terms of Kostka numbers and Kostka–Foulkes polynomials.

For each partition $\lambda $ , let $\epsilon _\lambda =(-1)^{|\lambda |-\ell (\lambda )}$ , where $\ell (\lambda )$ denotes the number of parts of $\lambda $ . The following theorem is the main result of this section.

Theorem 4.2. For each partition $\mu $ of n,

$$ \begin{align*} \sigma(\mu,\Delta)=\epsilon_{\mu'}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}}\sum_{\lambda \vdash n}\tilde{a}_{\mu' \lambda}(q)X_\lambda(\Delta), \end{align*} $$

for every prime power q and every matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ .

Proof. Define

(4.2) $$ \begin{align} \tilde{\sigma}(\mu,\Delta):=\epsilon_{\mu}q^{-\sum_{j\geq 2}{\mu^{\prime}_j \choose 2}}\sigma(\mu',\Delta), \end{align} $$

and note that the theorem is equivalent to $\tilde {\sigma }(\mu ,\Delta )=\sum _{\lambda }\tilde {a}_{\mu \lambda }(q)X_\lambda (\Delta )$ . To prove this, it suffices to show that

$$ \begin{align*} X_\lambda(\Delta)= \sum_{\mu}a_{\lambda \mu}(q) \tilde{\sigma}(\mu,\Delta), \end{align*} $$

since the matrices $(\tilde {a}_{\lambda \mu }(q))$ and $(a_{\lambda \mu }(q))$ for $\lambda $ and $\mu $ varying over partitions of n are mutually inverse to each other. In view of Theorem 2.19, it suffices to show that Theorem 4.2 holds for sufficiently large prime powers q. Fix a prime power $q\geq n$ and, for each partition $\nu $ of n, let $\Delta _{\nu }$ be a diagonal matrix of type $\nu $ over ${\mathbb F}_q$ . Given a partition $\lambda $ of n, consider the system of equations

(4.3) $$ \begin{align} X_\lambda(\Delta_\nu)= \sum_{\mu}y_{\mu}\, \tilde{\sigma}(\mu,\Delta_\nu), \end{align} $$

in the variables $y_{\mu }$ as $\nu $ varies over all partitions of n. We claim that the system has a unique solution given by $y_{\mu }=a_{\lambda \mu }(q)$ . To prove the claim, it suffices to show that the determinant $(\tilde {\sigma }(\mu ,\Delta _\nu ))$ for $\mu $ and $\nu $ varying over partitions of n is nonsingular and Equation (4.3) holds for $y_{ \mu }=a_{\lambda \mu }(q)$ .

Consider the determinant $D=\det (\tilde {\sigma }(\mu ,\Delta _\nu ))$ whose rows and columns are indexed by partitions $\mu ,\nu $ of n, respectively, in lexicographic order (so that $(1^n)$ comes first and $(n)$ comes last). By Theorem 3.2 and the defining equation (4.2) for $\tilde {\sigma }(\mu ,\Delta )$ , it follows that D is equal to the determinant $\det (b_{\mu '\nu }(q))$ up to sign and a power of $(q-1)$ . By permuting the rows of the determinant, it is clear that $\det (b_{\mu '\nu }(q))$ equals $\det (b_{\mu \nu }(q))$ up to sign. By Remark 3.4, $b_{\mu \nu }(q)=0$ unless $\mu \geq \nu $ in the dominance order and $b_{\mu \mu }(q)\neq 0$ for each prime power q. Thus the matrix $(b_{\mu \nu }(q))$ is lower triangular with nonzero diagonal entries. Therefore it is nonsingular, implying that D is nonsingular.

We use monomial generating functions to prove that Equation (4.3) holds for $y_{ \mu }=a_{\lambda \mu }(q)$ . Accordingly, let $m_\lambda $ denote the monomial symmetric function indexed by the partition $\lambda $ . The monomial generating function of the left-hand side of Equation (4.3) is given by

$$ \begin{align*} \sum_{\lambda}X_\lambda(\Delta_\nu)m_{\lambda}=\prod_{i\geq 1}W_{(\nu_i)}(x;q), \end{align*} $$

by Example 2.16. On the other hand, the monomial generating function for the right-hand side of Equation (4.3) with $y_{\mu }=a_{\lambda \mu }(q)$ is given by

$$ \begin{align*} \sum_{\lambda}\sum_{\mu}a_{\lambda \mu}(q) \tilde{\sigma}(\mu,\Delta_\nu)m_\lambda &=\sum_{\mu}\tilde{\sigma}(\mu,\Delta_\nu)\sum_{\lambda}a_{\lambda \mu}(q) m_\lambda. \end{align*} $$

By Lemma 4.1, the last expression above is equal to

$$ \begin{align*} \sum_{\mu}\tilde{\sigma}(\mu,\Delta_\nu)\sum_{\lambda}\sum_{\eta}K_{\eta\lambda}K_{\eta'\mu}(q)m_\lambda&=\sum_{\mu}\tilde{\sigma}(\mu,\Delta_\nu)\sum_{\eta}K_{\eta'\mu}(q)s_\eta\\ &=\sum_{\mu}\tilde{\sigma}(\mu,\Delta_\nu)W_{\mu'}(x;q), \end{align*} $$

where the last equality follows from Equation (3.2). By Theorem 3.2, the last sum above is equal to

$$ \begin{align*} \sum_{\mu} \epsilon_\mu (q-1)^{\sum_{j\geq 2}\mu^{\prime}_j}b_{\mu'\nu}(q) W_{\mu'}(x;q) &=\sum_{\mu} (1-q)^{|\mu|-\mu^{\prime}_1}b_{\mu'\nu}(q) W_{\mu'}(x;q)\\ &= \prod_{i=1}^k W_{(\nu_i)}(x;q), \end{align*} $$

by Proposition 3.7. This completes the proof.

The theorem can be restated in the following alternate form using the Hall scalar product.

Theorem 4.3. For each partition $\mu $ of n,

$$ \begin{align*} \sigma(\mu,\Delta) &=\epsilon_{\mu'}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}}\langle F_\Delta(x) , \widetilde{W}_{\mu}(x;q)\rangle, \end{align*} $$

for every prime power q and every matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ .

Proof. By applying the $\omega $ involution to Equation (4.1), one obtains $ \omega P_{\mu '}(x;t)=\sum _{\lambda }\tilde {a}_{\mu '\lambda }(t)h_{\lambda }$ . Since $\langle m_\lambda ,h_\mu \rangle =\delta _{\lambda \mu }$ , Theorem 4.2 can be written as

$$ \begin{align*}\sigma(\mu,\Delta)=\epsilon_{\mu'}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}}\langle F_\Delta(x) , \omega P_{\mu'}\rangle.\end{align*} $$

The result now follows from Equation (3.4).

Theorem 4.3 gives the following combinatorial interpretation for the coefficients in the q-Whittaker expansion of the invariant flag generating function $F_{\tau }(x;t)$ (see Equation (2.8)) associated to a similarity class type $\tau $ .

Corollary 4.4. For each similarity class type $\tau =\{(d_1,\lambda ^1),(d_2,\lambda ^2),\ldots ,(d_k,\lambda ^k)\}$ of size n,

$$ \begin{align*} F_\tau(x;t)=\prod_{i=1}^k p_{d_i}[\tilde{H}_{\lambda^i}(x;t)]=\sum_{\mu\vdash n}\epsilon_{\mu'}t^{-\sum_{j\geq 2}{\mu_j \choose 2}}\sigma(\mu,\tau) W_\mu(x;t), \end{align*} $$

where $\sigma (\mu ,\tau )$ denotes the number of subspaces which have profile $\mu $ with respect to a matrix of similarity class type $\tau $ over the finite field $\mathbb {F}_t$ for sufficiently large prime powers t.

In view of the examples considered in Section 2, Corollary 4.4 gives a combinatorial finite-field interpretation for the coefficients in the q-Whittaker expansion of the power sum symmetric functions, the complete homogeneous symmetric functions, products of modified Hall–Littlewood functions, and products of single-part q-Whittaker functions.

Example 4.5. Specializing Corollary 4.4 to the regular nilpotent and simple similarity class types and using Equations (1.1) and (1.2), we obtain the following expansions for homogeneous and power sum symmetric functions:

$$ \begin{align*} h_n&=\sum_{\mu \vdash n}(-1)^{n-\mu_1}\left(\prod_{i\geq 2}t^{\mu_i+1 \choose 2}{\mu_{i-1} \brack \mu_i}_t\right) W_\mu(x;t),\\ p_n&=\sum_{\mu \vdash n}(-1)^{n-\mu_1}\frac{t^n-1}{t^{\mu_1}-1}\left(\prod_{i\geq 2}t^{\mu_i \choose 2}{\mu_{i-1} \brack \mu_i}_t\right) W_\mu(x;t). \end{align*} $$

The q-Whittaker functions have recently arisen in the work of Karp and Thomas [Reference Karp and Thomas22] in the context of counting certain partial flags compatible with a nilpotent endomorphism over a finite field. They also obtain an elegant probabilistic bijection between nonnegative integer matrices and pairs of semistandard tableaux. It would be interesting to relate their work to the counting problem considered in this paper.

5 Arbitrary profiles

An explicit formula for $\sigma (\mu ,\Delta )$ when $\mu $ is a partition of the ambient vector space dimension was obtained in Theorem 4.2. In this section we extend the result to arbitrary partitions $\mu $ .

Lemma 5.1. For each partition $|\mu |\leq n$ , there exists a unique homogeneous symmetric function $G_{\mu }(x;t)\in \Lambda _{{\mathbb Q}(t)}$ of degree n, such that

$$ \begin{align*} \sigma(\mu,\Delta)=\langle F_\Delta(x),G_{\mu}(x;q) \rangle, \end{align*} $$

for every prime power q and each matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ .

Proof. By Theorem 2.19, there exist polynomials $g_{\mu \lambda }(t)\in {\mathbb Z}[t]$ , depending only on $\mu $ and $\lambda $ , such that

$$ \begin{align*} \sigma(\mu,\Delta)=\sum_{\lambda \vdash n}g_{\mu \lambda}(q)X_\lambda(\Delta), \end{align*} $$

for each prime power q and each matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ . If we define $ G_{\mu }(x;t):=\sum _{\lambda \vdash n}g_{\mu \lambda }(t)h_\lambda ,$ then the duality of the bases $m_\lambda $ and $h_\lambda $ with respect to the Hall scalar product implies that $ \sigma (\mu ,\Delta )=\langle F_\Delta (x),G_{\mu }(x;q) \rangle ,$ proving existence. To show uniqueness, suppose $G_{\mu }(x;t)$ and $\tilde {G}_{\mu }(x;t)$ are homogeneous symmetric functions of degree n satisfying

$$ \begin{align*} \langle F_\Delta(x), G_{\mu}(x;q)\rangle=\langle F_\Delta(x), \tilde{G}_{\mu}(x;q)\rangle, \end{align*} $$

for every prime power q and every matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ . Fix q and allow $\Delta $ to vary over nilpotent matrices in ${\mathrm M}_n({\mathbb F}_q)$ . Since $F_\Delta (x)=\tilde {H}_\lambda (x;q)$ when $\Delta $ is nilpotent with Jordan partition $\lambda $ , the bilinearity of the Hall scalar product yields

$$ \begin{align*} \langle \tilde{H}_\lambda(x;q), G_{\mu}(x;q)-\tilde{G}_{\mu}(x;q)\rangle=0, \end{align*} $$

for each partition $\lambda $ of n. The relations $ \tilde {H}_\lambda (x;q)=\sum _{\mu }\tilde {K}_{\mu \lambda }(q)s_\mu ,$ are upper triangular with the diagonal entries $\tilde {K}_{\mu \mu }(q)$ being powers of q. Therefore, the $\tilde {H}_\lambda (x;q)$ form a basis for homogeneous symmetric functions in $\Lambda _{{\mathbb Q}(t)}$ of degree n. It follows that $G_{\mu }(x;q)=\tilde {G}_{\mu }(x;q)$ . Since this holds for each prime power q, it follows that $G_{\mu }(x;t)=\tilde {G}_\mu (x;t)$ , proving uniqueness.

The following result of Bender, Coley, Robbins and Rumsey was derived by a probabilistic argument and shows that $\sigma (\mu ,\Delta )$ satisfies a remarkably simple system of equations.

Theorem 5.2 [Reference Bender, Coley, Robbins and Rumsey6, Eq. (4)].

Let n be a positive integer and suppose $\nu $ is a partition with $|\nu |<n$ . For each matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q),$

$$ \begin{align*} \sum_{\mu:|\mu|\leq n} (-1)^{\mu_1}q^{-\mu \cdot \nu+{\mu_1 \choose 2}} \sigma(\mu,\Delta)=0, \end{align*} $$

where the sum is taken over all partitions $\mu $ of size at most n (including the empty partition) and $\mu \cdot \nu :=\sum _{j\geq 1}\mu _j\nu _j.$

Note that the system of equations in Theorem 5.2 is indexed by partitions $\nu $ of size at most n. Bender, Coley, Robbins and Rumsey used these equations to derive an explicit formula for $\sigma (\mu ,\Delta )$ in the cases where $\Delta $ is simple or regular nilpotent. Our approach is to use Theorem 5.2 to solve for $\sigma (\mu ,\Delta )$ for partitions satisfying $|\mu |<n$ using the formula already obtained for $\sigma (\mu ,\Delta )$ in Theorem 4.2 when $|\mu |=n$ . The following theorem is our main result.

Theorem 5.3. For each partition $\mu $ ,

$$ \begin{align*} \sigma(\mu,\Delta)=\epsilon_{\mu'}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}}\langle F_\Delta(x),\widetilde{W}_{\mu}(x;q)\, h_{n-|\mu|} \rangle, \end{align*} $$

for each prime power q and each matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ .

Proof. By Lemma 5.1, there is a unique symmetric function $C_{\mu }(x;t)$ of degree n such that

(5.1) $$ \begin{align} \sigma(\mu,\Delta)=(-1)^{\sum_{j\geq 2}\mu_j}q^{\sum_{j\geq 2}{\mu_j \choose 2}}\langle F_\Delta(x),C_\mu(x;q) \rangle, \end{align} $$

for each prime power q and each matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ . We wish to show that $C_\mu (x;t)=\widetilde {W}_{\mu }(x;t)h_{n-|\mu |}$ , where $\widetilde {W}_\lambda $ denotes the dual q-Whittaker function indexed by $\lambda $ . Consider the coefficients $c_{\eta \mu }(t)$ defined by

(5.2) $$ \begin{align} C_{\mu}(x;t)=\sum_{\eta\vdash n}c_{\eta\mu}(t)\widetilde{W}_{\eta}(x;t), \end{align} $$

When $\mu $ is a partition of n, it follows from Theorem 4.3 that $C_{\mu }=\widetilde {W}_{\mu }$ ; therefore

(5.3) $$ \begin{align} c_{\eta\mu}(t)=\delta_{\eta\mu} \quad (|\mu|=n), \end{align} $$

where $\delta $ denotes the Kronecker delta. Substituting the expression (5.1) for $\sigma (\mu ,\Delta )$ into the equations in Theorem 5.2, we obtain

$$ \begin{align*} \sum_{\mu:|\mu|\leq n} (-1)^{|\mu|}q^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} \langle F_\Delta(x),C_\mu(x;q)\rangle=0, \end{align*} $$

for each partition $|\nu |<n.$ Fix $\nu $ with $|\nu |<n$ and set

$$\begin{align*}S_{\nu,q}(x):=\sum_{\mu:|\mu|\leq n} (-1)^{|\mu|}q^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}}\, C_\mu(x;q). \end{align*}$$

Then $\langle F_\Delta (x),S_{\nu ,q}(x)\rangle =0$ for every $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ . By varying $\Delta $ over nilpotent matrices, it follows that $\langle \tilde {H}_\lambda (x;q),S_{\nu ,q}(x)\rangle =0$ for each partition $\lambda $ of n. Since $\tilde {H}_\lambda (x;q)$ is a basis for homogeneous symmetric functions in $\Lambda _{{\mathbb Q}(t)}$ of degree n, this forces $S_{\nu ,q}(x)=0$ . As this holds for each prime power q, the identity continues to hold after replacing q by an indeterminate t; in other words,

$$ \begin{align*} \sum_{\mu:|\mu|\leq n} (-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} C_\mu(x;t)=0 \quad (|\nu|<n). \end{align*} $$

By Equation (5.2), the expression on the left-hand side above can be written as

$$ \begin{align*} &\sum_{\mu:|\mu|\leq n} (-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} \sum_{\eta\vdash n}c_{\eta\mu}(t)\widetilde{W}_{\eta}(x;t)\\ &\quad=\sum_{\eta\vdash n}\sum_{\mu:|\mu|\leq n} (-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} c_{\eta\mu}(t)\widetilde{W}_{\eta}(x;t). \end{align*} $$

Since the Hall-Littlewood functions $P_\lambda (x;t) (\lambda \vdash n)$ are linearly independent and $\omega $ is an automorphism of $\Lambda _{{\mathbb Q}(t)}$ , it follows that the dual q-Whittaker functions $\widetilde {W}_{\eta }(x;t)=\omega P_{\eta '}(x;t)$ are also linearly independent. Consequently,

$$ \begin{align*} \sum_{\mu:|\mu|\leq n} (-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} c_{\eta\mu}(t)=0 \quad \text{ for }|\nu|<n, |\eta|=n. \end{align*} $$

By Equation (5.3), this is equivalent to

$$ \begin{align*} \sum_{\mu:|\mu|< n} (-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} c_{\eta\mu}(t)+ (-1)^{n}t^{-\eta \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} =0 \quad (|\nu|<n), \end{align*} $$

for each partition $\eta $ of n. The idea now is to solve the above system of equations for the $c_{\eta \mu }(t)$ with $|\mu |<n$ . Note that the number of unknowns is equal to the number of equations, namely the number of integer partitions of size less than n. We claim that the system has a unique solution given by

(5.4) $$ \begin{align} c_{\eta\mu}(t)=\psi_{\eta/\mu}(t):=\prod_{i\geq 1}{\eta_i-\eta_{i+1}\brack \eta_i-\mu_i}_t. \end{align} $$

Observe that $\psi _{\eta /\mu }(t)$ vanishes unless $\eta /\mu $ is a horizontal strip. Moreover, the only partition $\mu $ of n for which $\eta /\mu $ is a horizontal strip is $\mu =\eta $ . Therefore, $\psi _{\eta /\mu }(t)=\delta _{\eta \mu }$ when $\mu $ is a partition of n, in accordance with Equation (5.3). Therefore, to prove the claim, it suffices to show the following.

1. 1. The determinant with entries $(-1)^{|\mu |}t^{-\mu \cdot \nu +\sum _{j\geq 1}{\mu _j \choose 2}}$ for $\mu ,\nu $ varying over integer partitions of size less than n is nonzero.

2. 2. For each partition $\eta $ of n,

   $$ \begin{align*} \sum_{\mu:|\mu|\leq n} (-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}} \psi_{\eta/\mu}(t)=0, \end{align*} $$
   for each partition $\nu $ of size less than n.

The last two statements above are proved in Corollaries 5.5 and 5.7, respectively. From Equation (5.2), we obtain

$$ \begin{align*} C_{\mu}(x;t)&=\sum_{\eta\vdash n}\psi_{\eta/\mu}(t)\widetilde{W}_{\eta}(x;t)=\widetilde{W}_{\mu}(x;t)h_{n-|\mu|}, \end{align*} $$

where the last equality follows by writing the Pieri rule for Hall–Littlewood functions as $P_{\mu '}e_{n-|\mu |}=\sum _{\eta \vdash n}\psi _{\eta /\mu }(t)P_{\eta '}$ (Macdonald [Reference Macdonald29, p. 340, Eq. (6.24)]) and applying $\omega $ . The result now follows by Equation (5.1).

We now prove the two claims made in the proof of Theorem 5.3. We introduce some notation, following Buck, Coley, and Robbins [Reference Buck, Coley and Robbins10], to state the relevant results. Let $\mathcal {P}$ denote the set of all partitions of nonnegative integers. Given partitions $\lambda =(\lambda _1,\lambda _2,\ldots )$ and $\mu =(\mu _1,\mu _2,\ldots )$ in $\mathcal {P}$ , write $\lambda \subseteq \mu $ to mean $\lambda _i\leq \mu _i$ for each $i\geq 1$ . With respect to the ordering $\subseteq $ , the set $\mathcal {P}$ forms a distributive lattice called Young’s lattice, denoted Y (Stanley [Reference Stanley38, Sec. 7.2]). An order ideal I in Y is a subset $I\subseteq Y$ such that if $\mu \in I$ and $\lambda \subseteq \mu $ for some $\lambda \in Y$ , then $\lambda \in I$ . Given a partition $\lambda =(\lambda _1,\lambda _2,\ldots )$ , the shift operator is defined by $\mathrm {sh}(\lambda ):=(\lambda _2,\lambda _3,\ldots )$ . To each pair $(i,j)$ of nonnegative integers, we associate an indeterminate $x_{i,j}$ . Given a pair of partitions $\lambda $ and $\mu ,$ associate a monomial by

$$ \begin{align*} x_\lambda^\mu=\prod_{k\geq 1}x_{k,\lambda_k}^{\mu_k}. \end{align*} $$

For partitions $\lambda ,\mu $ , write $\lambda \lessdot \mu $ if $\lambda \subseteq \mu $ and the partitions $\lambda $ and $\mu $ differ in precisely one coordinate. If they differ in the rth coordinate, let $\delta _x(\mu ,\lambda )$ denote the difference $x_{r,\mu _r}-x_{r,\lambda _r}$ . Buck, Coley, and Robbins [Reference Buck, Coley and Robbins10, Thm. 2] proved the following nice product formula for the determinant with entries $x^\mu _{\lambda }.$

Lemma 5.4. If $I\subset Y$ is a finite order ideal, then

$$ \begin{align*} \det(x_\lambda^\mu)_{\lambda,\mu\in I}=\pm\prod_{\lambda \in I}x_\lambda^{\mathrm{sh}(\lambda)}\prod_{\substack{ \lambda,\mu\in I\\\lambda \lessdot \mu}} \delta_x(\mu,\lambda). \end{align*} $$

Proof. Let $A=(a_{\mu \nu })_{\mu ,\nu \in I}$ denote the matrix with entries

$$\begin{align*}a_{\mu\nu}=(-1)^{|\mu|}\,t^{-\mu\cdot\nu+\sum_{j\ge1}\binom{\mu_j}{2}}. \end{align*}$$

For each fixed $\mu \in I$ , factoring $(-1)^{|\mu |}\,t^{\sum _{j\ge 1}\binom {\mu _j}{2}}$ out of the $\mu $ -th row scales the determinant by the nonzero factor $\prod _{\mu \in I}(-1)^{|\mu |}t^{\sum _{j\ge 1}\binom {\mu _j}{2}}$ . Hence $\det (A)\neq 0$ if and only if $\det (t^{-\mu \cdot \nu })_{\mu ,\nu \in I}\neq 0$ . If we set $x_{i,j}=t^{-j}$ in Lemma 5.4, then $x_{\nu }^\mu =t^{-\mu \cdot \nu }$ which is nonzero. For $\mu \lessdot \nu $ , the quantity $\delta _x(\mu ,\nu )$ is also nonzero, being a difference of distinct integer powers of t. The result follows from these observations.

Lemma 5.6. Let $\psi _{\eta /\mu }(t)$ be as defined in Equation (5.4). For all partitions $\nu $ and $\eta $ ,

$$ \begin{align*} &\sum_{\mu}(-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}}\psi_{\eta/\mu}(t)\\ &\qquad\qquad\qquad=(-1)^{|\eta|}(1-t)^{\eta_1}t^{-\eta\cdot \nu+\sum_{j \geq 1}{\eta_j \choose 2}}\prod_{i\geq 1}{\nu_i-\eta_{i+1} \brack \eta_i-\eta_{i+1}}_t[\eta_i-\eta_{i+1}]_t!, \end{align*} $$

where the sum is taken over all partitions $\mu $ such that $\eta /\mu $ is a horizontal strip.

Proof. Let $s(\eta ,\nu )$ denote the sum in the statement of the lemma. Note the sum is unchanged when taken over all integer partitions $\mu $ since $\psi _{\eta /\mu }(t)$ automatically vanishes unless $\eta /\mu $ is a horizontal strip. We proceed by induction on the length $\ell (\eta )$ of $\eta $ . When $\eta $ is the empty partition, the left-hand side of the identity equals 1. Since $[0]_t!=1$ , the right-hand side reduces to 1 as well and the result holds in this case. Now suppose the result is true for $\ell (\eta )=\ell -1$ and let $\eta $ be a partition with $\ell $ parts. By conditioning on the first part k of $\mu $ , write the sum $s(\eta ,\nu )$ as

$$ \begin{align*} s(\eta,\nu)&=\sum_{\mu}(-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}}\prod_{i\geq 1}{\eta_i-\eta_{i+1}\brack \eta_i-\mu_i}_t\\ &=\sum_{k=\eta_2}^{\eta_1}(-1)^k t^{-k\nu_1+{k \choose 2}}{\eta_1-\eta_2\brack \eta_1-k}_t\sum_{\tilde{\mu}}(-1)^{|\tilde{\mu}|}t^{-\tilde{\mu} \cdot \tilde{\nu}+\sum_{j\geq 1}{\tilde{\mu}_j \choose 2}}\psi_{\tilde{\eta}/\tilde{\mu}}, \end{align*} $$

where $\tilde {\lambda }$ denotes the partition obtained by removing the first part of $\lambda $ and the sum is taken over all partitions $\tilde {\mu }$ . The inner sum above is equal to $s(\tilde {\eta },\tilde {\nu })$ . Therefore,

$$ \begin{align*} s(\eta,\nu)= s(\tilde{\eta},\tilde{\nu})\sum_{k=\eta_2}^{\eta_1}(-1)^k t^{-k\nu_1+{k \choose 2}}{\eta_1-\eta_2\brack \eta_1-k}_t. \end{align*} $$

With $j=k-\eta _2$ , we obtain

(5.5) $$ \begin{align} s(\eta,\nu)&=(-1)^{\eta_2}s(\tilde{\eta},\tilde{\nu})\sum_{j=0}^{\eta_1-\eta_2}(-1)^j t^{-(j+\eta_2)\nu_1+{j+\eta_2 \choose 2}}{\eta_1-\eta_2\brack j}_t \notag \\ &=(-1)^{\eta_2}t^{-\eta_2\nu_1+{\eta_2\choose 2}}s(\tilde{\eta},\tilde{\nu})\sum_{j=0}^{\eta_1-\eta_2}(-1)^j t^{j(\eta_2-\nu_1)+{j \choose 2}}{\eta_1-\eta_2\brack j}_t. \end{align} $$

By applying the q-binomial theorem [Reference Stanley39, Eq. (1.87)]

$$ \begin{align*} (1-x)(1-tx)\cdots (1-t^{n-1}x)=\sum_{j=0}^n (-1)^jt^{j \choose 2} {n \brack j}_tx^j, \end{align*} $$

with $n=\eta _1-\eta _2$ and $x=t^{-(\nu _1-\eta _2)}$ , the sum in Equation (5.5) above becomes

$$ \begin{align*} &\left(1-\frac{1}{t^{\nu_1-\eta_2}}\right)\left(1-\frac{1}{t^{\nu_1-\eta_2-1}}\right)\cdots \left(1-\frac{1}{t^{\nu_1-\eta_1+1}}\right)\\ &\quad =\frac{(t-1)^{\eta_1-\eta_2}}{t^{(\nu_1-\eta_2)(\eta_1-\eta_2)-{\eta_1-\eta_2 \choose 2}}}{\nu_1-\eta_2 \brack \eta_1-\eta_2}_t[\eta_1-\eta_2]_t!. \end{align*} $$

By the inductive hypothesis,

$$ \begin{align*} s(\tilde{\eta},\tilde{\nu})=(-1)^{|\tilde{\eta}|}(1-t)^{\eta_2}t^{-\tilde{\eta}\cdot \tilde{\nu}+\sum_{j \geq 2}{{\eta}_j \choose 2}}\prod_{i\geq 2}{\nu_i-{\eta}_{i+1} \brack{\eta}_i-{\eta}_{i+1}}_t[{\eta}_i-{\eta}_{i+1}]_t!. \end{align*} $$

By substituting the above expression for $s(\tilde {\eta },\tilde {\nu })$ into Equation (5.5), a straightforward calculation shows that

$$ \begin{align*} s(\eta,\nu)&=(-1)^{\eta_2}t^{-\eta_2\nu_1+{\eta_2\choose 2}}s(\tilde{\eta},\tilde{\nu})\frac{(t-1)^{\eta_1-\eta_2}}{t^{(\nu_1-\eta_2)(\eta_1-\eta_2)-{\eta_1-\eta_2 \choose 2}}}{\nu_1-\eta_2 \brack \eta_1-\eta_2}_t[\eta_1-\eta_2]_t!\\ &= (-1)^{|\eta|}(1-t)^{\eta_1}t^{-\eta\cdot \nu+\sum_{j \geq 1}{\eta_j \choose 2}}\prod_{i\geq 1}{\nu_i-\eta_{i+1} \brack \eta_i-\eta_{i+1}}_t[\eta_i-\eta_{i+1}]_t!, \end{align*} $$

completing the inductive step and the proof.

Corollary 5.7. For partitions $\nu ,\eta $ satisfying $|\nu |<|\eta |=n$ , we have

$$ \begin{align*}\sum_{\mu:|\mu|\leq n}(-1)^{|\mu|}t^{-\mu \cdot \nu+\sum_{j\geq 1}{\mu_j \choose 2}}\psi_{\eta/\mu}(t)=0. \end{align*} $$

6 Partial profiles and anti-invariant subspaces

Definition 6.1. Given a matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ , a subspace $W\subseteq {\mathbb F}_q^n$ has partial $\Delta $ -profile $\rho =(\rho _1,\rho _2,\ldots ,\rho _r)$ if

$$ \begin{align*} \dim (W+\Delta W+\cdots +\Delta^{j-1}W)=\rho_1+\rho_2+\cdots+\rho_{j} \text{ for }1\leq j\leq r. \end{align*} $$

Let $\pi (\rho ,\Delta )$ denote the number of subspaces with partial $\Delta $ -profile $\rho $ .

Note that $\pi ((m,0),\Delta )$ is the number of m-dimensional $\Delta $ -invariant subspaces which is distinct from $\pi ((m),\Delta )$ in general. Therefore, we think of $\rho $ as a tuple rather than an integer partition. It is evident that the number of subspaces with $\Delta $ -profile $\mu =(\mu _1,\ldots ,\mu _k)$ equals the number of subspaces with partial $\Delta $ -profile $(\mu _1,\ldots ,\mu _k,0)$ .

Definition 6.3 [Reference Knüppel and Nielsen24, p. 1].

Given $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ and a positive integer t, a subspace W of ${\mathbb F}_q^n$ is said to be t-fold $\Delta $ -anti-invariant if

$$ \begin{align*} \dim(W+\Delta W+\cdots+\Delta^t W)=(t+1)\dim W. \end{align*} $$

Thus an m-dimensional $\Delta $ -anti-invariant subspace is precisely one with partial $\Delta $ -profile $(m^{t+1})$ . Anti-invariant subspaces were originally defined with $t=1$ by Barría and Halmos [Reference Barría and Halmos5], motivated by earlier work of Hadwin, Nordgren, Radjavi, and Rosenthal [Reference Hadwin, Nordgren, Radjavi and Rosenthal18] on the weak density of certain sets of operators on Banach spaces. Barría and Halmos determined the maximum possible dimension of an anti-invariant subspace. Another proof of their result was given by Sourour [Reference Sourour37]. This result was extended to arbitrary t by Knüppel and Nielsen [Reference Knüppel and Nielsen24].

Theorem 6.4. Given $\rho =(\rho _1,\ldots ,\rho _r)$ with $\rho _r\neq 0$ and $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ , the number of subspaces with partial $\Delta $ -profile $\rho $ is given by

$$ \begin{align*} \pi(\rho,\Delta)=\langle \omega F_\Delta(x), G_\rho\rangle, \end{align*} $$

where

$$ \begin{align*} G_\rho=(-1)^{\sum_{j\geq 2}\rho_j}q^{\sum_{j\geq 2}{\rho_j\choose 2}}\sum_{\substack{\eta \vdash n\\ \ell(\eta)=r}}\psi_{\eta/\rho}(q)P_{\eta'}(x;q). \end{align*} $$

Proof. We have

$$ \begin{align*} \pi(\rho,\Delta)&=\sum_{\substack{\mu:|\mu|\leq n\\ \mu_i=\rho_i (1\leq i\leq r)}}\sigma(\mu,\Delta)\\ &=\sum_{\substack{\mu:|\mu|\leq n\\ \mu_i=\rho_i (1\leq i\leq r)}}(-1)^{\sum_{j\geq 2}\mu_j}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}}\langle \omega F_\Delta(x),P_{\mu'}(x;q)\, e_{n-|\mu|} \rangle, \end{align*} $$

by Theorem 5.3. Therefore $\pi (\rho ,\Delta )=\langle \omega F_\Delta (x),G_\rho \rangle ,$ where

$$ \begin{align*} G_\rho=\sum_{\substack{\mu:|\mu|\leq n\\ \mu_i=\rho_i (1\leq i\leq r)}}(-1)^{\sum_{j\geq 2}\mu_j}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}}P_{\mu'}(x;q)\, e_{n-|\mu|}. \end{align*} $$

By the Pieri rule for Hall–Littlewood functions, we have $P_{\mu '}e_{n-|\mu |}=\sum _{\eta \vdash n}\psi _{\eta /\mu }P_{\eta '}.$ It follows that

$$ \begin{align*} G_\rho&=\sum_{\substack{\mu:|\mu|\leq n\\ \mu_i=\rho_i (1\leq i\leq r)}}(-1)^{\sum_{j\geq 2}\mu_j}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}} \sum_{\eta\vdash n}\psi_{\eta/\mu}(q)P_{\eta'}(x;q)\\ &=\sum_{\eta\vdash n}\sum_{\substack{\mu:|\mu|\leq n\\ \mu_i=\rho_i (1\leq i\leq r)}}(-1)^{\sum_{j\geq 2}\mu_j}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}} \psi_{\eta/\mu}(q) P_{\eta'}(x;q). \end{align*} $$

Write $\mu =(\rho _1,\ldots ,\rho _r,\bar {\mu }_1,\bar {\mu }_2,\ldots )$ and $\bar {\eta }=(\eta _{r+1},\eta _{r+2},\ldots )$ , $\bar {\mu }=(\ \bar {\mu }_1,\bar {\mu }_2,\ldots )$ . If we define

$$\begin{align*}\psi^{(r)}_{\eta/\rho}(q):=\prod_{i=1}^{r}{\eta_i-\eta_{i+1}\brack \eta_i-\rho_i}_q, \end{align*}$$

then $\psi _{\eta /\mu }(q)=\psi ^{(r)}_{\eta /\rho }(q)\cdot \psi _{\bar {\eta }/\bar {\mu }}(q).$ The coefficient of $P_{\eta '}(x;q)$ in $G_\rho $ equals

$$ \begin{align*} &\sum_{\substack{\mu:|\mu|\leq n\\ \mu_i=\rho_i (1\leq i\leq r)}}(-1)^{\sum_{j\geq 2}\mu_j}\, q^{\sum_{j\geq 2}{\mu_j \choose 2}} \psi_{\eta/\mu}(q)\\ &\qquad=(-1)^{\sum_{j\geq 2}\rho_j}\, q^{\sum_{j\geq 2}{\rho_j \choose 2}}\, \psi^{(r)}_{\eta/\rho}(q)\sum_{\bar{\mu}:|\bar{\mu}|\leq n-|\rho|} (-1)^{\sum_{j\geq 1}\bar{\mu}_j}\, q^{\sum_{j\geq 1}{\bar{\mu}_j \choose 2}} \psi_{\bar{\eta}/\bar{\mu}}(q). \end{align*} $$

If $\bar {\eta }$ is not the empty partition, then the inner sum vanishes by Corollary 5.7 with $\nu =\emptyset $ . If $\bar {\eta }=\emptyset $ , then $\psi _{\bar {\eta }/\bar {\mu }}(q)=0$ unless $\bar {\mu }=\emptyset $ , so the inner sum equals $1$ . Moreover, since $\rho _r\neq 0$ , the condition $\eta /\rho $ being a horizontal strip forces $\ell (\eta )=r$ , and in this case $\psi ^{(r)}_{\eta /\rho }(q)=\psi _{\eta /\rho }(q)$ . It follows that

$$ \begin{align*} G_\rho=(-1)^{\sum_{j\geq 2}\rho_j}q^{\sum_{j\geq 2}{\rho_j\choose 2}}\sum_{\substack{\eta \vdash n\\ \ell(\eta)=r}}\psi_{\eta/\rho}(q)P_{\eta'}(x;q), \end{align*} $$

proving the result.

Corollary 6.5. Given $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ and a positive integer t, the number of t-fold $\Delta $ -anti-invariant subspaces of dimension m is given by

$$ \begin{align*} (-1)^{mt}q^{t{m \choose 2}} \langle \omega F_\Delta(x),P_{((t+1)^m,1^{n-m(t+1)})}(x;q) \rangle, \end{align*} $$

for $m(t+1)\leq n$ .

7 Application to Krylov subspace methods

Let $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ and consider a subset $S=\{v_1,\ldots ,v_k\}$ of column vectors in ${\mathbb F}_q^n$ . The truncated Krylov subspace of order $\ell $ generated by S is defined by

$$ \begin{align*} \mathrm{Kry}(\Delta,S,\ell):=W+\Delta W+\cdots+\Delta^{\ell-1}W, \end{align*} $$

where $W=W_S$ denotes the subspace spanned by S. Let $\psi _{k,\ell }(\Delta )$ denote the probability of selecting a k-tuple of vectors uniformly at random from ${\mathbb F}_q^n$ such that the truncated Krylov subspace of order $\ell $ spanned by them is all of ${\mathbb F}_q^n$ . Thus

(7.1) $$ \begin{align} \psi_{k,\ell}(\Delta):=\frac{1}{q^{nk}}|\{(v_1,\ldots,v_k)\in ({\mathbb F}_q^n)^k : \mathrm{ Kry}(\Delta,\{v_1,\ldots,v_k\};\ell)={\mathbb F}_q^n\}|. \end{align} $$

Computing $\psi _{k,\ell }(\Delta )$ is essential for analyzing a class of algorithms that solve large, sparse linear systems over finite fields, commonly encountered in number theory and computer algebra (Watkins [Reference Watkins40]). These algorithms, collectively referred to as Krylov subspace methods, have origins that can be traced back to contributions by Lagrange, Euler, Gauss, Hilbert, and von Neumann, among others (Liesen and Strakoš [Reference Liesen and Strakoš27, p. 8]). For instance, the linear algebra step in the Number Field Sieve, a well-known algorithm for large integer factorization, depends on Krylov subspace methods (Lenstra, Lenstra, Manasse and Pollard [Reference Lenstra, Lenstra, Manasse and Pollard26]). Another example is Wiedemann’s algorithm, which is employed to determine the minimal polynomials of large matrices over finite fields (Liesen and Strakoš [Reference Liesen and Strakoš27, p. 19]). The quantity $\psi _{k,\ell }(\Delta )$ plays a key role in evaluating the effectiveness of these algorithms, and determining bounds on this probability represents a challenging and crucial task in the field (Brent, Gao, and Lauder [Reference Brent, Gao and Lauder8, p. 277]). We give an explicit formula for this probability as a scalar product of the flag generating function $F_{\Delta }$ with a suitably defined symmetric function.

Theorem 7.1. For each matrix $\Delta \in {\mathrm M}_n({\mathbb F}_q)$ , we have $\psi _{k,\ell }(\Delta )=\langle F_\Delta (x),G(n,k,\ell )\rangle ,$ where

$$ \begin{align*} G(n,k,\ell)= q^{-nk}\sum_{\substack{\mu\vdash n \\ \ell(\mu)\leq \ell }} (-1)^{n-\mu_1}(q-1)^{\mu_1}q^{\sum_{j\geq 1}{\mu_j \choose 2}}{k \brack \mu_1}_q [\mu_1]_q! \widetilde{W}_{\mu}(x;q). \end{align*} $$

Proof. The number of tuples $(v_1,\ldots ,v_k)$ of vectors in ${\mathbb F}_q^n$ which span a fixed subspace of dimension m is given by

$$ \begin{align*} (q^k-1)(q^k-q)\cdots (q^k-q^{m-1})={k \brack m}_q(q-1)^mq^{m \choose 2}[m]_q!. \end{align*} $$

If W denotes the subspace spanned by $(v_1,\ldots ,v_k)$ , then $\mathrm {Kry}(\Delta ,\{v_1,\ldots ,v_k\},\ell )={\mathbb F}_q^n$ precisely when the $\Delta $ -profile of W is a partition of n with at most $\ell $ parts. It follows that

$$ \begin{align*} \psi_{k,\ell}(\Delta)&= q^{-nk}\sum_{m=0}^k {k \brack m}_q(q-1)^m q^{m \choose 2}[m]_q!\sum_{\substack{\mu\vdash n \\ \mu_1=m\\ \ell(\mu)\leq \ell }} \sigma(\mu,\Delta)\\ &=q^{-nk}\sum_{m=0}^k {k \brack m}_q(q-1)^m q^{m \choose 2}[m]_q!\sum_{\substack{\mu\vdash n \\ \mu_1=m\\ \ell(\mu)\leq \ell }} \epsilon_{\mu'}q^{\sum_{j\geq 2}{\mu_j \choose 2}}\langle F_\Delta(x),\widetilde{W}_{\mu}(x;q)\rangle, \end{align*} $$

by Theorem 4.3. Therefore, $\psi _{k,\ell }(\Delta )=\langle F_{\Delta },G(n,k,\ell )\rangle ,$ where

$$ \begin{align*} G(n,k,\ell)&=q^{-nk}\sum_{m=0}^k {k \brack m}_q(q-1)^m q^{m \choose 2}[m]_q!\sum_{\substack{\mu\vdash n \\ \mu_1=m\\ \ell(\mu)\leq \ell }} \epsilon_{\mu'}q^{\sum_{j\geq 2}{\mu_j \choose 2}}\widetilde{W}_{\mu}(x;q)\\ &=q^{-nk}\sum_{\substack{\mu\vdash n \\ \ell(\mu)\leq \ell }} (-1)^{n-\mu_1}(q-1)^{\mu_1}q^{\sum_{j\geq 1}{\mu_j \choose 2}}{k \brack \mu_1}_q [\mu_1]_q! \widetilde{W}_{\mu}(x;q).\\[-57pt] \end{align*} $$

8 Recent developments

Denote by $[n]$ the set of the first n positive integers. A Hessenberg function is a weakly increasing function ${\mathsf m}:[n]\to [n]$ satisfying ${\mathsf m}(i)\geq i$ for each $ i\in [n]$ . For a linear operator $\Delta $ on ${\mathbb F}_q^n,$ the Hessenberg variety is defined by

$$ \begin{align*} \mathscr{H}({\mathsf m},\Delta):= \{\text{complete flags } V_1\subseteq V_2\subseteq \cdots \subseteq V_n={\mathbb F}_q^n: \Delta V_i\subseteq V_{{\mathsf m}(i)}\text{ for } i\in [n]\}. \end{align*} $$

Drawing on results in this paper, the following theorem was proved in joint work with Abreu and Nigro [Reference Abreu, Nigro and Ram1].

Theorem 8.1. For each operator $\Delta $ on ${\mathbb F}_q^n$ , the number of ${\mathbb F}_q$ -rational points on the Hessenberg variety $\mathscr {H}({\mathsf m},\Delta )$ is given by

$$ \begin{align*}|\mathscr{H}({\mathsf m},\Delta)|=\langle F_\Delta(x), \omega X_{G({\mathsf m})}(x;q)\rangle, \end{align*} $$

where $X_{G({\mathsf m})}(x;t)$ denotes the chromatic quasisymmetric function of the unit interval graph $G({\mathsf m})$ associated to ${\mathsf m}$ .

This result entails an expression for the Poincaré polynomials of complex Hessenberg varieties involving modified Hall–Littlewood functions.