Algorithms for Computing the Determinant of a Hankel Matrix Consider a $n\times n$ Hankel Matrix
$$
H = \begin{bmatrix}
    x_{1} & x_{2} & \dots & x_{n} \\
    x_{2} & x_{3} & \dots & x_{n+1} \\
    \vdots \\
    x_{n} & x_{n+1} & \dots & x_{2n}
\end{bmatrix}
$$
, where all $x_i \in \mathbb{Z}_p = \{ 0,\dots,p-1 \}$, where $p$ is prime.
What is the most efficient way to test whether the matrix is invertible or not. More concretely:
Is there a more efficient than computing the determinant?
If not, is there a more efficient way of computing the determinant of such a matrix?
 A: There is an algorithm called Levinson Recursion for Toeplitz matrices which is $\mathcal{O}(n^{2})$. There is exists a similar algorithm for Hankel matrices called Hankel Recursion. It appears to be based on the Lanczos algorithm. People don't generally compute determinants the normal way. E.g. they form a matrix decomposition since the following
$$ A = LU \implies det(A) = det(LU) =det(L)det(U)$$
after this is done.
$$ det(L)det(U) =\prod_{i=1}^{n} l_{ii} \prod_{i=1}^{n} u_{ii} $$
Similarly with the QR decomp
$$ A =QR \implies det(A) = det(Q)det(R) $$
since the determinant of $ Q $ is 1
$$ det(A) = 1 \cdot \prod_{i=1}^{n} r_{ii} $$
However, in general, you don't want to use determinant to see if it is invertible. Just extra steps...
A: This is not a full answer, but it's too long for a comment. The Hankel matrix
$$
H = \begin{bmatrix} x_1 & x_2 & x_3 & x_4 \\ 
x_2 & x_3 & x_4 & x_5 \\
x_3 & x_4 & x_5 & x_6 \\
x_4 & x_5 & x_6 & x_7 \\
\end{bmatrix}
$$
can be enlarged to an anti-circulant matrix
$$
\tilde H = 
\left[
\begin{array}{c|c}
\begin{array}{c c c c}
x_1 & x_2 & x_3 & x_4  \\
x_2 & x_3 & x_4 & x_5 \\
x_3 & x_4 & x_5 & x_6  \\
x_4 & x_5 & x_6 & x_7 \\
\end{array}
& 
\begin{array}{c c c}
x_5 & x_6 & x_7 \\
x_6 & x_7 & x_1 \\
x_7 & x_1 & x_2 \\
x_1 & x_2 & x_3\\
\end{array}
\\
\hline
\begin{array}{c c c c}
x_5 & x_6 & x_7 & x_1 \\
x_6 & x_7 & x_1 & x_2  \\
x_7 & x_1 & x_2 & x_3 \\
\end{array}
& 
\begin{array}{c c c}
x_2 & x_3 & x_4 \\
x_3 & x_4 & x_5 \\
x_4 & x_5 & x_6\\
\end{array}
\end{array}
\right].
$$
I think some discrete Fourier transform techniques are available to perform computations with anti-circulant matrices efficiently. See this post for example: https://math.stackexchange.com/a/1377399/40119
Perhaps this would help with computations involving $H$, though I'm not certain.
