Algorithms for Computing the Determinant of a Hankel Matrix

Question

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?

Answer 1

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.

Answer 2

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...