RELATIVELY PRIME POLYNOMIALS AND NONSINGULAR HANKEL MATRICES OVER FINITE FIELDS

MARIO GARCÍA-ARMAS, SUDHIR R. GHORPADE, AND SAMRITH RAM

Abstract. The probability for two monic polynomials of a positive degree n with coefficients in the finite field 𝔽_{q} to be relatively prime turns out to be identical with the probability for an n × n Hankel matrix over 𝔽_{q} to be nonsingular. Motivated by this, we give an explicit map from pairs of coprime polynomials to nonsingular Hankel matrices that explains this connection. A basic tool used here is the classical notion of Bezoutian of two polynomials. Moreover, we give simpler and direct proofs of the general formulae for the number of m-tuples of relatively prime polynomials over 𝔽_{q} of given degrees and for the number of n × n Hankel matrices over 𝔽_{q} of a given rank.

1. Introduction

It is a remarkable fact that the probability for two randomly chosen monic polynomials of the same positive degree with coefficients in the binary field 𝔽_{2} to be coprime is exactly 1/2. This observation appears to go back at least to an exercise in the treatise, first published in 1969, of Knuth [9, §4.6.1, Ex. 5] (see also Remark 4.2). More recently, it was made by Corteel, Savage, Wilf, and Zeilberger [2] in 1998 in the course of their work on Euler’s pentagonal sieve in the theory of partitions, and it led them to ask for a “nice simple bijection” between the coprime and the non-coprime ordered pairs of monic polynomials of degree n over 𝔽_{2}. This was answered first by Reifegerste [12] in 2000 and by Benjamin and Bennett [1] in 2007. The latter deals with the more general case of polynomials over any finite field 𝔽_{q} where the probability turns out to be 1 − (1/q) instead of 1/2. Since there are q^{2n} ordered pairs of monic polynomials over 𝔽_{q} of degree n, this means that

(1)  |CPP_{n}(𝔽_{q})| = q^{2n} − q^{2n−1} = q^{2n−1}(q − 1),

where CPP_{n}(𝔽_{q}) denotes the set of ordered pairs of coprime monic polynomials over 𝔽_{q} of degree n. In effect, Benjamin and Bennett gave an explicit surjective map from CPP_{n}(𝔽_{q}) onto the set of ordered pairs of non-coprime monic polynomials over 𝔽_{q} of degree n in such a way that the cardinality of each fiber is q − 1.

A couple of years prior to [2] and working on a seemingly unrelated topic, Kaltofen and Lobo [8] observed that the probability for a n × n Toeplitz matrix with entries in 𝔽_{q} to be nonsingular is exactly 1 − (1/q). In fact, this observation can be traced back to Daykin [3] who had essentially proved the same result (and also a more general one) in 1960 with Hankel matrices in place of Toeplitz matrices. Since there are q^{2n−1} Toeplitz matrices (or equivalently, Hankel matrices) of size n × n with entries in 𝔽_{q}, this means that

Date: September 7, 2010.

2000 Mathematics Subject Classification. 11T06, 11T35, 15B05.

Key words and phrases. Finite field, relatively prime polynomials, Toeplitz matrix, Hankel matrix, Bezoutian.

(2)  |TGL_{n}(𝔽_{q})| = |HGL_{n}(𝔽_{q})| = q^{2n−1} − q^{2n−2} = q^{2n−2}(q − 1),

where TGL_{n}(𝔽_{q}) (resp: HGL_{n}(𝔽_{q})) denotes the set of all n×n nonsingular Toeplitz (resp: Hankel) matrices with entries in 𝔽_{q}.

One of the main aims of this paper is to explain the uncanny coincidence that the probability in both of the above situations turns out to be the same or, more precisely, the fact that the formulae (1) and (2) differ just by a factor of q. We do this by giving an explicit surjective map from CPP_{n}(𝔽_{q}) onto HGL_{n}(𝔽_{q}) such that each fiber has cardinality q. This readily yields a similar map with HGL_{n}(𝔽_{q}) replaced by TGL_{n}(𝔽_{q}). As a consequence, we obtain new proofs of (1) and (2) by combining any one of the known proofs with this surjective map. We further add to this collection of proofs by giving alternative, short and completely self-contained proofs of more general versions of (1) and (2).

2. Preliminaries

Let F be a field. Recall that a matrix M = (m_{ij}) with entries in F is said to be a Toeplitz matrix (resp: Hankel matrix) if m_{ij} = m_{rs} whenever i − j = r − s (resp: i + j = r + s). Thus every n × n Toeplitz (resp: Hankel) matrix over F looks like (a_{n+i−j}) (resp: (a_{i+j−1})) for a unique (2n − 1)-tuple (a_{1}, …, a_{2n−1}) ∈ F^{2n−1}.

We denote by T_{n}(F) (resp: H_{n}(F)) the set of all Toeplitz (resp: Hankel) matrices with entries in F and, as in the Introduction, set

TGL_{n}(F) = T_{n}(F) ∩ GL_{n}(F) and HGL_{n}(F) = H_{n}(F) ∩ GL_{n}(F).

