Find Linear Reccurence Operator Given Solutions
The characteristic polynomial of a linear operator refers to the polynomial whose roots are the eigenvalues of the operator. It carries much information about the operator.
In the context of problem-solving, the characteristic polynomial is often used to find closed forms for the solutions of linear recurrences.
Contents
- 1 Definition
- 2 Properties
- 3 Linear recurrences
- 3.1 Proof 1 (Linear Algebra)
- 3.2 Proof 2 (Induction)
- 3.3 Proof 3 (Partial fractions)
- 4 Differential equations
- 4.1 Proof
- 5 Problems
- 5.1 Introductory
- 5.2 Intermediate
- 5.3 Olympiad
- 6 Hints/Solutions
- 6.1 Introductory
- 6.2 Intermediate
- 6.3 Olympiad
Definition
Suppose is a matrix (over a field ). Then the characteristic polynomial of is defined as , which is a th degree polynomial in . Here, refers to the identity matrix.
Written out, the characteristic polynomial is the determinant
Properties
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 the matrix are linearly dependent. Indeed, if we define and let denote the column vectors of , this is equivalent to saying that there exists not all zero scalars such that
Note that if , then . Hence, the characteristic polynomial encodes the determinant of the matrix. Also, the coefficient of the term of gives the negative of the trace of the matrix (which follows from Vieta's formulas).
By the Hamilton-Cayley Theorem, the characteristic polynomial of a square matrix applied to the square matrix itself is zero, that is . The minimal polynomial of thus divides the characteristic polynomial .
Linear recurrences
Let be a sequence of real numbers. Consider a monic homogenous linear recurrence of the form
where are real constants. The characteristic polynomial of this recurrence is defined as 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
Given a linear recurrence of the form , we often try to find a new sequence such that is a homogenous linear recurrence. Then, we can find a closed form for , and then the answer is given by .
Of the following proofs, the second and third are more approachable.
Proof 1 (Linear Algebra)
Note: The ideas expressed in this section can be transferred to the next section about differential equations. This requires some knowledge of linear algebra (upto the Spectral Theorem).
Let . Then, we can express our linear recurrence as the matrix
so that (try to verify this). The characteristic polynomial of is precisely . This is not difficult to show via Laplace's expansion and induction, and is left as an exercise to the reader.
If the roots of are distinct, then there exists a basis (of ) consisting of eigenvectors of (since eigenvectors of different eigenvalues are linearly independent). That is, applying a change of bases, we can write
Suppose now that that the roots of are not distinct. Then, we can write the matrix in the Jordan normal form. For simplicity, first consider just a single root repeated times. The corresponding Jordan form of the matrix is given by (that is, the matrix is similar to the following):
Exponentiating this matrix to the th power will yield binomial coefficients as follows
We can treat the binomial coefficient as a polynomial in . Furthermore, we can scale away the powers of the eigenvalue (which is a constant); after taking the appropriate linear combinations of the binomial coefficients and a little bit of work, the result follows.
See also a <url>viewtopic.php?t=290351 graph-theoretic</url> approach.
Proof 2 (Induction)
There are a couple of lower-level 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
It is also possible to reduce the recurrence to a telescoping sum. However, the details are slightly messy.
Proof 3 (Partial fractions)
Another method uses partial fractions and generating functions, though not much knowledge of each is required for this proof. Let be a linear recurrence. Consider the generating function given by
Then, writing the following expressing out and carefully comparing coefficients (try it),
where is a remainder polynomial with degree . Re-arranging,
This polynomial in the denominator is the reverse of the characteristic polynomial of the recurrence. Hence, its roots are , assuming that the roots are distinct. Using partial fraction decomposition (essentially the reverse of the process of adding fractions by combining denominators, except we now pull the denominators apart), we can write
for some constants . Using the geometric series formula, we have . Thus,
Comparing coefficients with our original definition of gives , as desired.
The generalization to characteristic polynomials with multiple roots is not difficult from here, and is left to the reader. The partial fraction decomposition will have terms of the form for .
A note about this argument: all of the power series used here are defined formally, and so we do not actually need to worry whether or not they converge. See these blogposts for further ideas.
Differential equations
Given a monic linear homogenous differential equation of the form , then the characteristic polynomial of the equation is the polynomial
Here, is short-hand for the differential operator.
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 .
Proof
We can apply an induction technique similar to the section on linear recurrences above.
From linear algebra, we can use the following vector space decomposition theorem. Let be a linear operator for a vector spaces over a field . Suppose that there exists a polynomial such that , where and are non-zero polynomials such that , and such that . Then . This allows us to reduce the differential equation into finding the solutions to the equation , which has a basis of functions .
Problems
Introductory
Intermediate
- Let be the largest integer that satisfies all of the following conditions:
-
- (i) , for some positive integer ;
- (ii) , for some positive integer ;
- (iii) .
- Find the remainder when is divided by . (2007 iTest, #47)
- contains infinitely many natural numbers.
Olympiad
Hints/Solutions
Introductory
Intermediate
Olympiad
- Hint (WOOT): substitute the closed form solution. It is true for all .
- Hint (1976 Putnam A2): do the even and odd cases separately.
- <url>viewtopic.php?search_id=804457492&t=327474 Discussion</url> (2010 Chinese MO, 6)
Find Linear Reccurence Operator Given Solutions
Source: https://artofproblemsolving.com/wiki/index.php/Characteristic_polynomial