Let the sequence $(s_n)_n$ be generated by an LFSR (linear feedback shift register) of order $k$. We know $s_0,\dots,s_{2k-1}$ and want to determine $a_0,\dots,a_{k-1}$. If the solution is not unique, show that every solution leads to the sequence $(s_n)_n$.
My attempt: We know that $s_{n+k}=a_{k-1}s_{n+k-1}+\dots+a_os_n$ for $n\geq 0$ (where $a_i\in\mathbb{F_q}$. This implies the following set of equations: $$ s_k=a_{k-1}s_{k-1}+\dots+a_0s_0\\ s_{k+1}=a_{k-1}s_{k}+\dots+a_0s_1\\ \vdots\\ s_{2k-1}=a_{k-1}s_{2k-2}+\dots+a_0s_{k-1} $$ but I do not know how to proceed. Is there a simple way of solving such a large system of equations?
The unknown vector in this case is $a = [a_{k-1}, a_{k-2}, \dots, a_1, a_0] $, you can build the system
$ S a = v $
where
$ S = \begin{bmatrix} s_{k-1}&& s_{k-2}&& \dots && s_1 && s_0 \\ s_{k}&& s_{k-1}&& \dots && s_2 && s_1 \\ \vdots && \vdots && \vdots && \vdots && \vdots \\ s_{2k-2}&& s_{2k-1}&& \dots && s_{k-2} && s_{k-1} \end{bmatrix}$
And
$ v = \begin{bmatrix} s_k \\ s_{k+1} \\ \vdots \\ s_{2k-1} \end{bmatrix} $
Then the unknown vector is given by
$ a = S^{-1} v $