On the rank of Hankel matrices over finite fields

DOI10.1016/J.LAA.2022.02.014MaRDI QIDQ2669189zbMATH OpenOpenAlexWikidataFDO

Authors Omesh Dhar Dwivedi, Darij Grinberg

Publication date 9 March 2022

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.05415

zbMATH Keywords

finite fieldsHankel matricesJacobi-Trudi matricesmatrix rankSchur polynomialsToeplitz matrices

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Polynomials over finite fields (11T06) Toeplitz, Cauchy, and related matrices (15B05) Matrices over special rings (quaternions, finite fields, etc.) (15B33)

Abstract: Given three nonnegative integers $p,q,r$ and a finite field $F$, how many Hankel matrices $left(x_{i+j}ight{)}_{0leqileqp,0leqjleqq}$ over $F$ have rank $leqr$ ? This question is classical, and the answer ($q^{2r}$ when $rleqminleftp,qight$) has been obtained independently by various authors using different tools (Daykin, Elkies, Garcia Armas, Ghorpade and Ram). In this note, we study a refinement of this result: We show that if we fix the first $k$ of the entries $x_0,x_1,ldots,x_{k-1}$ for some $kleqrleqminleftp,qight$, then the number of ways to choose the remaining $p+q-k+1$ entries $x_k,x_{k+1},ldots,x_{p+q}$ such that the resulting Hankel matrix $left(x_{i+j}ight{)}_{0leqileqp,0leqjleqq}$ has rank $leqr$ is $q^{2r-k}$. This is exactly the answer that one would expect if the first $k$ entries had no effect on the rank, but of course the situation is not this simple. The refined result generalizes (and provides an alternative proof of) a result by Anzis, Chen, Gao, Kim, Li and Patrias on evaluations of Jacobi-Trudi determinants over finite fields.

Review text

Given a field \(F,\) any \((n+1)\)-tuple \(x= (x_{0}, x_{1}, \cdots, x_{n})\in F^{n+1}\) and nonnegative integer numbers \(p, q\) satisfying \(p+q \leq n,\) generate the structured matrix \(H_{p,q}(x)= (x_{i+j})_{0\leq i \leq p, 0\leq j \leq q } \in F^{p+1, q+1}\) that is known in the literature as a Hankel matrix. These matrices appear in many fields of mathematics, as the theory of orthogonal polynomials (as Gram matrices in the monomial basis for inner products associated with probability measures supported on the real line), in the theory of total positivity and in control theory, among others. When \(F\) is a finite field with \(|F|=s\), an interesting problem is to find the number of Hankel matrices of a given rank. Indeed, if \(r, m, n\) are nonnegative integer numbers satisfying \(r\leq m\), \(r\leq n\), then the number of \((m+n+1)\)-tuples \(x\in F^{m+n+1}\) such that rank \(H_{m,n} (x)\leq r\) is \(s^{2r}.\) This result has been stated in an equivalent way and proved in [\textit{D. E. Daykin}, J. Reine Angew. Math. 203, 47--54 (1960; Zbl 0104.01304)]. In the present paper, the authors obtain the following generalization of the above result. Let \(F\) be a finite field and \(|F|=s\) and consider nonnegative integer numbers \(r, m, n\) such that \(r\leq m, r\leq n\) and fix a \(k\)-tuple \(a= (a_{0}, a_{1}, \cdots, a_{k-1}).\) Then the number of \(m+n+1\)-tuples \(x\in F^{m+n+1}\) such that \((x_{0}, x_{1}, \cdots, x_{k-1})=a\) and rank\((H_{m,n} (x) )\leq r\) is \(s^{2r-k}.\) This means that if one fixes the first \(k\) entries of \(H_{p,q}(x),\) then \(s^{2r-k}\) is the number of ways to choose the remaining \(p+q- k+1\) entries for some \(k\leq r \leq \min\{p,q\},\) in order to rank\((H_{p,q}(x))\leq r.\) This reflects the fact that the first \(k\) entries have no effect on the rank of the matrix. As a straightforward consequence, if \(r=m=n, \) then \(s^{2n-k}\) is the number of \((2n+1)\)-tuples \(x\in F^{2n+1}\) such that \((x_{0}, x_{1}, \cdots, x_{k-1})=a\) and \(H_{n,n}(x)\) is a singular matrix. Notice that in the framework of random matrices, in [\textit{B. Anzis} et al., Ann. Comb. 22, No. 3, 447--489 (2018; Zbl 1402.05214)], the authors deduce an expression of the probability of a certain Hankel matrix of size \((n+1)\times (n+1)\) over a finite field to be singular.

Recommendations

• scientific article; zbMATH DE number 3959669
• Spaces of Hankel matrices over finite fields
• scientific article; zbMATH DE number 1263321
• On determinantal varieties of Hankel matrices
• The Hankel matrix rank theorem revisited

Cites work

• Advanced determinant calculus
• Distribution of Bordered Persymmetric Matrices in a Finite Field.
• Enumerative combinatorics. Volume 2.
• scientific article; zbMATH DE number 5296403 (Why is no real title available?)
• scientific article; zbMATH DE number 3775748 (Why is no real title available?)
• scientific article; zbMATH DE number 1254299 (Why is no real title available?)
• Jacobi-Trudi determinants over finite fields
• On finite sequences satisfying linear recursions
• On the t-adic Littlewood conjecture
• On the sign patterns of entrywise positivity preservers in fixed dimension
• Relatively prime polynomials and nonsingular Hankel matrices over finite fields
• The mathematics of computerized tomography

Cited in

(12)

• On finite sequences satisfying linear recursions
• Spaces of Hankel matrices over finite fields
• Ranks for representations of \(GL_n\) over finite fields, their agreement, and positivity of Fourier transform
• The Hankel matrix rank theorem revisited
• Relatively prime polynomials and nonsingular Hankel matrices over finite fields
• scientific article; zbMATH DE number 3959669 (Why is no real title available?)
• On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field
• Multislant matrices and Jacobi-Trudi determinants over finite fields
• The Bhargava greedoid as a Gaussian elimination greedoid
• On the minimal denominator problem in function fields
• Counting minors of a Hankel matrix
• On determinantal varieties of Hankel matrices

This page was built for publication: On the rank of Hankel matrices over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2669189)