The following simple observation shows that at least as far as enumerative and bijective combinatorics is concerned, Toeplitz and Hankel matrices are the same.

Proposition 2.1. There is a bijection between T_{n}(F) and H_{n}(F), which induces a bijection between TGL_{n}(F) and HGL_{n}(F).

Proof. Let E be the n × n matrix with 1 on the antidiagonal and 0 elsewhere, i.e., E = (δ_{i,n−j+1}) where δ is the Kronecker delta. Then E is nonsingular and the map given by A ↦ AE sets up the desired bijection. □

As usual, F [X] will denote the set of polynomials in one variable X with coefficients in F. Recall that for any u, v ∈ F [X] of degree ≤ n, the nth order Bezoutian (matrix) of u and v is the n×n matrix B_{n}(u, v) = (b_{ij}) determined by the equation

\frac{u(X)v(Y) − v(X)u(Y)}{X − Y} = ∑_{i,j=1}^{n} b_{ij}X^{i−1}Y^{j−1}.

The coefficients b_{ij} are not hard to determine explicitly; in fact, if u = ∑_{i=0}^{n} u_{i}X^{i} and v = ∑_{i=0}^{n} v_{i}X^{i}, then upon letting u_{k} = v_{k} := 0 for k > n, we have

b_{ij} = ∑_{s=1}^{min{i,j}} (v_{s−1}u_{i+j−s} − u_{s−1}v_{i+j−s}) for 1 ≤ i, j ≤ n.

It is clear from the definition that if u and v have a nonconstant common factor then the system of homogeneous linear equations corresponding to B_{n}(u, v) has a nontrivial solution, and hence B_{n}(u, v) is singular. It is a classical fact that the converse is also true; we record this below for convenience and refer to the survey article [5] of Helmke and Fuhrmann for a proof.

Proposition 2.2. Let u, v ∈ F [X]. Assume that deg u = n and deg v ≤ n. Then B_{n}(u, v) is nonsingular if and only if u and v are coprime.

As an illustration, consider u, v ∈ F [X] such that v is the constant polynomial 1 and u(X) = u_{0} + u_{1}X + ⋯ + u_{n}X^{n} with u_{0}, u_{1}, …, u_{n} ∈ F. Then

\frac{u(X) − u(Y)}{X − Y} = ∑_{k=1}^{n} u_{k} \frac{X^{k} − Y^{k}}{X − Y} = ∑_{k=1}^{n} u_{k} ∑_{i=1}^{k} X^{i−1} Y^{k−i} = ∑_{i,j=1}^{n} u_{i+j−1}X^{i−1} Y^{j−1},

where, by convention, u_{k} := 0 for k > n. Thus the nth order Bezoutian B_{n}(u, 1) has u_{n} on its antidiagonal and 0 below that. In particular, if deg u = n, i.e., if u_{n} ≠ 0, then u and v are coprime, and moreover B_{n}(u, v) is nonsingular.

3. An Explicit Surjection

Fix a positive integer n and a field F. As in the Introduction, let

CPP_{n}(F) := {(f, g) ∈ F [X]^{2} : f, g are coprime and both are monic of degree n} .

Moreover, let us consider

P_{n}(F) := {(u, v) ∈ F [X]^{2} : u is monic, deg u = n, and deg v < n} , and
HP_{n}(F) := {(u, v) ∈ P_{n}(F) : u and v are coprime} .

We may refer to an element of P_{n}(F) as a Padé pair and an element of HP_{n}(F) as a Hermite pair.

Lemma 3.1. CPP_{n}(F) is in bijection with HP_{n}(F).

Proof. The map given by (f, g) ↦ (f, g − f) does the job. □

Lemma 3.2. Let (u, v) ∈ P_{n}(F). Then there are unique a_{i} ∈ F, i ≥ 1, such that

(3)  \frac{v(X)}{u(X)} = ∑_{i=1}^{∞} \frac{a_{i}}{X^{i}} .

Proof. Write u(X) = X^{n} [1 − u^{∗}(1/X)] for a unique u^{∗} ∈ F [X] with no constant term. Expanding as a formal power series, we obtain

\frac{v(X)}{u(X)} = X^{−n}v(X) ∑_{j=0}^{∞} u^{∗}(1/X)^{j}.

This yields the desired a_{i} ∈ F. □

Definition 3.3. For (u, v) ∈ P_{n}(F), we define H_{n}(u, v) to be the n × n Hankel matrix whose (i, j)th entry is a_{i+j−1} for 1 ≤ i, j ≤ n, where a_{1}, a_{2}, … are as in (3).

The following result which relates H_{n}(u, v) to the nth order Bezoutian B_{n}(u, v) is classical and is sometimes referred to as Barnett’s factorization. We include a proof for the sake of completeness, especially since the proofs found in the literature are often a bit involved and tend have an additional assumption that the polynomials u and v are coprime, i.e., (u, v) is a Hermite pair rather than a Padé pair.

