Math 540 - Solutions to Selcted HW Problems - ATLA C.1 – C.10

ATLA Problem # C.1: Let \(T\in\Lcal(V)\), and suppose that \(\bfv_1,\ldots,\bfv_n\) is a basis of eigenvectors for \(T\), say \[ T\bfv_1=\l_1\bfv_1,\quad T\bfv_2=\l_2\bfv_2,\ldots\quad T\bfv_n=\l_n\bfv_n. \] Some of the eigenvalues might be the same, so let \[ \mu_1,\mu_2,\ldots,\mu_k \] be a list of the distinct eigenvalues in the set \(\{\l_1,\l_2,\ldots,\l_n\}\). Let \(F(z)\) be the polynomial \[ F(z)=(z-\mu_1)(z-\mu_2)\ldots(z-\mu_k). \] Prove that \(F(T)=0\).

This shows that for some linear maps \(T\), there may be a non-zero polynomial \(F(z)\) with \(F(T)=0\) whose degree is smaller than the degree of \(P_T(z)\).
Solution: The proof is very similar to our proof of the Cayley-Hamilton theorem. If we use the basis of eigenvectors, then the matrix \(A\) of \(T\) is a diagonal matrix with \(\l_1,\ldots,\l_n\) on the diagonal. Then \[ F(A) = (A-\mu_1I)(A-\mu_2I)\ldots(A-\mu_kI) \] is a product of diagonal matrices, and the \(i\)'th entry on the diagonal is \[ (\l_i-\mu_1)(\l_i-\mu_2)\cdots(\l_i-\mu_k). \] Since \(\l_i\) is equal to one of \(\mu_1,\ldots,\mu_k\), we see that the \(i\)'th diagonal entry is \(0\), and since this is true for every \(i\), the matrix \(F(A)\) is the zero matrix.

ATLA Problem # C.2: Let \(B\) be the matrix \[ B = \begin{pmatrix} 0 & 0 & \dots & 0 & -c_0 \\ 1 & 0 & \dots & 0 & -c_1 \\ 0 & 1 & \dots & 0 & -c_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \dots & 1 & -c_{n-1} \end{pmatrix}. \] Prove that \[ \det(zI-B) = z^n + c_{n-1}z^{n-1} + \cdots + c_1z + c_0. \] This exercise shows that every monic polynomial is the characteristic polynomial of some matrix. The matrix \(B\) is often called the companion matrix to the polynomial.
Solution: We essentially did this in class.

ATLA Problem # C.3: We have seen that the set of linear maps \(\Lcal(V)\) is a vector space. Let \(T\in\Lcal(V)\), and for each \(k=1,2,3,\ldots\), let \[ U_k = \operatorname{Span}(I,T,T^2,\ldots,T^k) \subset \Lcal(V). \] So \(U_k\) is a subspace of \(\Lcal(V)\), and clearly \(\dim(U_k)\le k+1\), since it has a spanning set consisting of \(k+1\) vectors. Prove that \[ \dim(U_k) \le \dim(V) \quad\text{for all \(k\).} \]
Solution: Let \(n=\dim(V)\) and let \(k\ge n-1\). We claim that \(I,T,T^2,\ldots,T^{n-1}\) spans \(U_k\). To see this, we use induction on \(k\) and the Cayley-Hamilton theorem. For \(k=n-1\), the claim is true by definition of \(U_k\). So we now assume that it is true for all values strictly smaller than \(k\), and we consider \(U_k\). The Cayley-Hamilton theorem says that \(T\) satisfies its characteristic polynomial \[ P_T(z) = z^n + c_1z^{n-1} + c_2z^{n-2} + \cdots + c_{n-1}z + c_n. \] Hence \[ A^n = - c_1A^{n-1} - c_2A^{n-2} - \cdots - c_{n-1}A - c_n. \] Multiplying by \(A^{k-n}\), we find that \begin{align*} A^k &= - c_1A^{k-1} - c_2A^{k-2} - \cdots - c_{k-n+1}A - c_nA^{k-n} \\ &\in \operatorname{Span}(A^{k-1},A^{k-2},\ldots,A^{k-n}) \\ &\subset \operatorname{Span}(I,T,T^2,\ldots,T^{n-1}) \quad\text{by the induction hypothesis.} \end{align*} Since the induction hypothesis also says that \[ U_{k-1} \subset\operatorname{Span}(I,T,T^2,\ldots,T^{n-1}), \] this proves the \[ U_k = \operatorname{Span}(A^k)+U_{k-1} \subset\operatorname{Span}(I,T,T^2,\ldots,T^{n-1}). \]

