Suppose is a matrix (over a field ). Then the characteristic polynomial of is defined as $P_A(t) = \Det(tI - A)$ (Error compiling LaTeX. ! Undefined control sequence.), which is a th degree polynomial in . Here, refers to the identity matrix.
Written out, the characteristic polynomial is the determinant
An eigenvector is a non-zero vector that satisfies the relation , for some scalar . In other words, applying a linear operator to an eigenvector causes the eigenvector to dilate. The associated number is called the eigenvalue.
There are at most distinct eigenvalues, whose values are exactly the roots of the characteristic polynomial of the square matrix. To prove this, we use the fact that the determinant of a matrix is iff the column vectors of the matrix are linearly dependent. Observe that if satisfies , then the column vectors of are linearly dependent. Hence, there exists a non-zero vector such that . Distributing and re-arranging, , as desired. In the other direction, if , then . But then, the column vectors of are linearly dependent, so it follows that .
By the Hamilton-Cayley Theorem, the character polynomial of a square matrix applied to the square matrix itself is zero.
where is a sequence of real numbers, and are real constants. The characteristic polynomial of this recurrence is the polynomial
For example, let be the th Fibonacci number defined by , and
Then, its characteristic polynomial is .
The roots of the polynomial can be used to write a closed form for the recurrence. If the roots of this polynomial are distinct, then suppose the roots are . Then, there exists real constants such that
If we evaluate different values of (typically ), we can find a linear system in the s that can be solved for each constant. Refer to the introductory problems below to see an example of how to do this. In particular, for the Fibonacci numbers, this yields Binet's formula.
If there are roots with multiplicity greater than , suppose . Then we would replace the term with the expression .
For example, consider the recurrence relation . It’s characteristic polynomial, , has a double root. Then, its closed form solution is of the type .
Note: The ideas expressed in this section can be transferred to the next section about differential equations.
so that (try to verify this). The characteristic polynomial of is precisely (again, try to verify this). If the roots of are distinct, then there exists a basis (of ) consisting of eigenvectors of . That is, we can write
for an unitary matrix and a diagonal matrix . Then, , and in general, . Thus, . Here, and are fixed (note that to find the values of , we may need to trace the recurrence backwards. We only take the th index for simplicity). It follows that is a linear combination of the diagonal elements of , namely .
There are a couple of other ways to prove this. One is by induction, though the proof is not very revealing; we can explicitly check that a sequence , for real numbers , satisfies the linear recurrence relation . If the two sequences are the same for the first values of the sequence, it follows by induction that the two sequences must be exactly the same.
In particular, for , we can check this by using the identity
Here, is short-hand for the differential operator.
If the roots of the polynomial are distinct, say , then the solutions of this differential equation are precisely the linear combinations . Similarly, if there is a set of roots with multiplicity greater than , say , then we would replace the term with the expression .
In general, given a linear differential equation of the form , where is a linear differential operator, then the set of solutions is given by the sum of any solution to the homogenous equation and a specific solution to .
We can apply an induction technique similar to the section on linear recurrences above.
From linear algebra, we can use the following theorem.
- Prove Binet's formula. Find a similar closed form equation for the Lucas sequence, defined the starting terms , and .
This article is a stub. Help us out by.