The Number of Solutions of X^{2} = 0 in Triangular Matrices Over GF (q)

Shalosh B. EKHAD^{1} and Doron ZEILBERGER^{1}

Abstract: We prove an explicit formula for the number of n × n upper triangular matrices, over GF (q), whose square is the zero matrix. This formula was recently conjectured by Sasha Kirillov and Anna Melnikov [KM].

Theorem. The number of n × n upper-triangular matrices over GF (q) (the finite field with q elements), whose square is the zero matrix, is given by the polynomial C_{n}(q), where,

C_{2n}(q) = ∑_{j} [\binom{2n}{n − 3j} − \binom{2n}{n − 3j − 1}] · q^{n^{2}−3j^{2}−j},

C_{2n+1}(q) = ∑_{j} [\binom{2n + 1}{n − 3j} − \binom{2n + 1}{n − 3j − 1}] · q^{n^{2}+n−3j^{2}−2j}.

Proof. In [K] it was shown that the quantity of interest is given by the polynomial A_{n}(q) = ∑_{r≥0} A_{n}^{r}(q), where the polynomials A_{n}^{r}(q) are defined recursively by

A_{n+1}^{r+1}(q) = q^{r+1} · A_{n}^{r+1}(q) + (q^{n−r} − q^{r}) · A_{n}^{r}(q) ; A_{n+1}^{0}(q) = 1.  (Sasha)

For any Laurent formal power series P (w), let CT_{w}P (w) denote the coefficient of w^{0}. Recall that the q-binomial coefficients are defined by

\binom{m}{n}_{q} := \frac{(1 − q^{m})(1 − q^{m−1}) ⋯ (1 − q^{m−n+1})}{(1 − q)(1 − q^{2}) ⋯ (1 − q^{n})} ,  (Carl)

whenever 0 ≤ n ≤ m, and 0 otherwise.

Lemma 1. We have

A_{n}^{r}(q) = CT_{w} [\frac{(1 − w)(1 + w)^{n}q^{r(n−r)}}{w^{r}} ∑_{i=0}^{∞}(−1)^{i}q^{−(i+1)i/2−i(n−2r)}\binom{i + n − 2r}{i}_{q}w^{i}] . (Anna)

Proof. Call the right side of Eq. (Anna), S_{n}^{r}(q). Since S_{n+1}^{0}(q) = 1, the lemma would follow by induction if we could show that

S_{n+1}^{r+1}(q) − q^{r+1} · S_{n}^{r+1}(q) − (q^{n−r} − q^{r}) · S_{n}^{r}(q) = 0 .  (Sasha′)

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. [ekhad,zeilberg]@math.temple.edu,

http://www.math.temple.edu/~[ekhad, zeilberg]   ftp://ftp.math.temple.edu/pub/[ekhad,zeilberg] .

Supported in part by the NSF. Nov. 28, 1995.

Using the linearity of CT_{w}, manipulating the series, using the definition (Carl) of the q−binomial coefficients, and simplifying, brings the left side of (Sasha′) to be CT_{w}Φ_{n}^{r}(q, w), where Φ_{n}^{r} is zero except when n is odd and r = (n − 1)/2, in which case it is a monomial in q times \frac{(1−w)(1+w)^{n}}{w^{r+1}} , and applying CT_{w} kills it all the same, thanks to the symmetry of the Chu-Pascal triangle.

Summing the expression proved for A_{n}^{r}(q), yields that

A_{n}(q) = CT_{w} [(1 − w)(1 + w)^{n} · ∑_{r=0}^{∞} ∑_{i=0}^{r}(−1)^{i}q^{r(n−r)−(i+1)i/2−i(n−2r)}\binom{i + n − 2r}{n − 2r}_{q}w^{i−r}] .

Letting l = r − i, and changing the order of summation, yields

A_{n}(q) = CT_{w} [(1 − w)(1 + w)^{n} · ∑_{ℓ=0}^{⌊n/2⌋} w^{−ℓ} · q^{ℓn−ℓ^{2}} ∑_{i=0}^{⌊(n−2ℓ)/2⌋}(−1)^{i}q^{i(i−1)/2}\binom{n − 2ℓ − i}{i}_{q}] .

(SumAnna)

Luckily, the inner sum evaluates nicely thanks to the following.

Lemma 2. We have

∑_{i=0}^{⌊m/2⌋}(−1)^{i}q^{i(i−1)/2}\binom{m − i}{i}_{q} = (−1)^{⌊m/3⌋}q^{m(m−1)/6} · χ(m ≢ 2 mod 3) ,

where χ(⋯) is the truth value (=1 or 0) of the proposition “⋯”.

Proof. While this is unlikely to be new^{2}, it is also irrelevant whether or not it is new, since such things are now routine, thanks to the package qEKHAD, accompanying [PWZ]. Let’s call the left side divided by q^{m(m−1)/6}, Z(m). Then we have to prove that Z_{0}(m) := Z(3m) equals (−1)^{m}, Z_{1}(m) := Z(3m + 1) equals (−1)^{m}, and Z_{2}(m) := Z(3m + 2) equals 0. It is directly verified that these are true for m = 0, 1, and the general result follows from the second order recurrences produced by qEKHAD. The input files inZ0, inZ1, inZ2 as well as the corresponding output files, outZ0, outZ1,

outZ2 can be obtained by anonymous ftp to ftp.math.temple.edu, directory pub/ekhad/sasha.
The package qEKHAD can be downloaded from http://www.math.temple.edu/~zeilberg.

To complete the proof of the theorem, we use lemma 2 to evaluate the inner sum of (SumAnna), then to get A_{2n}(q), we replace n by 2n, and then replace l by l + n, and finally use the binomial theorem. Similarly for A_{2n+1}(q).

References

[K] A.A. Kirillov, On the number of solutions to the equation X^{2} = 0 in triangular matrices over a finite field, Funct. Anal. and Appl. 29 (1995), no. 1.

[KM] A.A. Kirillov and A. Melnikov, On a remarkable sequence of polynomials, preprint.

[PWZ] M. Petkovšek, H.S. Wilf, and D. Zeilberger, “A = B”, A.K.Peters, 1996.

2 For a ‘classical’ proof, see Christian Krattenthaler’s message, at ftp://ftp.math.temple.edu/pub/ekhad/sasha.