Proposition 3.4. B_{n}(u, v) = B_{n}(u, 1)H_{n}(u, v)B_{n}(u, 1) for any (u, v) ∈ P_{n}(F).

Proof. Let R(T) := v(T)/u(T) and let a_{i}, i ≥ 1, be as in (3). Then

\frac{R(Y) − R(X)}{X − Y} = ∑_{i=1}^{∞} a_{i} ∑_{j=1}^{i} \frac{X^{i−j} Y^{j−1}}{X^{i}Y^{i}} = ∑_{k,ℓ=1}^{∞} a_{k+ℓ−1}X^{−k} Y^{−ℓ}.

Now if u(X) = u_{0} + ⋯ + u_{n−1}X^{n−1} + X^{n} with u_{0}, …, u_{n−1} ∈ F and u_{n} := 1, then

\frac{u(X)v(Y) − v(X)u(Y)}{X − Y} = u(X)\frac{R(Y) − R(X)}{X − Y}u(Y)

= ( ∑_{r=0}^{n} u_{r}X^{r})( ∑_{k,ℓ=1}^{∞} a_{k+ℓ−1}X^{−k}Y^{−ℓ})( ∑_{s=0}^{n} u_{s}Y^{s})

= ∑_{i,j≤n} ( ∑_{k,ℓ≥1} u_{i+k−1} a_{k+ℓ−1} u_{ℓ+j−1})X^{i−1}Y^{j−1},

where, by convention, u_{t} = 0 for t > n and a_{t} = 0 for t ≤ 0. Comparing the coefficients of X^{i−1}Y^{j−1} for 1 ≤ i, j ≤ n, we obtain the desired result. □

Theorem 3.5. There is a surjective map σ : CPP_{n}(F) → TGL_{n}(F) such that for any A ∈ TGL_{n}(F), the fiber σ^{−1} ({A}) is in one-to-one correspondence with F. In particular, |CPP_{n}(𝔽_{q})| = q |TGL_{n}(𝔽_{q})| .

Proof. From Propositions 2.2 and 3.4, we see that H_{n}(u, v) is nonsingular for any (u, v) ∈ HP_{n}(F). Thus, we obtain a well-defined map η : HP_{n}(F) → HGL_{n}(F) given by (u, v) ↦ H_{n}(u, v). Now let B ∈ HGL_{n}(F). Then there are unique b_{1}, …, b_{2n−1} ∈ F such that the (i, j)th entry of B is b_{i+j−1} for 1 ≤ i, j ≤ n. Let λ be an arbitrary element of F and set b_{2n} := λ. Since B is nonsingular, there are unique u_{0}, …, u_{n−1} ∈ F such that

(4)  B ( u_{0} ; u_{1} ; ⋮ ; u_{n−1}) = − (b_{n+1} ; b_{n+2} ; ⋮ ; b_{2n}) .

Next, define u_{n} := 1 and v_{0}, v_{1}, …, v_{n−1} to be the unique elements of F given by the following triangular system of equations:

(5)  ( v_{0} ; v_{1} ; ⋮ ; v_{n−1}) = (\begin{matrix}b_{1} & b_{2} & … & b_{n} \\ 0 & b_{1} & … & b_{n−1} \\ ⋮ & & ... & ⋮ \\ 0 & 0 & … & b_{1} \end{matrix}) (u_{1} ; u_{2} ; ⋮ ; u_{n}) .

Finally, define u, v ∈ F [X] by

u = ∑_{i=0}^{n} u_{i}X^{i} and v = ∑_{i=0}^{n−1} v_{i}X^{i}.

Then (u, v) ∈ P_{n}(F) and if we let a_{k} ∈ F, k ≥ 1, as in (3), then we have

∑_{i=1}^{n} v_{i−1}X^{i−1} = ( ∑_{j=0}^{n} u_{j}X^{j})( ∑_{k≥1} a_{k}X^{−k}) = ∑_{i≤n} ( ∑_{j=0}^{n} a_{j−i+1}u_{j})X^{i−1},

where, by convention, a_{k} := 0 for k ≤ 0. Comparing the coefficients of X^{i−1} for −n < i ≤ n, we find that (5) and (4) are satisfied with b_{1}, …, b_{2n} replaced by a_{1}, …, a_{2n}, respectively. Since u_{n} = 1, the triangular nature of (5) implies that a_{i} = b_{i} for 1 ≤ i ≤ n. Further, successive comparison of (4) with its counterpart where b_{i}’s are replaced by a_{i}’s yields a_{i} = b_{i} for 1 ≤ i ≤ 2n. In particular, B = H_{n}(u, v). Now since B is nonsingular, Propositions 3.4 and 2.2 show that u and v are coprime. Thus (u, v) ∈ HP_{n}(F) and η(u, v) = B. It is clear from the construction above that a Hermite pair (u, v) satisfying η(u, v) = B is uniquely determined by the matrix B and the element b_{2n} = λ. Also, in view of (4), distinct values of λ in F give rise to distinct monic polynomials u in F [X] of degree n. This shows that for each B ∈ HGL_{n}(F), the fiber η^{−1} ({B}) is in one-to-one correspondence with F. Finally, combining η with the bijections given by Proposition 2.1 and Lemma 3.1, we obtain the desired surjective map σ : CPP_{n}(F) → TGL_{n}(F). □

