Linear algebra question: does it have a solution?

Question

Given $k\in\mathbb{N}$, $p$ a prime number, $s = (s_1, s_2,..., s_{2k+1})\in \mathbb{M}_{(2k+1)*1}(\mathbb{F}_p)$, the Hankel matrix generated by s is denoted as H.

$$

H = \begin{pmatrix}

s_1 & s_2 & \cdots & s_{k+1} \\

s_2 & s_3 & \cdots & s_{k+2} \\

\vdots & \vdots & \ddots & \vdots \\

s_{k+1} & s_{k+2} & \cdots & s_{2k+1}

\end{pmatrix}

$$

Now we know that H is of full rank. Question: do there exist $c = (n_1,n_2,\dots,n_{k+1})\in\mathbb{M}_{1*(k+1)}(\mathbb{F}_p)$ and $b = (b_1,b_2,\dots, b_{k+1})^T\in\mathbb{M}_{(k+1)*1}(\mathbb{F}_p)$ such that the following system holds:

$$\begin{pmatrix}

1 & 1 & \cdots & 1 \\

n_1 & n_2 & \cdots & n_{k+1} \\

\vdots & \vdots & \ddots & \vdots \\

n_1^{2k} & n_2^{2k} & \cdots & n_{k+1}^{2k}

\end{pmatrix}\cdot \begin{pmatrix}

b_1 \\ b_2\\ \vdots\\b_{k+1}

\end{pmatrix} = \begin{pmatrix}

s_1\\s_2\\\vdots\\\vdots\\s_{2k+1}

\end{pmatrix}$$

Answer 1

Given \( k \in \mathbb{N} \), \( p \) a prime number, \( s = (s_1, s_2, \ldots, s_{2k+1}) \in \mathbb{M}_{(2k+1) \times 1} (\mathbb{F}_p) \), the Hankel matrix generated by \( s \) is denoted as \( H \):

\[

H = \begin{pmatrix}

s_1 & s_2 & \cdots & s_{k+1} \\

s_2 & s_3 & \cdots & s_{k+2} \\

\vdots & \vdots & \ddots & \vdots \\

s_{k+1} & s_{k+2} & \cdots & s_{2k+1}

\end{pmatrix}

\]

We know that \( H \) is of full rank. The question is whether there exist \( c = (n_1, n_2, \ldots, n_{k+1}) \in \mathbb{M}_{1 \times (k+1)} (\mathbb{F}_p) \) and \( b = (b_1, b_2, \ldots, b_{k+1})^T \in \mathbb{M}_{(k+1) \times 1} (\mathbb{F}_p) \) such that the following system holds:

\[

\begin{pmatrix}

1 & 1 & \cdots & 1 \\

n_1 & n_2 & \cdots & n_{k+1} \\

\vdots & \vdots & \ddots & \vdots \\

n_1^{2k} & n_2^{2k} & \cdots & n_{k+1}^{2k}

\end{pmatrix}

\begin{pmatrix}

b_1 \\ b_2 \\ \vdots \\ b_{k+1}

\end{pmatrix} =

\begin{pmatrix}

s_1 \\ s_2 \\ \vdots \\ s_{2k+1}

\end{pmatrix}

\]

Yes, such vectors \( c = (n_1, n_2, \ldots, n_{k+1}) \) and \( b = (b_1, b_2, \ldots, b_{k+1})^T \) exist. This is guaranteed by the fact that the Hankel matrix \( H \) is of full rank. Here's a detailed explanation:

Given the Hankel matrix \( H \) generated by the sequence \( s = (s_1, s_2, \ldots, s_{2k+1}) \):

\[

H = \begin{pmatrix}

s_1 & s_2 & \cdots & s_{k+1} \\

s_2 & s_3 & \cdots & s_{k+2} \\

\vdots & \vdots & \ddots & \vdots \\

s_{k+1} & s_{k+2} & \cdots & s_{2k+1}

\end{pmatrix}

\]

we know that \( H \) is of full rank, meaning its rank is \( k+1 \).

The problem is to find vectors \( c = (n_1, n_2, \ldots, n_{k+1}) \) and \( b = (b_1, b_2, \ldots, b_{k+1})^T \) such that the following Vandermonde matrix equation holds:

\[

\begin{pmatrix}

1 & 1 & \cdots & 1 \\

n_1 & n_2 & \cdots & n_{k+1} \\

\vdots & \vdots & \ddots & \vdots \\

n_1^{2k} & n_2^{2k} & \cdots & n_{k+1}^{2k}

\end{pmatrix}

\begin{pmatrix}

b_1 \\ b_2 \\ \vdots \\ b_{k+1}

\end{pmatrix} =

\begin{pmatrix}

s_1 \\ s_2 \\ \vdots \\ s_{2k+1}

\end{pmatrix}

\]

This can be rephrased as finding a solution to a system where the Vandermonde matrix is constructed from the roots \( n_1, n_2, \ldots, n_{k+1} \).

Since \( H \) is of full rank, it means that the sequence \( s \) can be represented in the form of a linear combination of powers of \( n_1, n_2, \ldots, n_{k+1} \). Specifically, there exist distinct elements \( n_1, n_2, \ldots, n_{k+1} \) in \( \mathbb{F}_p \) and coefficients \( b_1, b_2, \ldots, b_{k+1} \) such that:

\[ s_m = \sum_{j=1}^{k+1} b_j n_j^{m-1} \quad \text{for} \quad m = 1, 2, \ldots, 2k+1 \]

This is equivalent to the system:

\[

\begin{pmatrix}

1 & 1 & \cdots & 1 \\

n_1 & n_2 & \cdots & n_{k+1} \\

\vdots & \vdots & \ddots & \vdots \\

n_1^{2k} & n_2^{2k} & \cdots & n_{k+1}^{2k}

\end{pmatrix}

\begin{pmatrix}

b_1 \\ b_2 \\ \vdots \\ b_{k+1}

\end{pmatrix} =

\begin{pmatrix}

s_1 \\ s_2 \\ \vdots \\ s_{2k+1}

\end{pmatrix}

\]

The Vandermonde matrix on the left-hand side is known to be non-singular if the \( n_i \) are distinct. Hence, the existence of a unique solution \( b = (b_1, b_2, \ldots, b_{k+1})^T \) is guaranteed, provided the \( n_i \) are chosen to be distinct elements in \( \mathbb{F}_p \).

Therefore, such vectors \( c \) and \( b \) exist, and they satisfy the given matrix equation.