On the singularity of generalised Vandermonde matrices over finite fields (Q1779326): Difference between revisions

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.