4. Relatively Prime Polynomials

The general version of (1) alluded to in the Introduction is the theorem stated below. It may be noted that this generalizes [2, Prop. 3], [11, Thm. 9] and [10, Prop. 2.4], and also that it is a more precise form of [1, Cor. 5] and [6, Thm. 1.1]. We remark at the outset that in this theorem, considering arbitrary polynomials (not necessarily monic) in 𝔽_{q}[X] does not affect the probability.

Theorem 4.1. Let m be a positive integer and n_{1}, …, n_{m} be nonnegative integers. The probability that m monic polynomials in 𝔽_{q}[X] of degrees n_{1}, …, n_{m}, chosen independently and uniformly at random, are relatively prime is 1 − q^{1−m} if min{n_{1}, …, n_{m}} ≥ 1 and 1 otherwise.

Proof. Let N(n_{1}, …, n_{m}) denote the number of ordered m-tuples (f_{1}, …, f_{m}) of coprime monic polynomials in 𝔽_{q}[X] such that deg f_{i} = n_{i} for i = 1, …, m. Evidently, it suffices to show that

(6) N(n_{1}, …, n_{m}) = \begin{cases}q^{n_{1}+···+n_{m}} (1 − q^{1−m}) & if min\{n_{1}, n_{2}, …, n_{m}\} ≥ 1, \\ q^{n_{1}+···+n_{m}} & if min\{n_{1}, n_{2}, …, n_{m}\} = 0. \end{cases}

To this end, we shall assume, without loss of generality, that n_{1} ≥ ⋯ ≥ n_{m}. We can partition the set of ordered m-tuples (f_{1}, …, f_{m}) of monic polynomials in 𝔽_{q}[X] with deg f_{i} = n_{i} for i ≤ i ≤ m, into disjoint subsets S_{0}, S_{1}, …, S_{n_{m}}, where for 0 ≤ d ≤ n_{m}, the set S_{d} consists of m-tuples whose GCD is of degree d. Given any monic polynomial h ∈ 𝔽_{q}[X] of degree d and any coprime m-tuple (g_{1}, …, g_{m}) of monic polynomials such that deg g_{i} = n_{i} − d for i = 1, …, m, it is easy to see that (hg_{1}, …, hg_{m}) ∈ S_{d}. Conversely, if (f_{1}, …, f_{m}) ∈ S_{d}, then the polynomial h = GCD(f_{1}, …, f_{m}) is monic of degree d and (f_{1}/h, …, f_{m}/h) is an ordered mtuple of coprime monic polynomials of degrees n_{1} −d, …, n_{m} −d, respectively. This shows that |S_{d}| = q^{d}N(n_{1} − d, …, n_{m} − d) for 0 ≤ d ≤ n_{m}, and consequently,

(7)  q^{n_{1}+···+n_{m}} = ∑_{d=0}^{n_{m}} |S_{d}| = ∑_{d=0}^{n_{m}} q^{d}N(n_{1} − d, n_{2} − d, …, n_{m} − d).

If n_{m} = 0, we immediately obtain N(n_{1}, …, n_{m}) = q^{n_{1}+···+n_{m}}. On the other hand, if n_{m} ≥ 1, substituting n_{i} by n_{i} − 1 (i = 1, …, m) in the above relation yields

(8)  q^{n_{1}+···+n_{m}−m} = ∑_{d=1}^{n_{m}} q^{d−1}N(n_{1} − d, n_{2} − d, …, n_{m} − d).

Multiplying equation (8) by q and subtracting the result from (7), we obtain N(n_{1}, n_{2}, …, n_{m}) = q^{n_{1}+···+n_{m}} (1 − q^{1−m}), as desired. □

