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!

  • $\begingroup$ Using the Frobenius decomposition theorem seems like a perfect way to get the result $\endgroup$ – Omnomnomnom May 31 '16 at 9:23
  • $\begingroup$ Thank you for your input! I guess I should be satisfied with my current proof. $\endgroup$ – C. Falcon May 31 '16 at 9:30
  • 1
    $\begingroup$ You might want to post your current proof (in a new question) and get feedback on it that way $\endgroup$ – Omnomnomnom May 31 '16 at 9:32

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

  • 1
    $\begingroup$ That is a really neat way of seeing it! I am not sure Cayley-Hamilton theorem is easier than the Frobenius decomposition though, but both theorems suit me. To give some background I wanted to show the equivalence between Skolem-Mahler-Lech theorem and this statement: if $k/\mathbb{Q}$ is a field extension, $\sigma$ is a linear automorphism, $x\in k^d$ and $H$ is an hyperplane, then $\{n\in\mathbb{N}\textrm{ s.t. }\sigma^n(x)\in H\}$ is the union of a finite set and of a finite number of arithmetic progressions. $\endgroup$ – C. Falcon Jun 25 '16 at 1:29
  • 1
    $\begingroup$ @C.Falcon This method comes up often for me because of integer quadratic forms; if $H$ is the symmetric matrix of second partial derivates of a quadratic form, given by $h(x) = (1/2) x^T H x,$ then a matrix $A$ that solves $A^T H A = H$ automatically gives $h(Ax) = h(x).$ The most frequent example on this site is the ordinary Pell equation $x^2 - n y^2 = 1.$ The outcome is that $x$ and $y$ obey identical linear recurrences, degree $2$ because we have two variables. $\endgroup$ – Will Jagy Jun 25 '16 at 1:52
  • 1
    $\begingroup$ This year I actually studied (in an arithmetic course) the link between integer quadratic forms, Pell equations and units of the ring of integers of a quadratic field extension. It is nice to have here a quick reminder, it helped me clarify some of my ideas. $\endgroup$ – C. Falcon Jun 25 '16 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.