ATLA Problem # C.4: If \(T\in\Lcal(V)\) is a nilpotent, prove that \(0\) is the only eigenvalue of \(T\).
Solution: Let \(T\bfv=\l\bfv\) with \(\bfv\ne0\). Since \(T\) is nilpotent, we have \(T^k=0\) for some \(k\). Apply \(T^k\) to \(\bfv\) gives \[ 0 = T^k\bfv = \l^k\bfv, \] so \(\l^k=0\), hence \(\l=0\).

ATLA Problem # C.5: Let \(n=\dim(V)\) and let \(T\in\Lcal(V)\) be a nilpotent linear map. Prove that \(T^n=0\). (By definition, the fact that \(T\) is nilpotent means that \(T^j=0\) for some \(j\). This exercise asks you to prove that it suffices to take \(j=n\).)
Solution: By definition, there is some \(j\ge1\) such that \(T^j=0\). Using the Jordan normal form theorem, we can find a basis for \(B\) so that the matrix \(A=\mathcal{M}(T,\mathcal{B})\) is in block form with Jordan blocks \(J_{m_1}(\l_1),\ldots,J_{m_r}(\l_r)\). Then \(A^j\) is in block form with Jordan blocks \(J_{m_1}(\l_1)^j,\ldots,J_{m_r}(\l_r)^j\), so we must have \[ J_{m_1}(\l_1)^j=\cdots=J_{m_r}(\l_r)^j=0. \] But in general, \(J_m(\l)^j\) is an upper triangular matrix with \(\l^j\) on the diagonal, so the only way to get \(J_m(\l)^j=0\) is to have \(\l=0\). (Alternatively, from Problem C.4, \(0\) is the only eigenvalue of \(T\), so \(\l_1=\cdots=\l_r=0\).)

So we now know that \(A\) is in block form with Jordan blocks \(J_{m_1}(0),\ldots,J_{m_r}(0)\). We proved in class that \(J_m(0)^m=0\). (The matrix \(J_m(0)\) is what we called \(N\).) Since \(A\) is an \(n\)-by-\(n\) matrix, where \(n=\dim(V)\), we certainly have \(m_i\le n\), so \(J_{m_i}(0)^n=0\). Hence \(A^n=0\), since \(A^n\) is in block form with Jordan blocks \(J_{m_1}(0)^n,\ldots,J_{m_r}(0)^n\).

ATLA Problem # C.6: Let \(J=J_m(\l)\) be a Jordan block matrix, and let \(\bfe_m=(0,0,\ldots,0,1)\) be the last vector in the standard basis for \(\FF^m\). Prove that \[ \bigl\{\bfe_m,J\bfe_m,J^2\bfe_m,\ldots,J^{m-1}\bfe_m\bigr\} \] is a basis for \(\FF^m\).
Solution: Let \[ \bfv_0=\bfe_m,\quad \bfv_1=J\bfe_m,\quad \bfv_2=J^2\bfe_m,\ldots, \bfv_{n-1}=J^{m-1}\bfe_m. \] Claim. \[ \bfv_i = \bfe_{m-i} + \text{an element of Span\((\bfe_{m-i+1},\ldots,\bfe_m)\)}. \] We prove the claim by induction. For \(i=0\), we have \(\bfv_0=\bfe_m\), so \(i=0\) is okay. Assume now that it is true for \(i\). Then \begin{align*} \bfv_{i+1} &= J\bfv_{i} \\ &\in J( \bfe_{m-i} + \operatorname{Span}(\bfe_{m-i+1},\ldots,\bfe_m) ) \quad\text{by the induction hypothesis,} \\ &= J\bfe_{m-i} + \operatorname{Span}(J\bfe_{m-i+1},\ldots,J\bfe_m) \\ &= (\bfe_{m-i-1} + \l \bfe_{m-i}) + \operatorname{Span}(\bfe_{m-i}+\l\bfe_{m-i+1},\ldots, \bfe_{m-1}+\l\bfe_m) \quad\text{definition of \(J_m(\l)\),} \\ &\in \bfe_{m-i-1} + \operatorname{Span}(\bfe_{m-i},\ldots,\bfe_m) . \end{align*} This completes the proof of the claim.