Remark 4.2. As indicated in the Introduction, the case m = 2 (and q prime) of the above result appears as an exercise (# 5 of §4.6.1) in Knuth [9]. The solution outlined by Knuth uses the result obtained in the previous exercise and in turn, a deep analysis of the euclidean algorithm. The general result with arbitrary m and q (but with n_{1} = ⋯ = n_{m} = n) given in Corteel, Savage, Wilf and Zeilberger [2] seems to have been arrived at independently by completely different means. Also, it is indicated in a footnote in [2, p.188] that the degrees n_{1}, …, n_{m} could well be different (i.e., one has a result such as Theorem 4.1 above), and this observation is ascribed to D. Zagier. Many of the subsequent works (e.g. [1, 6, 4, 12]) cite [2] as an earliest reference for this result (and in fact, the authors of this paper did the same before it was pointed out by a referee that the result is classical). In retrospect, the key ideas in the answer by Benjamin and Bennett [1] to the question in [2] about a nice bijective proof can be traced back to [9, §4.6] and a more detailed analysis by Norton [11] as well as by Ma and van zur Gathen [10]. In the same vein, the short proof given above of Theorem 4.1, even though it was discovered independently, can be viewed as an extension of the “alternative proof” that appears in the solution of Exercise 5 of §4.6.1 in the first edition of Knuth [9], but for some mysterious reason, is missing in the subsequent editions. Thus, the contents of this section may help resurrect an original and perhaps the simplest proof. Finally, we remark that nontrivial generalizations of Theorem 4.1 are studied by Gao and Panario [4] and by Hou and Mullen [6], while an application to a conjecture about the enumeration of certain Singer cycles is discussed in [7].

5. Hankel Matrices over 𝔽_{q}

The general version of (2) alluded to in the Introduction is the following.

Theorem 5.1. The number N(n, r; q) of n × n Hankel matrices of rank r with entries in the finite field 𝔽_{q} is given by

(9)  N(n, r; q) = \begin{cases}1 & if r = 0, \\ q^{2r−2}(q^{2} − 1) & if 1 ≤ r ≤ n − 1, \\ q^{2n−2}(q − 1) & if r = n. \end{cases}

Before giving a proof of the above theorem, we introduce some notation and prove a few auxiliary results. Let F be a field and, as before, n a positive integer. Given any n × n matrix A with entries in F and any positive integers d, i_{1}, …, i_{d}, j_{1}, …, j_{d} such that i_{1} < ⋯ < i_{d} ≤ n and j_{1} < ⋯ < j_{d} ≤ n, we denote by A[i_{1}, …, i_{d}|j_{1}, …, j_{d}] the d × d submatrix of A formed by the rows indexed by i_{1}, …, i_{d} and the columns indexed by j_{1}, …, j_{d}. Note that the d^{th} leading principal submatrix of A is A[1, …, d|1, …, d] and this will be denoted simply by A_{d}. Define

δ(A) := \begin{cases}0 & if A_{d} is singular for each d = 1, …, n, \\ max\{d : A_{d} is nonsingular\} & otherwise. \end{cases}

For r, k ∈ {0, 1, …, n}, let H_{n}(r, F) := {A ∈ H_{n}(F) : rank(A) ≤ r}, and moreover,

H_{n}^{(k)}(F) := {A ∈ H_{n}(F) : δ(A) = k} and H_{n}^{(k)}(r, F) := H_{n}(r, F) ∩ H_{n}^{(k)}(F).

Note that HGL_{n}(F) = H_{n}^{(n)}(F) = H_{n}^{(n)}(n, F) and also that

(10)  H_{n}(F) = ∐_{k=0}^{n} H_{n}^{(k)}(F) and H_{n}(r, F) = ∐_{k=0}^{r} H_{n}^{(k)}(r, F),

where ∐ denotes disjoint union. The main idea in the proof of Theorem 5.1 is to use the above decompositions and to characterize H_{n}^{(k)}(𝔽_{q}) and H_{n}^{(k)}(r, 𝔽_{q}) suitably so as to be able to determine their cardinalities recursively. Here is the first step.

Lemma 5.2. Let A = (a_{i+j−1}) ∈ H_{n}(F). Then

(11)  A ∈ H_{n}^{(0)}(F) ⟺ a_{1} = ⋯ = a_{n} = 0.

Moreover, for 0 ≤ r ≤ n − 1,

(12)  A ∈ H_{n}^{(0)}(r, F) ⟺ a_{1} = ⋯ = a_{2n−r−1} = 0.

In particular, |H_{n}^{(0)}(𝔽_{q})| = q^{n−1} and |H_{n}^{(0)}(r, 𝔽_{q})| = q^{r}.

Proof. If A ∈ H_{n}^{(0)}(F), then det(A_{k}) = 0 for k = 1, …, n. Using this successively, we obtain a_{1} = ⋯ = a_{n} = 0. Conversely, if a_{1} = ⋯ = a_{n} = 0, then it is clear that det(A_{k}) = 0 for k = 1, …, n, i.e., A ∈ H_{n}^{(0)}(F). Next, let 0 ≤ r ≤ n−1 and suppose A ∈ H_{n}^{(0)}(r, F). Then a_{1} = ⋯ = a_{n} = 0, as before. Moreover, by successively using the vanishing of the (r+1)×(r+1) minor det A[n−r, n−r+1, …, n|j, j+1, …, j+r] for j = 2, …, n − r, we obtain a_{n+1} = ⋯ = a_{2n−r−1} = 0 as well. Conversely, suppose a_{1} = ⋯ = a_{2n−r−1} = 0, then A ∈ H_{n}^{(0)}(F) and it is easily seen that every (r + 1) × (r + 1) submatrix of A has a column of zeros, and so A ∈ H_{n}^{(0)}(r, F). □

The following result is an analogue of (11) for H_{n}^{(k)}(F) where k ≥ 1.

Lemma 5.3. Let k ∈ {1, …, n − 1} and A = (a_{i+j−1}) ∈ H_{n}(F) be such that A_{k} is nonsingular. Suppose x = (x_{1}, …, x_{k}) ∈ F^{k} is the unique solution of the system A_{k}x^{T} = (a_{k+1}, …, a_{2k})^{T}, i.e., for t = 1, …, k, the following relation holds:

(13)  a_{k+t} = x_{1}a_{t} + ⋯ + x_{k}a_{t+k−1}.

Then

(14)  A ∈ H_{n}^{(k)}(F) ⟺ the relation (13) holds for t = 1, …, n.

Proof. Suppose A ∈ H_{n}^{(k)}(F). We will use induction on t to show that (13) holds for t = 1, …, n. The case when 1 ≤ t ≤ k is known by the hypothesis. So let us assume that t ≥ k + 1 and that (13) holds for all values of t smaller than given one. Consider the t × t matrix A_{t} and successively make the following t − k elementary column transformations:

C_{t} − (x_{1}C_{t−k} + ⋯ + x_{k}C_{t−1}) , …, C_{k+1} − (x_{1}C_{1} + ⋯ + x_{k}C_{k})

where C_{j} indicates the j^{th} column. This transforms A_{t} to the t × t matrix

A′ = ( \begin{matrix}a_{1} & ⋯ & a_{k} & h_{1} & ⋯ & h_{t−k} \\ ⋮ & ... & ⋮ & ⋮ & & ⋮ \\ a_{k} & ⋯ & a_{2k−1} & h_{k} & ⋯ & h_{t−1} \\ a_{k+1} & ⋯ & a_{2k} & h_{k+1} & ⋯ & h_{t} \\ ⋮ & & ⋮ & ⋮ & ... & ⋮ \\ a_{t} & ⋯ & a_{k+t−1} & h_{t} & ⋯ & h_{2t−k−1} \end{matrix} ) ,

where h_{m} = a_{k+m} −(x_{1}a_{m} +⋯+x_{k}a_{m+k−1}) for m = 1, … 2t−k −1. By induction hypothesis, h_{m} = 0 for m = 1, …, t − 1, and therefore

det(A_{t}) = det(A′) = (−1)^{(t−k)(t−k+1)/2} det(A_{k})h_{t}^{t−k}.

Since det(A_{t}) = 0 and det(A_{k}) ≠ 0, it follows that h_{t} = 0, i.e., the relation (13) holds for the given value of t.

Conversely, suppose the relation (13) holds for t = 1, …, n. Then we can write v_{k+1} = x_{1}v_{1} + ⋯ + x_{k}v_{k}, where v_{j} denotes the j^{th} column vector of A. In particular, rank(A_{k+1}) ≤ k, which implies that A ∈ H_{n}^{(k)}(F). □

Let us pause to observe that the formula (2) for the number of nonsingular Hankel matrices can already be derived as a consequence of the above results.

Corollary 5.4. |H_{n}^{(0)}(𝔽_{q})| = q^{n−1} and |H_{n}^{(k)}(𝔽_{q})| = q^{n+k−2}(q − 1) for 1 ≤ k ≤ n. In particular, |HGL_{n}(𝔽_{q})| = q^{2n−2}(q − 1).

Proof. Induct on n. If n = 1, then k is 0 or 1, and the desired formulae are obvious. Suppose n > 1 and the result holds for positive values of n smaller than the given one. By Lemma 5.2, |H_{n}^{(0)}(𝔽_{q})| = q^{n−1}. Now suppose 1 ≤ k < n. Then by Lemma 5.3, we see that the map A = (a_{i+j−1}) ↦ (A_{k}, a_{2k}, a_{n+k+1}, …, a_{2n−1}) gives a bijection of H_{n}^{(k)}(F) onto H_{k}^{(k)}(F) × F^{n−k}. Hence using the induction hypothesis, |H_{n}^{(k)}(𝔽_{q})| = q^{2k−2}(q − 1)q^{n−k} = q^{n+k−2}(q − 1). Finally, in view of (10), the induction hypothesis, and an easy evaluation of a telescopic sum, we conclude that |HGL_{n}(𝔽_{q})| = |H_{n}^{(n)}(𝔽_{q})| = |H_{n}(𝔽_{q})| − ∑_{k=0}^{n−1} |H_{n}^{(k)}(𝔽_{q})| = q^{2n−1} − q^{2n−2}. □

If a Hankel matrix in H_{n}^{(k)}(F) satisfies a rank condition, the validity of (13) can be pushed a little further. More precisely, one has the following analogue of (12).

Lemma 5.5. Let k, r be integers with 1 ≤ k ≤ r < n and A = (a_{i+j−1}) ∈ H_{n}(F) be such that A_{k} is nonsingular. Suppose x = (x_{1}, …, x_{k}) ∈ F^{k} is the unique solution of the system A_{k}x^{T} = (a_{k+1}, …, a_{2k})^{T}. Then

(15)  A ∈ H_{n}^{(k)}(r, F) ⟺ the relation (13) holds for t = 1, …, 2n − r − 1.

Proof. Suppose A ∈ H_{n}^{(k)}(r, F). Again, we use induction on t. By Lemma 5.3, the relation (13) holds if 1 ≤ t ≤ n. Assume that n + 1 ≤ t ≤ 2n − r − 1 and that (13) holds for all values of t smaller than the given one. Define x^{(0)}, x^{(1)}, …, x^{(t−1)} in F^{k} recursively as follows. First, x^{(0)} := x = (x_{1}, …, x_{k}). Next, if ℓ ≥ 1 and if x^{(ℓ−1)} = (x_{1}^{(ℓ−1)}, …, x_{k}^{(ℓ−1)}) is known, then we let x_{0}^{(ℓ−1)} := 0 and let x^{(ℓ)} = (x_{1}^{(ℓ)}, …, x_{k}^{(ℓ)}) ∈ F^{k} be given by

x_{s}^{(ℓ)} = x_{s}x_{k}^{(ℓ−1)} + x_{s−1}^{(ℓ−1)} for s = 1, …, k.

Observe that for 1 ≤ ℓ < t and 1 ≤ m < t, we have

(16) ∑_{s=1}^{k} x_{s}^{(ℓ)}a_{m+s−1} = x_{k}^{(ℓ−1)} ∑_{s=1}^{k} x_{s}a_{m+s−1} + ∑_{s=1}^{k−1} x_{s}^{(ℓ−1)}a_{m+s} = ∑_{s=1}^{k} x_{s}^{(ℓ−1)}a_{m+s},

where the last equality follows from (13) with t replaced by m. Successive application of (16) shows that

(17)  ∑_{s=1}^{k} x_{s}^{(ℓ)}a_{m+s−1} = ∑_{s=1}^{k} x_{s}a_{m+s+ℓ−1} for 0 ≤ ℓ < t and 1 ≤ m ≤ t − ℓ.

Now consider the (2n − t) × (2n − t) principal submatrix B of A given by

B := A[1, 2, …, k, t + k − n + 1, …, n − 1, n|1, 2, …, k, t + k − n + 1, …, n − 1, n] and make the following 2n − t − k elementary column transformations:

C_{2n−t} − ∑_{s=1}^{k} x_{s}^{(n−k−1)}C_{s}, C_{2n−t−1} − ∑_{s=1}^{k} x_{s}^{(n−k−2)}C_{s}, …, C_{k+1} − ∑_{s=1}^{k} x_{s}^{(t−n)}C_{s},

where C_{j} indicates the j^{th} column. This transforms B to the (2n−t)×(2n−t) matrix

B′ = ( \begin{matrix}a_{1} & ⋯ & a_{k} & u_{1, 1} & ⋯ & u_{1, 2n−t−k} \\ ⋮ & ... & ⋮ & ⋮ & & ⋮ \\ a_{k} & ⋯ & a_{2k−1} & u_{k, 1} & ⋯ & u_{k, 2n−t−k} \\ a_{t+k−n+1} & ⋯ & a_{t+2k−1} & v_{1, 1} & ⋯ & v_{1, 2n−t−k} \\ ⋮ & & ⋮ & ⋮ & ... & ⋮ \\ a_{n} & ⋯ & a_{n+k−1} & v_{2n−t−k, 1} & ⋯ & v_{2n−t−k, 2n−t−k} \end{matrix} ) ,

for some u_{i, j}, v_{i, j} ∈ F. In fact, for 1 ≤ i ≤ k and 1 ≤ j ≤ 2n − t − k,

u_{i, j} = a_{i+t+k−n+j−1} − ∑_{s=1}^{k} x_{s}^{(t−n+j−1)}a_{i+s−1}

= a_{i+j+t−n−1+k} − ∑_{s=1}^{k} x_{s}a_{i+j+t−n−1+s−1} = 0,

where the penultimate equality follows from (17) and the last equality follows from (13) since t ≥ n + 1. Moreover, for 1 ≤ i, j ≤ 2n − t − k,

v_{i, j} = a_{2t+2k−2n+i+j−1} − ∑_{s=1}^{k} x_{s}^{(t−n+j−1)}a_{t+k−n+i+s−1};

also, since t ≥ n + 1, using (17), we have

(18) v_{i, j} = a_{2t+2k−2n+i+j−1} −∑_{s=1}^{k} x_{s}a_{2t+k−2n+i+j+s−2} if i + j ≤ 2n − t − k + 1.

In particular, v_{i, j} depends only on i+j whenever i+j ≤ 2n−t−k+1. Furthermore, if i + j ≤ 2n − t − k, then from (13) we deduce that v_{i, j} = 0 . Consequently, upon letting v = v_{1, 2n−t−k} = ⋯ = v_{2n−t−k, 1}, we obtain

det(B) = det(B′) = (−1)^{(2n−t−k)(2n−t−k+1)/2} det(A_{k})v^{2n−t−k}.

But since A ∈ H_{n}^{(k)}(r, F) and 2n − t ≥ r + 1, we have det(A_{k}) ≠ 0 and det(B) = 0. Hence v = 0, and from (18), we conclude that (13) holds for the given value of t.

Conversely, suppose the relation (13) holds for t = 1, …, 2n − r − 1. Then we can write v_{j} = x_{1}v_{j−k} + ⋯ + x_{k}v_{j−1} for j = k + 1, …, k + n − r, where v_{j} denotes the j^{th} column vector of A. Hence the column space of A is spanned by v_{1}, …, v_{k}, v_{k+n−r+1}, …, v_{n}. In particular, rank(A) ≤ k+n−(k+n−r+1)+1 = r. This together with Lemma 5.3 shows that A ∈ H_{n}^{(k)}(r, F). □

Corollary 5.6. |H_{n}^{(0)}(r, 𝔽_{q})| = q^{r} for 0 ≤ r < n and |H_{n}^{(k)}(r, 𝔽_{q})| = q^{r+k−1}(q − 1) for 1 ≤ k ≤ r < n. Consequently, |H_{n}(r, 𝔽_{q})| = q^{2r} for 0 ≤ r < n.

Proof. The first assertion follows from Lemma 5.2. Now suppose 1 ≤ k ≤ r < n. By Lemma 5.5, we see that the map A = (a_{i+j−1}) ↦ (A_{k}, a_{2k}, a_{2n−r+k}, …, a_{2n−1}) gives a bijection of H_{n}^{(k)}(r, F) onto HGL_{k}(F) × F^{r−k+1}. Hence by Corollary 5.4, |H_{n}^{(k)}(𝔽_{q})| = q^{2k−2}(q − 1)q^{r−k+1} = q^{r+k−1}(q − 1). Finally, |H_{n}(r, 𝔽_{q})| = q^{2r} is obvious when r = 0, whereas if 1 ≤ r < n, then using (10) and an easy evaluation of a telescopic sum, we conclude that |H_{n}(r, 𝔽_{q})| = ∑_{k=0}^{r} |H_{n}^{(k)}(r, 𝔽_{q})| = q^{2r}. □

We are now ready to prove the main result of this section.

Proof of Theorem 5.1: The case r = 0 is trivial and for r = n, Corollary 5.4 applies. Finally, if 1 ≤ r < n, then N(n, r; q) = |H_{n}(r, 𝔽_{q})| − |H_{n}(r − 1, 𝔽_{q})| = q^{2r} − q^{2r−2}, thanks to Corollary 5.6. □

A noteworthy consequence of Theorem 5.1 is that for a fixed positive integer r, the number of n×n Hankel matrices of rank r remains constant for every n ≥ r +1.

Acknowledgments

We are grateful to Bharath Sethuraman for his help in bringing together the two sets of authors from two different continents. We also thank an anonymous referee for bringing [9, §4.6] and [4] to our attention.

References

[1] A.T. Benjamin and C.D. Bennett, The probability of relatively prime polynomials, Math. Mag. 80 (2007), 196-202.

[2] S. Corteel, C. Savage, H. Wilf, and D. Zeilberger, A Pentagonal Number Sieve, J. Combin. Theory Ser. A 82 (1998), 186-192.

[3] D. E. Daykin, Distribution of bordered persymmetric matrices in a finite field, J. Reine Angew. Math. 203 (1960), 47–54.

[4] Z. Gao and D. Panario, Degree distribution of the greatest common divisor of polynomials over 𝔽_{q}, Random Structures Algorithms 29 (2006), 26–37.

[5] U. Helmke and P. A. Fuhrmann, Bezoutians, Linear Algebra Appl. 122/123/124 (1989), 1039–1097.

[6] X. Hou and G.L. Mullen, Number of irreducible polynomials and pairs of relatively prime polynomials in several variables over finite fields, Finite Fields Appl. 15 (2009), 304–331.

[7] S. R. Ghorpade and S. Ram, Block companion Singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields, preprint, 2010.

[8] E. Kaltofen and A. Lobo, On rank properties of Toeplitz matrices over finite fields, pp. 241–249, Proc. 1996 Internat. Symp. Symbolic Algebraic Comput. (ISSAC ’96), ACM Press, New York, 1996.

[9] D. E. Knuth, The Art of Computer Programming, Vol. 2, Seminumerical Algorithms, First, Second, and Third edition, Addison Wesley, Reading, MA, 1969, 1981, and 1997.

[10] K. Ma and J. von zur Gathen, Analysis of euclidean algorithms for polynomials over finite fields, J. Symbolic Computation 9 (2003), 429–455.

[11] G. H. Norton, Precise analysis of the right- and left-shift greatest common divisor algorithms for GF (q)[x], SIAM J. Comput. 18 (1989), 605–624.

[12] A. Reifegerste, On an involution concerning pairs of polynomials in 𝔽_{2}, J. Combin. Theory Ser. A 90 (2000), 216-220.

Department of Mathematics, University of British Columbia, Vancouver, BC V6T 1Z2, Canada.

E-mail address: marioga@math.ubc.ca

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: srg@math.iitb.ac.in

Department of Mathematics, Indian Institute of Technology Bombay, Powai, Mumbai 400076, India.

E-mail address: samrithram@gmail.com