On the singularity of generalised Vandermonde matrices over finite fields
type: Item
instance of: scholarly article
title: On the singularity of generalised Vandermonde matrices over finite fields
zbMATH Open document ID: 1144.11083
author: Igor E. Shparlinski
published in: Finite Fields and their Applications
publication date: 2005-06-01T00:00:00Z
review text: Let \(\mathbb F_q\) denote a finite field of \(q\) elements. Fix \(m\) elements \(\lambda_1,\dots,\lambda_m\in\mathbb F_q^*\) and consider matrices of the form \((\lambda_i^{u_j})_{i,j=1}^m\), with integers \(u_1,\dots,u_m\in [0,q-2]\). The choice \(u_j= j-1\), \(j=1,\dots,m\), corresponds to the Vandermonde matrix, which is known to be nonsingular, provided that \(\lambda_1,\dots,\lambda_m\) are pairwise distinct. Here the author shows that for \(m\) fixed almost all matrices of the above form are nonsingular. More precisely, denote by \(V(\lambda_1,\dots,\lambda_m)\) the number of \(m\)-tuples \((u_1,\dots,u_m)\in [0,q-2]^m\) for which \(\det(\lambda_i^{u_j})_{i,j=1}^m=0\). The author uses an upper bound on the number of zeros of sparse polynomials [\textit{R. Canetti, J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman} and \textit{I. E. Shparlinski}, Isr. J. Math. 120, 23--46 (2000; Zbl 0997.11066), \textit{J. B. Friedlander, S. Konyagin, M. Larsen, D. Lieman} and \textit{I. E. Shparlinski}, Des. Codes Cryptography 16, No. 3, 249--256 (1999; Zbl 0941.94014)] to estimate \(V(\lambda_1,\dots,\lambda_m)\). His estimate depends on the multiplicative orders of ratios \(\lambda_j/\lambda_i\), \(1\leq i<j\leq m\). Recall that for an element \(\lambda\in\mathbb F_q^*\) \(\operatorname{ord}\lambda\) denotes the multiplicative order of \(\lambda\), that is, the smallest positive integer \(s\) with \(\lambda^s=1\). Theorem. For any \(m\geq 2\) the bound \(V(\lambda_1,\dots,\lambda_m)\leq 3(m-1) (q-1)^m T^{-1/(m-1)},\) holds, where \[ T=\min_{1\leq i\leq m}\;\min_{\substack{ 1\leq i\leq m\\ j\neq i}} \operatorname{ord} \lambda_j/\lambda_i. \] The author also obtains another result about the value of \(V(\lambda_1,\dots,\lambda_m)\) on average over all \(m\)-tuples \((\lambda_1,\dots,\lambda_m)\in (\mathbb F_q^*)^m\). Theorem. For any \(m\geq 2\) and any \(\varepsilon>0\) the bound \(W_m= O(q^{m-1/(m-1)+\varepsilon})\) holds.
reviewed by: Olaf Ninnemann
Mathematics Subject Classification ID: 11T30
Mathematics Subject Classification ID: 12E20
zbMATH DE Number: 2173074
zbMATH Keywords: exponential equations
zbMATH Keywords: sparse polynomials
zbMATH Keywords: Vandermonde matrices
MaRDI profile type: Publication
full work available at URL: j.ffa.2004.11.001
OpenAlex ID: W1981407720
cites work: On the statistical properties of Diffie-Hellman distributions
cites work: Q4421931
cites work: On the correlation of binary \(M\)-sequences
cites work: Q3248054
cites work: Cryptographic applications of analytic number theory. Complexity lower bounds and pseudo\-randomness
cites work: ON THE CONSTRUCTION OF A PRIMITIVE NORMAL BASIS IN A FINITE FIELD
DOI: 10.1016/J.FFA.2004.11.001
description: scientific article; zbMATH DE number 2173074