View paper:
View abstract:

Published: 
May 1, 2002

Keywords: 
Hankel matrix, linear recursion, finite field, discrete Fourier transform, random Hankel matrix

Subject: 
47B35, 15A57

Abstract:

For any field $k$\/ and any integers $m,n$
with $0 \leqs 2m \leqs n+1$, let $W_n$ be the \hbox{$k$\/vector} space
of sequences $(x_0,\ldots,x_n)$, and let $H_m \subseteq W_n$ be the
subset of sequences satisfying a \hbox{degree$m$} linear recursion
 that is, for which there exist $a_0,\ldots,a_m\in k$,
not all zero, such that
$$
\sum_{i=0}^m a_i x_{i+j} = 0
$$
holds for each $j=0,1,\ldots,nm$. Equivalently, $H_m$ is the set
of $(x_0,\ldots,x_n)$ such that the $(m+1) \times (nm+1)$ matrix
with $(i,j)$ entry $x_{i+j}$ ($0\leqs i\leqs m$, $0\leqs j \leqs nm$)
has rank at most~$m$. We use elementary linear and polynomial algebra
to study these sets $H_m$. In particular, when $k$\/ is a finite field
of~$q$ elements, we write the characteristic function of~$H_m$ as a
linear combination of characteristic functions of linear subspaces
of dimensions~$m$ \hbox{and $m+1$} in~$W_n$. We deduce a formula
for the discrete Fourier transform of this characteristic function,
and obtain some consequences. For instance, if the $2m+1$ entries
of a square Hankel matrix of order $m+1$ are chosen independently from
a fixed but not necessarily uniform distribution~$\mu$ on~$k$,
then as $m\ra\infty$ the matrix is singular with probability
approaching $1/q$ provided $\\muhat\\0_1 < q^{1/2}$.
This bound $q^{1/2}$ is best possible if $q$ is a square.

Acknowledgments:
Supported in part by the Packard Foundation
Author information:
Department of Mathematics, Harvard University, Cambridge, MA 02138
elkies@math.harvard.edu
http://www.math.harvard.edu/~elkies/
 