# Does a fundamental solution set exist for homogeneous first-order difference equations?

When $A$ is diagonalisable, $\vec{x}_{k+1}=A\vec{x}_k$ implies that $\vec{x}_k = c_1\lambda_1^k\vec{v}_1 +...+c_n\lambda_n^k\vec{v}_n$ because an eigenbasis exists and any $\vec{x}$ can be decomposed into a linear combination of $A$'s eigenvectors.

But when $A$ is not diagonalisable, is there a related general formula for (or a general technique to find) $\vec{x}_k$ in terms of $A$'s eigenvalues and eigenvectors?

I ask this because I have just learnt that for the differential system $\dot{\vec{x}}=A\vec{x}$, a fundamental solution set always exists so that even when $A$ is defective, $\vec{x}$ can still be expressed in terms of $A$'s eigenvectors and eigenvalues.

-

It works pretty much the same way as for differential equations. Let $P^{-1}AP=J$ where $J$ is in Jordan form. Then $$x_k=A^kx_0=PJ^kP^{-1}x_0$$ and you just need to understand powers of a matrix in Jordan form, and the relation of $P$ to the eigenvectors and generalized eigenvectors.
EDIT: Here's the simplest example. Say $$A=\pmatrix{\lambda&1\cr0&\lambda\cr}$$ Then $$A^n=\pmatrix{\lambda^n&n\lambda^{n-1}\cr0&\lambda^n\cr}$$ Let $v_1$ be the eigenvector $(1,0)$, let $v_2$ be the generalized eigenvector $(0,1)$. Then $$A^nv_1=\lambda^nv_1\quad A^nv_2=n\lambda^{n-1}v_1+\lambda^nv_2$$ so $$A^n(c_1v_1+c_2v_2)=(c_1\lambda^n+c_2n\lambda^{n-1})v_1+c_2\lambda^nv_2$$
MORE EDIT: We can rewrite that last expression as $$x_n=c_1\lambda^nv_1+c_2\lambda^n((n/\lambda)v_1+v_2)$$ which looks a little more like the form you've given for the analogous difference equation.
Thnkas Gerry. Is it possible to give a concrete example specifically showing how the formula for $\textbf x_k$ is expressed in terms of the eigenvecs and eigenvals for those components of $\textbf x$ that don't directly have a eigenvector-coordinate? – Ryan Aug 26 '12 at 10:57
I'm very lost. Will you express $\mathbf x_k$ in terms of the eigenvecs and eigenvals? (For a differential system containing 2 equations and where $\lambda$ has algebraic multiplicity 2 and geometric multiplicity 1, we have $\mathbf x=c_1e^{\lambda t}\mathbf v+c_2 e^{\lambda t} (t\mathbf v +\mathbf w)$. Is there a related equation for the analogous difference system?) – Ryan Aug 26 '12 at 11:38