Using the claim, we can express the vectors \(\bfv_1,\ldots,\bfv_m\) in terms of the standard basis vectors (in reverse order) by the formula \[ [\bfv_1 | \bfv_2 | \cdots | \bfv_m ] = [\bfe_m | \bfe_{m-1} | \cdots | \bfe_1 ] \begin{pmatrix} 1 & * & * & \cdots & * \\ 0 & 1 & * & \cdots & * \\ 0 & 0 & 1 & \cdots & * \\ \vdots & & & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & 1 \\ \end{pmatrix} \] The upper triangular matrix with \(1\)'s on the diagonal is invertible (its determinant is 1), which shows that we can write \(\bfe_1,\ldots,\bfe_m\) as linear combinations of \(\bfv_1,\ldots,\bfv_m\). Hence \(\bfv_1,\ldots,\bfv_m\) span \(\FF^m\), and since there are \(m\) vectors, they form a basis.

ATLA Problem # C.7: In 1202 Leonardo of Pisa (also known as Leonardo Fibonacci) published his \textit{Liber Abbaci}, a highly influential book of practical mathematics. In this book Leonardo posed the following Rabbit Problem.

In the first month, start with a pair of baby rabbits. One month later they have grown up. The following month the pair of grown rabbits produce a pair of babies, so now we have one pair of grown rabbits and one pair of baby rabbits. Each month thereafter, each pair of grown rabbits produces a new pair of babies, and every pair of baby rabbits grows up. How many pairs of rabbits will there be at the end of one year?

ATLA Problem # C.8(a,d,f): Use Binet's formula to prove that the Fibonacci sequence satisfies the following formulas.

(a) \(F_{n+1}F_{n-1}-F_n^2=(-1)^n\).

(d) \(\displaystyle \sum_{n=1}^k F_n = F_{k+2}-1\).

(f) Prove that at least one of the numbers \(5F_n^2+4\) and \(5F_n^2-4\) is a perfect square.
Solution: We let \(\a=(1+\sqrt5)/2\) and \(\b=(1-\sqrt5)/2\). We will make use of the formulas \[ \a^2=\a+1,\quad\b^2=\b+1,\quad\a+\b=1,\quad\a-\b=\sqrt5,\quad \a\b=-1. \] Binet's formula says that \[ F_n = \frac{\a^n-\b^n}{\sqrt5} = \frac{\a^n-\b^n}{\a-\b}. \]

(a) We compute \begin{align*} F_{n+1}F_{n-1}-F_n^2 &= \left(\frac{\a^{n+1}-\b^{n+1}}{\sqrt5}\right) \left(\frac{\a^{n-1}-\b^{n-1}}{\sqrt5}\right) - \left(\frac{\a^{n}-\b^{n}}{\sqrt5}\right)^2 \\ &= \frac{ \a^{2n} - \a^{n+1}\b^{n-1} - \a^{n-1}\b^{n+1} - \b^{2n} }{5} - \frac{ \a^{2n} - 2\a^n\b^n + \b^{2n} }{5} \\ &= \frac{ - \a^{n+1}\b^{n-1} - \a^{n-1}\b^{n+1} + 2\a^n\b^n }{5} \\ &= - (\a\b)^{n-1} \frac{\a^2+\b^2-2\a\b}{5} \\ &= (-1)^n \frac{(\a-\b)^2}{5} \\ &= (-1)^n. \end{align*}

