Let $k$ be a field, let $d$ be an integer greater than $1$, let $(v,x)\in k^d\times k^d$ and let $A\in k^{d\times d}$ be invertible.
For all $n\in\mathbb{N}$, let define the following element of $k$: $$u_n:={}^tvA^nx.$$
I would like to show that:
$(u_n)_{n\in\mathbb{N}}$ is a recurrent linear sequence.
This fact is well-known when $A$ is a companion matrix (or its transpose, that depends on your definition).
Surely I can use Frobenius decomposition theorem and get the result, but that might be overkill.
Any hint will be appreciated!
This should be the same as the linear systems we often get, just $y_n = A^n x.$ Here the matrix $A$ is square, you are calling it $d.$
The Cayley-Hamilton Theorem says that $A$ satisfies a polynomial, degree no larger than $d.$ The same equation is satisfied by the column vectors $y_{k+d}, y_{k+d-1}, \ldots, y_k.$ That is why the $d$ entries of $y$ each obey the same linear recursion.
Finally, your $u_n$ obeys the same recursion, coefficients are those of the characteristic polynomial of $A,$ or the minimal polynomial if that has smaller degree.
Here is a recent one How does one solve this recurrence relation?
I have answered many questions the same way...