Matrix counting over finite fields

Submitted by Joel Brewster Lewis

Let ${r \leq m \leq n}$ be positive integers, and ${q}$ a prime power. Given a subset ${S}$ of the discrete grid ${\{1, \ldots, m\} \times \{1, \ldots, n\}}$ , one may define the matrix count ${m_r(S; q)}$ to be the number of rank- ${r}$ matrices over the finite field of order ${q}$ whose entries on ${S}$ are equal to ${0}$ . This question concerns the properties of this matrix count as a function of ${q}$ .

A first basic property is that the integer ${m_r(S; q)}$ is always divisible by ${(q - 1)^r}$ . (The idea of the proof is to consider the orbits formed when rescaling the rows by nonzero factors.) Consequently, it is convenient to define the reduced (or projective) matrix count ${M_r(S; q) := \frac{m_r(S; q)}{(q - 1)^r}}$ .

One motivation for the study of the matrix counts comes from the classical enumerative combinatorics of rook theory: the rook number ${R_r(S)}$ is the number of placements of ${r}$ nonattacking rooks on ${\{1, \ldots, m\} \times \{1, \ldots, n\}}$ so that none of them lies on ${S}$ . (Two rooks are attacking if they lie in the same row or same column, so this may equivalently be described as the number of ${m \times n}$ partial permutation matrices whose support is disjoint from ${S}$ .) Then for any prime power ${q}$ one has

$\displaystyle M_r(S; q) \equiv R_r(S) \pmod{q - 1},$

(see [4, Prop 5.1]) and so one may think of ${M_r(S; q)}$ as a ${q}$ -analogue of the rook number ${R_r(S)}$ .

Depending on the diagram ${S}$ , the reduced rook count may be more or less nice as a function of ${q}$ . When ${S}$ is a Ferrers board (i.e., the diagram of an integer partition), Haglund [2, Thm 1] showed that the function ${M_r(S; q)}$ is actually a polynomial in ${q}$ , with positive integer coefficients, and related to the ${q}$ -rook number of Garsia and Remmel [1]. However, when ${S}$ is arbitrary, the function ${M_r(S; q)}$ need not be a polynomial function of ${q}$ [7, Section 8.1], and in fact may be exceptionally complicated. It is natural to explore this boundary: which diagrams ${S}$ give “nice” counting functions ${M_r(S; q)}$ ?

One natural way to extend Ferrers boards is to skew shapes, the set difference of two Ferrers boards. In fact, both are special cases of inversion diagrams of permutations (appearing in the literature under many names, including Rothe diagram): given a permutation ${w = w_1w_2 \cdots w_n}$ in one-line notation, the inversion diagram contains the box ${(i, w_j)}$ whenever ${i < j}$ and ${w_j < w_i}$ . Then any Ferrers board ${S}$ is (for some sufficiently large ${n}$ ) the inversion diagram of some ${n}$ -permutation, and the ${n}$ -permutations whose inversion diagrams are Ferrers boards are exactly those that avoid the permutation pattern ${132}$ , i.e., those for which there do not exist ${i < j < k}$ with ${w_i < w_k < w_j}$ . Similarly, every skew shape is (after rearranging rows and columns; for some sufficiently large ${n}$ ) the inversion diagram of a ${321}$ -avoiding permutation. In [6, Cor. 4.6], it was shown that for any permutation ${w}$ with inversion diagram ${I_w}$ , the matrix count ${M_r(I_w; q)}$ is a polynomial function of ${q}$ with integer coefficients; but there exist permutations for which some of the coefficients are negative.

OPAC-011. Prove that if ${w}$ is a ${321}$ -avoiding permutation, then the matrix count ${M_r(I_w; q)}$ is a polynomial in ${q}$ with nonnegative integer coefficients.

This is essentially Conjecture 6.9 of [6]. It has been checked for all ${321}$ -avoiding permutations of size ${14}$ or less.

One particular special case is worth mentioning. When ${n}$ is even, the permutation ${w = 214365 \cdots n(n - 1)}$ avoids ${321}$ ; its diagram consists of exactly ${n/2}$ of the ${n}$ diagonal boxes in ${\{1, \ldots, n\} \times \{1, \ldots, n\}}$ . In this case, we have an explicit formula for ${M_n(I_w; q)}$ : define the standard ${q}$ -number ${[n]_q := 1 + q + \ldots + q^{n - 1}}$ and ${q}$ -factorial ${[n]!_q := [1]_q \cdot [2]_q \cdots [n]_q}$ ; then one has ${M_n(I_w; q) = q^K \sum_{i = 0}^n (-1)^i \binom{n}{i} [2n - i]!_q}$ for some integer ${K}$ [6, Section 6.3].

OPAC-012. The sum ${\sum_{i = 0}^n (-1)^i \binom{n}{i} [2n - i]!_q}$ is manifestly a polynomial with integer coefficients; prove that in fact the coefficients are nonnegative integers.

OPAC-012 is essentially Conjecture 6.8 of [6]. It is easy to verify on a computer for ${n \leq 40}$ . Ideally, one would hope for a solution method that could be applied to other cases of OPAC-011, as well.

For more open questions along these lines, see [3] and [5].

References:

[1] A.M. Garsia, and J.B. Remmel, ${q}$ -counting rook configurations and a formula of Frobenius. J. Combin. Theory (A) 41 (1986), 246–275. DOI: 10.1016/0097-3165(86)90083-X

[2] J. Haglund, ${q}$ -rook polynomials and matrices over finite fields. Adv. in Appl. Math. 20 (1998), no. 4, 450–487. DOI: 10.1006/aama.1998.0582

[3] A.J. Klein, J.B. Lewis, and A.H. Morales, Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams. J. Algebraic Combin. 39 (2014), no. 2, 429–456. DOI: 10.1007/s10801-013-0453-x

[4] J.B. Lewis, R.I. Liu, A.H. Morales, G. Panova, S.V. Sam, and Y.X Zhang, Matrices with restricted entries and ${q}$ -analogues of permutations. J. Comb. 2 (2011), no. 3, 355–395. DOI: 10.4310/JOC.2011.v2.n3.a2

[5] J.B. Lewis, and A.H. Morales, Combinatorics of diagrams of permutations. J. Combin. Theory Ser. A 137 (2016), 273–306. DOI: 10.1016/j.jcta.2015.09.004

[6] J.B. Lewis, and A.H. Morales, Rook theory of the finite general linear group. Exper. Math., forthcoming (2018). DOI: 10.1080/10586458.2018.1470045

[7] J.R. Stembridge, Counting points on varieties over finite fields related to a conjecture of Kontsevich. Ann. Comb. 2 (1998), no. 4, 365–385. DOI: 10.1007/BF01608531

Share this:

Related

Leave a comment Cancel reply