Characteristic Polynomial for a Difference Equation¶

Definition¶

For the homogeneous linear difference equation of order $k$ with constant coefficients and $a_0\ne0$$0$,

the characteristic polynomial is

and $p(r)=0$ is the characteristic equation. Its roots $r_1,\ldots,r_k$ (real or complex, counted with multiplicity) are the characteristic roots.

Interpretation¶

Substituting the trial solution $x_t=r^t$ with $r\ne0$ gives $r^t\,p(r)=0$$0$. So the geometric sequence $r^t$ solves the equation exactly when $r$ is a characteristic root, and the problem of solving a recurrence reduces to finding the roots of one polynomial.

The figure takes the complex-roots example $x_{t+2}-x_{t+1}+x_t=0$$0$. The roots of $p(r)=r^2-r+1$ lie on the unit circle at the angles $\pm\pi/3$ (left). Because $|r|=1$ the solutions neither grow nor shrink, and because each step turns by $\pi/3$ they return after $6$ steps: the solution from $x_0=x_1=1$ (right) is $1,1,0,-1,-1,0$ repeated.

The polynomial is read off the equation by replacing $x_{t+j}$ with $r^j$. Its coefficients are those of the equation written with every term on the left; with $x_{t+2}=x_{t+1}+x_t$ one must first rewrite $x_{t+2}-x_{t+1}-x_t=0$ to get $p(r)=r^2-r-1$$1$.

The name is not a coincidence. The equation is equivalent to $\boldsymbol{y}_{t+1}=C\boldsymbol{y}_t$ for the companion matrix $C$ of a higher-order equation, and $p(\lambda)=\det(\lambda I-C)$$C)$, which is the characteristic polynomial $\det(C-\lambda I)$ of that matrix up to the factor $(-1)^k$. Characteristic roots are therefore the eigenvalues of $C$.

Key Results¶

• $r^t$ is a solution if and only if $p(r)=0$$0$; since $a_0\ne0$$0$, $0$ is never a root.
• A root $r$ of multiplicity $m$ gives the $m$ solutions $r^t,\,t\,r^t,\,\ldots,\,t^{m-1}r^t$; together over all roots these form a complex basis of solutions for complex-valued sequences.
• Real coefficients make nonreal roots appear in conjugate pairs $\rho \mathrm{e}^{\pm\mathrm{i}\theta}$; for a real basis, replace each pair of multiplicity $m$ by $t^j\rho^t\cos(\theta t)$ and $t^j\rho^t\sin(\theta t)$ for $j=0,\ldots,m-1$$1$.
• Vieta: the roots sum to $-a_{k-1}$ and multiply to $(-1)^k a_0$.
• $p(1)=1+a_{k-1}+\cdots+a_0$$a_0$; if $p(1)\ne0$$0$, the equation with constant right-hand side $b$ has the equilibrium $x^*=b/p(1)$$b/p(1)$.

Examples¶

Distinct roots. $x_{t+2}-3x_{t+1}+2x_t=0$ has $p(r)=r^2-3r+2=(r-1)(r-2)$$2)$, so $x_t=c_1+c_2\,2^t$$c_2{2}^t$.

Repeated root. $x_{t+2}-4x_{t+1}+4x_t=0$ has $p(r)=(r-2)^2$$2{)}^2$. Besides $2^t$, $t\,2^t$ is a solution: $(t+2)2^{t+2}-4(t+1)2^{t+1}+4t\,2^t=2^t(4t+8-8t-8+4t)=0$$0$. Hence $x_t=(c_1+c_2t)2^t$$c_{2}t)2^t$.

Complex roots. $x_{t+2}-x_{t+1}+x_t=0$ has $p(r)=r^2-r+1$ with roots $\tfrac{1}{2}\pm\tfrac{\sqrt{3}}{2}\mathrm{i}=\mathrm{e}^{\pm\mathrm{i}\pi/3}$${\mathrm{e}}^{\pm \mathrm{i}\pi /3}$. So $x_t=c_1\cos(\pi t/3)+c_2\sin(\pi t/3)$$c_2\sin (\pi t/3)$, a solution of period $6$; from $x_0=x_1=1$ the recursion gives $1,1,0,-1,-1,0,1,\ldots$

Fibonacci. $p(r)=r^2-r-1$ has roots $\varphi=\tfrac{1+\sqrt{5}}{2}$ and $\psi=\tfrac{1-\sqrt{5}}{2}$$\frac{1-\sqrt{5}}{2}$; with $x_0=0$$0$, $x_1=1$ this gives $x_t=(\varphi^t-\psi^t)/\sqrt{5}$${\psi }^t)/\sqrt{5}$.

Prerequisites¶

• Difference Equation
• Root of a Polynomial
• Characteristic Polynomial

Related Concepts¶

• Basis of Solutions of a Difference Equation
• Second-Order Linear Difference Equation
• Higher-Order Linear Difference Equation
• Stability of a Scalar Difference Equation
• Characteristic Equation for a Differential Equation

Sources¶

• Math V: Advanced Linear Algebra · Week 2

Aliases: characteristic equation of a difference equation, auxiliary equation of a recurrence, characteristic polynomial of a recurrence Keywords: trial solution x_t = r^t, characteristic roots, repeated root t r^t, companion matrix, p(r) = r^k + a_{k-1} r^{k-1} + ... + a_0 Symbols: lambda, phi, pi, psi, rho, square root, theta

Last updated: 27 October 2026 11:52