(d) We compute (using the formula \(\sum_{n=1}^k r^n = r(r^k-1)/(r-1)\) that gives the partial sum of a geometric series): \begin{align*} \sum_{n=1}^k F_n &= \sum_{n=1}^k \frac{\a^n-\b^n}{\sqrt5} \\ &= \frac{1}{\sqrt5} \left( \a \frac{\a^k-1}{\a-1} - \b \frac{\b^k-1}{\b-1} \right) . \end{align*} We're going to put the fractions over a common denominator \[ (\a-1)(\b-1)=\a\b-\a-\b+1=(\a\b+1)-(\a+\b)=-1. \] Hence \begin{align*} \sum_{n=1}^k F_n &= \frac{1}{\sqrt5} \Bigl( -\a(\a^k-1)(\b-1) + \b(\b^k-1)(\a-1) \Bigr) \\ &= \frac{1}{\sqrt5} \Bigl( (\a^k-1)(1+\a) - (\b^k-1)(1+\b) \Bigr) \quad\text{using \(\a\b=-1\),} \\ &= \frac{1}{\sqrt5} \Bigl( (\a^k-1)\a^2 - (\b^k-1)\b^2 \Bigr) \quad\text{using \(\a^2=\a+1\) and \(\b^2=\b+1\),} \\ &= \frac{\a^{k+2}-\b^{k+2}}{\sqrt5} - \frac{\a^{2}-\b^{2}}{\sqrt5} \\ &= F_{k+2} - F_2 \\ &= F_{k+2} -1. \end{align*} (Remark It's probably easier to prove this formula by induction!)

(f) Binet's formula gives \begin{align*} 5F_n^2\pm4 &= 5\left(\frac{\a^n-\b^n}{\sqrt5}\right)^2 \pm 4 \\ &= \a^{2n} - 2\a^n\b^n + \b^{2n} \pm 4 \\ &= \a^{2n} - 2(-1)^n + \b^{2n} \pm 4 \quad\text{using \(\a\b=-1\).} \end{align*} So if \(n\) is even, then \[ 5F_n^2 + 4 = \a^{2n} - 2 + \b^{2n} + 4 = \a^{2n} + 2 + \b^{2n} = \a^{2n} + 2\a^n\b^n + \b^{2n} = (\a^n+\b^n)^2. \] Similarly, if \(n\) is odd, then \[ 5F_n^2 + 4 = (\a^n-\b^n)^2. \] It remains to show that if \(n\) is even, then \(\a^n+\b^n\) is an integer, and if \(n\) is odd, then \(\a^n-\b^n\) is an integer. I'll do the case that \(n\) is even; the case that \(n\) is odd is proven similarly.

One proof method is to use the binomial formula to expand the powers of \(\a\) and \(\b\). We write \(n=2m\), since we are assuming that \(n\) is even. Then \begin{align*} \a^n+\b^n &= \a^{2m}+\b^{2m} \\ &= \left(\frac{1+\sqrt5}{2}\right)^{2m} + \left(\frac{1-\sqrt5}{2}\right)^{2m} \\ &= \frac{1}{2^{2m}} \left( \sum_{i=0}^{2m} \binom{{2m}}{i} (\sqrt5)^i + \sum_{i=0}^{2m} \binom{{2m}}{i} (-\sqrt5)^i \right) \\ &= \frac{1}{2^{2m}} \sum_{j=0}^{m} 2\binom{{2m}}{2j} (\sqrt5)^{2j} \quad\text{since the terms with \(i\) odd cancel,} \\ &= \frac{1}{2^{2m}} \sum_{j=0}^{m} 2\binom{{2m}}{2j}5^j. \end{align*} This at least shows that \(\a^n+\b^n\) is a rational number. But when we square it, we get the integer \(5F_n^2+4\), so when we write \(\a^n+\b^n\) in lowest terms, it can't have a denominator, since otherwise when we squared it, it would still have a denominator. Hence \(\a^n+\b^n\) is an integer, and then \(5F_n^2+4=(\a^n+\b^n)^2\) is the square of an integer.

ATLA Problem # C.9(a,c): Find a closed form solution for each of the following linear recursions.

(a) \( a_1=1,\quad a_2=3,\quad a_n=a_{n-1}+a_{n-2}. \) This is called the Lucas sequence.

(c) \( a_1=6,\quad a_2=-14,\quad a_n=6a_{n-1}-25a_{n-2}. \)
Solution: Here are the answers. The calculations are the same as the ones we did to find Binet's formula

(a) \(a_n = \left(\frac{1+\sqrt5}{2}\right)^n + \left(\frac{1-\sqrt5}{2}\right)^n\).

(c) \(a_n = (3+4i)^n + (3-4i)^n\).

ATLA Problem # C.10: Suppose that \(a_1,a_2,a_3,\ldots\) is a linear recursion associated to a non-zero linear function \[ L(x_1,\ldots,x_d) = c_1x_1+c_2x_2+\cdots+c_dx_d, \] let \[ F(z) = z^d - c_1z^{d-1} - \cdots - c_{d-1}z - c_d \] be the associated polynomial, and suppose that \(F(z)\) factors over \(\mathbb{C}\) as \[ F(z)=(z-\l_1)(z-\l_2)\cdots(z-\l_d). \] Suppose further that \[ |\l_1| > |\l_2| > |\l_3| > \cdots > |\l_d|. \]

(a) Prove that the limit \[ \lim_{n\to\infty} |a_n|^{1/n} \qquad\qquad(*) \] exists and is equal to one of the numbers \(|\l_1|,|\l_2|,\ldots,|\l_d|\).

(b) Why doesn't the limit \((*)\) have to equal \(|\l_1|\). Give an example with \(d=2\) where the limit \((*)\) is equal to \(|\l_2|\).

(c) What might go wrong if \(|\l_1|=|\l_2|\)? For example, consider the linear recursion \[ a_1=6,\quad a_2=-14,\quad a_n=6a_{n-1}-25a_{n-2}. \] Does the limit \(\lim_{n\to\infty} |a_n|^{1/n}\) even exist? (This is hard.)
Solution: (a) From our general procedure, we know that there are numbers \(b_1,\ldots,b_d\) such that \[ a_n = b_1\l_1^n+b_2\l_2^n+\cdots+b_d\l_d^n \quad\text{for all \(n\ge1\).} \] It's also certainly true that \(\l_1^n\) grows much faster than \(\l_2^n\). However, it might happen that \(b_1=0\), in which case the \(\l_1^n\) terms doesn't appear! In general, if we choose \(i\) to be the smallest index such that \(b_i\ne0\), then \begin{align*} \lim_{n\to\infty} |a_n|^{1/n} &= \lim_{n\to\infty} |b_i\l_i^n+b_{i+1}\l_{i+1}^n+\cdots+b_d\l_d^n|^{1/n}\\ &= |\l_i| \lim_{n\to\infty} \left|b_i +b_{i+1}\left(\frac{\l_{i+1}}{\l_i}\right)^n+\cdots +b_{d}\left(\frac{\l_{d}}{\l_i}\right)^n \right|^{1/n} \\ &= |\l_i| \quad\text{since \(b_i\ne0\), and \(|\l_j/\l_i|\lt 1\) for all \(j\gt i\).} \end{align*}

(b) In the notation of (a), we just need to create a linear recursion where \(b_1=0\). The two-term linear recursion \(a_n=5a_{n-1}-6a_{n-2}\) has eigenvalues \[ z^2-5z+6=(z-2)(z-3), \] so it looks like \(a_n=b_1\cdot3^n+b_2\cdot2^n\), but if we use the starting values \(a_1=2\) and \(a_2=4\), then we find that in fact \(a_n=2^n\) for all \(n\).

(c) The potential problem is that even though \(|\l_1^n|\) and \(|\l_2^n|\) are large, there might be a lot of cancelation. The example given is the sequence in problem C.9 that has the closed form \[ a_n = (3+4i)^n + (3-4i)^n. \] Since \[ |3+4i|=|3-4i|=5, \] it is hard to predict whether \(a_n\) is large. It turns out that one can prove that for this sequence, it is true that \(\lim_{n\to\infty} |a_n|^{1/n}=5\), but the proof is quite difficult.

And consider the recursion given by \(a_1=0\), \(a_2=4\), and \(a_n=a_{n-2}\). Then it's easy to check that the sequence looks like \(0,4,0,32,0,128,\ldots\), so \(\lim_{n\to\infty} |a_n|^{1/n}\) does not exist.

Return to the Math 540 Homework Page

Return to the Math 540 Home Page