Mathematics Extra Homework Questions Solutions

1. Let D ∈ Rn×n be a diagonal matrix D = diag (d1 , d2 , . . . , dn ). Prove that  k  d1 0 · · · 0  0 dk · · · 0  2   Dk = diag (dk1 , dk2 , . . . , dkn ) =  . .. .. ..  . . . . . . 0 0 ··· dkn Hint: one good way to do this is via induction. Solution: For k = 1, the statement is true trivially. We must therefore start our induction by proving the statement for the first non-trivial case k = 2. By matrix multiplication, we have     2  d1 0 · · · 0 d1 0 · · · 0 d1 0 · · · 0  0 d2 · · · 0   0 d2 · · · 0   0 d2 · · · 0  2      2 D =. .. .. ..   .. .. .. ..  =  .. .. .. ..  . . . . . .  . . . . . . . . 0 0 ··· dn 0 ··· 0 dn 0 0 ··· d2n So the statement is also true for k = 2. Suppose now that the statement is true for the case k = p, p > 2:   p d1 0 · · · 0  0 dp · · · 0  2   p D =. .. .. ..  . . . . . . 0 0 · · · dpn This is the inductive assumption. We need to show that the statement is true for the case k = p + 1. So Dp+1 = DDp  d1 0  =.  .. 0 0 ··· d2 · · · .. .. . . 0 ···  p 0 d1 0 · · ·  0 dp · · · 0 2  ..   .. .. ..   . . . . dn 0 0 ··· where we used the inductive assumption to get an expression for Dp .  p+1 d1 0 ··· 0 p+1  0 d2 ··· 0  Dp+1 =  . .. .. .. .  . . . . 0 0 ···  0 0  ..  , . dpn Thus,  dp+1 n   .  Thus, by mathematical induction, the statement is true for all k ≥ 1. 2. Let D ∈ Rn×n be a diagonal matrix D = diag (d1 , d2 , . . . , dn ). Prove that   exp(D) = diag ed1 , ed2 , . . . , edn . Solution: Recall that the exponential of a matrix D is given by ∞ X 1 1 1 k D = I + D + D2 + D3 + · · · exp(D) = k! 2! 3! k=0 Using our result from Question 1, we can write    1 0 ··· 0 d1 0 · · · 0 1 · · · 0  0 d2 · · ·    exp(D) =  . . .. ..  +  .. .. .. . . . . . .  . . . 0 0 ··· 1 0 0 ···  2  d1 0 · · · 0   0  1  0 d22 · · · .. .. ..  +  .. . . .  2!  . 0 0 ··· dn  0 0  ..  + · · · . d2n Notice that the only non-zero entries occur on the main diagonal. That is, all entries away from the main diagonal will be zero. Thus, we have   1 + d1 + 2!1 d21 + · · · 0 ··· 0   0 1 + d2 + 2!1 d22 + · · · · · · 0   exp(D) =   .. .. .. ..   . . . . 0 0 · · · 1 + dn + 2!1 d2n + · · · Now observe that the first entry on the main diagonal is the Taylor series expansion (about d1 = 0) for ed1 . Similarly, the second entry on the main diagonal is the Taylor series expansion for ed2 and so on. Thus,  d  e 1 0 ··· 0  0 ed2 · · · 0    exp(D) =  . . . ..  . . . .  . . . .  0 0 ··· edn       u1 v 3. Let λ1 , and λ2 , 1 be the eigenvalue-eigenvector pairs of A ∈ R2×2 and suppose u2 v2   u1 v1 −1 λ1 6= λ2 . Then A can be diagonalized. That is, A = P DP , where P = is the matrix of u2 v2 eigenvectors and D = diag(λ1 , λ2 ) is the diagonal matrix of eigenvalues. The solution of the linear system of ODEs u̇ = Au, u ∈ R2 is given by u(t) = exp(At) u0   α where u0 = is the initial condition. Show (by matrix multiplication) that the solution u(t) can be β rewritten as u(t) = C1 v 1 eλ1 t + C2 v 2 eλ2 t , for some constants C1 and C2 . Write down the values of C1 and C2 in terms of u1 , u2 , v1 , v2 , α and β. Solution: This is just an exercise in matrix multiplication and algebra. We have u(t) = exp(At) = P exp(Dt)P −1 u0 ,   u1 v1 (see lectures for why this is so). We now write P = where det P 6= 0 (since the eigenvectors are u2 v2   λ1 0 linearly independent) and D = and do some serious algebra! 0 λ2 2   λ t    1 u1 v1 e 1 v2 −v1 0 u(t) = u0 u2 v2 0 eλ2 t det P −u2 u1    1 u1 v1 v2 eλ1 t −v1 eλ1 t = u0 −u2 eλ2 t u1 eλ2 t det P u2 v2    1 u1 v2 eλ1 t − v1 u2 eλ2 t −u1 v1 eλ1 t + u1 v1 eλ2 t α = λ1 t − u v eλ2 t −u v eλ1 t + u v eλ2 t β u v e det P 2 2 2 2 2 1 1 2

  1 u1 v2 eλ1 t − v1 u2 eλ2 t
α + −u1 v1 eλ1 t + u1 v1 eλ2 t
β = u2 v2 eλ1 t − u2 v2 eλ2 t α + −u2 v1 eλ1 t + u1 v2 eλ2 t β det P  λt  1 u1 e 1 (αv2 − βv1 ) + v1 eλ2 t (βu1 − αu2 ) = det P u2 eλ1 t (αv2 − βv1 ) + v2 eλ2 t (βu1 − αu2 )     αv2 − βv1 u1 λ1 t βu1 − αu2 v1 λ2 t = e + e u2 v2 det P det P Now, let C1 := αv2 −βv1 det P and C2 := βu1 −αu2 det P . Then  u(t) = C1    v u1 λ1 t e + C2 1 eλ2 t v2 u2 = C1 v 1 eλ1 t + C2 v 2 eλ2 t The point of this exercise is to show you that even though we can compute a general formula for the solution that always works, it’s much easier to just write down     v u1 λ1 t e + C2 1 eλ2 t u(t) = C1 v2 u2 as the general solution and work out what C1 and C2 need to be by substituting the initial condition. 4. We have seen that if the eigenvalues of A ∈ R2×2 are distinct, then the eigenvectors are linearly independent, we can diagonalize A and hence compute the solution u = exp(At)u0 of u̇ = Au. We now examine the scenario where we have a repeated eigenvalue. Consider the system dx = 5x − 4y, dt dy = 4x − 3y. dt As usual for linear systems, the general solution is     x(t) x(0) = exp(At) , y(t) y(0) where A is the Jacobian matrix. The computation of the matrix exponential will be a little more tricky. (i) Compute the eigenvalue λ and eigenvector v 1 of the Jacobian. (ii) Find a vector v 2 such that (A − λI) v 2 = v 1 . Such a v 2 is called a generalized eigenvector. 3 (1) (iii) Show that the vectors v 1 and v 2 are linearly independent. (iv) Let P = (v 1 v 2 ), where v 2 is the generalized eigenvector. Show that   λ 1 −1 P AP = . 0 λ The matrix J = P −1 AP is called the Jordan normal form of A. In this case, the best that the ‘diagonalization’ process can do is reduce the system to a diagonal matrix with 1s along the superdiagonal. (v) Show that   exp(λt) t exp(λt) exp (At) = P P −1 . 0 exp(λt) Hint: first show that  k J =  λk kλk−1 , 0 λk k ≥ 0. Note in this case that the two linearly independent solutions are exp(λt) and t exp(λt). (vi) Hence compute the general solution of (1). Solution:    1 . 1, 1   p . We want p, q such that (ii) Let v 2 = q (i) (λ, v) = (A − λI)     1 p . = 1 q That is, we are looking for a solution of the system of algebraic equations:      4 −4 p 1 = . 4 −4 q 1 Observe that the first and second rows are identical. That is, both equations tell us that 4p − 4q = 1. We have one equation for two variables (p and q), so there are infinitely many solutions to this problem. Let’s take q = 0 as our solution. In that case, p = 14 and 1 v2 = 4 0 . Note: you should check for yourself that (A − λI)v 2 gives v 1 . (iii) To check linear independence, we show that the determinant is non-zero:   1 1 1 14 = 1 × 0 − 1 × = − 6= 0. det 1 0 4 4 4 (iv) We have P −1  −1    1 14 5 −4 1 14 AP = 1 0 4 −3 1 0     1 1 0 −4 5 −4 1 41 = 4 −3 1 0 det P −1 1    1 1 0 −4 1 5/4 = −1 1 1 1 −1/4  1  1 − 4 − 41 = −1/4 0 − 14   1 1 = 0 1   λ 1 = , 0 λ where λ = 1. (v) We now need to compute the matrix exponential: exp(At) = = ∞ X 1 n n A t n! n=0 ∞ X n=0 1 (P JP −1 )n tn n!   λ 1 −1 . So, where J = P AP = 0 λ ∞ X 1 exp(At) = P J n P −1 tn = P n! n=0 ∞ X 1 n n J t n! ! P −1 . n=0 Our task now is to get a general expression for J n . Observe that  λ 0  λ J 3 = JJ 2 = 0  λ J 4 = JJ 3 = 0 J 2 = JJ =     2 λ 1 λ 2λ = 0 λ 0 λ2   2   3 λ 2λ λ 3λ2 1 = 0 λ2 0 λ3 λ  3    1 λ 3λ2 λ4 4λ3 = . 0 λ4 λ 0 λ3 1 λ Hopefully, you can see the pattern. Note that this does not constitute a proof. Our calculations suggest that we should guess  n  λ nλn−1 n J = . 0 λn To formally prove this, we can use mathematical induction. I leave this as an exercise for you. Now, substituting our expression for J n into the matrix exponential calculation from before, we have   ! ∞ X 1 λn nλn−1 n exp(At) = P t P −1 . λn n! 0 n=0 5 Writing the sum out term-by-term gives          1 λ2 2λ1 2 1 λ3 3λ2 3 1 0 λ λ0 exp(At) = P + t+ t + t + · · · P −1 0 1 0 λ 2! 0 λ2 3! 0 λ3          1 λ2 t2 2λt2 1 λ3 t3 3λ2 t3 1 0 λt t =P + + + + · · · P −1 0 1 0 λt 0 λ2 t2 0 λ3 t3 2! 3!   t + 2!2 λt2 + 3!3 λ2 t3 + · · · 1 + λt + 2!1 λ2 t2 + 3!1 λ3 t3 + · · · P −1 =P 0 1 + λt + 2!1 λ2 t2 + 3!1 λ3 t3 + · · ·  λt  e t + 2!2 λt2 + 3!3 λ2 t3 + · · · =P P −1 , 0 eλt where we observe that the diagonal entries are the Taylor series expansions of eλt . The only term we need to deal with now is the (1, 2) entry:   2 2 3 2 3 2 3 2 2 t + λt + λ t + · · · = t 1 + λt + λ t + · · · 2! 3! 2! 3!   1 2 2 = t 1 + λt + λ t + · · · 2! = teλt . Hence, we have  exp(At) = P  eλt teλt P −1 , 0 eλt (vi) The general solution of (1) is     x(0) x(t) . = exp(At) y(0) y(t) Thus, using the result from the previous part, we have    t −1     1 14 e tet x(0) 1 14 x(t) . = 0 et y(0) 1 0 1 0 y(t) After some matrix multiplication, you will find that the result is       t  x(0) e (4t + 1) −4et t x(t) t 4t(x0 − y0 ) + x0 =e . = y(0) 4t(x0 − y0 ) + y0 4et t et (1 − 4t) y(t) 5. In this problem we’re going to explore some more functions of matrices. For a real number t, we have two different, but equivalent ways to define the trig functions sin(t) and cos(t), using either the Taylor series, or Euler’s formula: ∞ X (−1)k t2k+1 eit − e−it sin(t) = or sin(t) = (2k + 1)! 2i k=0 cos(t) = ∞ X (−1)k t2k k=0 or (2k)! cos(t) = eit + e−it . 2 It makes sense for us to do the same thing with matrices, either using the power series, or the matrix exponential. That is we can define the sine or cosine of a matrix using either of the above definitions. We have for any A ∈ Rn×n : sin(A) := cos(A) := eAi − e−Ai 2i or eAi + e−Ai 2 or sin(A) := cos(A) := ∞ X (−1)k A2k+1 k=0 ∞ X k=0 6 (2k + 1)! (−1)k A2k . (2k)! (i) For both sin(A) and cos(A) show that the two definitions are equivalent. (ii) Show that (as matrices now), sin2 (A) + cos2 (A) = In for any n × n matrix A. (iii) Show that d dt sin(At) = A cos(At), and that d dt cos(At) = −A sin(At). (iv) We now generalize simple harmonic motion to the n-dimensional case. Suppose that A ∈ Rn×n is invertible. Show that the solution of the initial value problem ẍ = −A2 x, x(0) = 0, ẋ(0) = x0 is given by x(t) = A−1 sin(At)x0 . Now show that the solution of the initial value problem ẍ = −A2 x, x(0) = x0 , ẋ(0) = 0 is given by x(t) = cos(At)x0 . Hint: it suffices to show that the given solutions satisfy the ODE and initial conditions. (v) Suppose that A ∈ Rn×n is invertible. Write ẍ = −A2 x as a 2n × 2n first order system of equations. Find the general solution. Hint: Let y be defined by ẋ = −Ay. Solution: (i) We will show that the two definitions for the sine of a matrix are equivalent: 1 (exp(Ai) − exp(−Ai)) 2i ! ∞ ∞ X 1 X 1 1 = (Ai)n − (−Ai)n 2i n! n! sin(A) := n=0 n=0 ∞ 1 X 1 n n A (i − (−i)n ) = 2i n! n=0 By Euler’s formula, we have eiθ = cos θ + i sin θ so that i = eiπ/2 and −i = e−iπ/2 . So in − (−i)n = einπ/2 − e−inπ/2 nπ nπ  nπ nπ  = cos + i sin − cos(− ) + i sin(− ) 2 2 2 2 nπ nπ  nπ nπ  + i sin − cos − i sin = cos 2 2 2 2 since cos and sin are even and odd functions, respectively. Thus, ( 0 for n = 2k, k ∈ Z (i.e., n even) 1 n nπ (i − (−i)n ) = sin = k 2i 2 (−1) for n = 2k + 1, k ∈ Z (i.e. n odd) . So all even terms drop out and only the odd powers make any contribution. Thus, substituting into our expression for sin(A), we have ∞ X (−1)k A2k+1 . sin(A) = (2k + 1)! k=0 Note: if you are not comfortable working with the sigma notation, then write out each series term-byterm and you will get the same result. I leave it to you as an exercise to show that the two definitions for the cosine of a matrix are equivalent. 7 (ii) 2  2 1 Ai 1 Ai −Ai −Ai (e − e ) + (e + e ) sin (A) + cos (A) = 2i 2

1 Ai

1 e + e−Ai eAi + e−Ai = − eAi − e−Ai eAi − e−Ai + 4 4
1 Ai Ai Ai −Ai −Ai Ai =− e e −e e − e e + e−Ai e−Ai 4
1 Ai Ai e e + eAi e−Ai + e−Ai eAi + e−Ai e−Ai + 4  1  1  2Ai =− e − 2e(A−A)i + e−2Ai + e2Ai + 2e(A−A)i + e−2Ai 4 4
1 2Ai
1 2Ai −2Ai =− e − 2In + e + e + 2In + e−2Ai , 4 4 2 2  since the matrix exponential of the zero matrix is the identity matrix. Hence, we have sin2 (A) + cos2 (A) = In . (iii) We first note that d dt exp(At) = A exp(At) (as proved in lectures). d d 1 sin(At) = (exp(Ait) − exp(−Ait)) dt dt 2i 1 (Ai exp(Ait) − (−Ai) exp(−Ait)) = 2i 1 = A (exp(Ait) + exp(−Ait)) 2 = A cos(At). I leave showing d dt cos(At) = −A sin(At) as an exercise for you. (iv) Let x(t) = A−1 sin(At)x0 . Then d d x(t) = A−1 sin(At)x0 = A−1 A cos(At)x0 = cos(At)x0 dt dt d d2 x(t) = cos(At)x0 = −A sin(At)x0 = −A2 A−1 sin(At)x0 . =⇒ dt2 dt That is, ẍ = −A2 x. Now to check the initial conditions: x(0) = A−1 sin(0)x0 = A−1 0x0 = 0 ẋ(0) = cos(0)x0 = x0 . Note that we used the fact that sin(0) is the zero matrix and cos(0) is the identity matrix. Again, I leave the rest of the question as an exercise for you. (v) Let ẋ = −Ay so that y = −A−1 ẋ. Then dy d = (−A−1 ẋ) = −A−1 ẍ = −A−1 (−A2 x) = Ax. dt dt Thus, the second order equation ẍ = −A2 x can be rewritten as the linear system dx = −Ay dt dy = Ax dt 8 Note that we can write this in an even more compact form:     x 0n −A u̇ = M u, u= , M= , y A 0n where x ∈ Rn , y ∈ Rn , 0n denotes the n × n zero matrix and A ∈ Rn×n . Note that each entry of the matrix M is itself an n × n matrix. Each entry of M is called a block. Now, we have a linear system of ODEs and as usual, the solution is a matrix exponential: u(t) = exp(M t) u0 . We now compute exp(M t) using the power series definition of the matrix exponential. Let In denote the n × n identity matrix. Then: exp(M t) = I2n + M t + 1 1 1 1 2 2 M t + M 3 t3 + M 4 t4 + M 5 t5 + · · · 2! 3! 4! 5! Before we proceed, let’s compute the various powers of M and see if some kind of pattern emerges:   In 0n 0 M = 0n In   0n −A 1 M = A 0n      0n −A 0n −A −A2 0n M2 = = A 0n A 0n 0n −A2       −A2 0n 0n −A 0 n A3 3 2 M =M M = = A 0n −A3 0n 0n −A2       A4 0n 0n −A 0n A3 4 3 = M =M M = A 0n 0 n A4 −A3 0n Can you see the pattern? Notice that M 4 = diag (A4 , A4 )I2n so that M 5 = diag (A4 , A4 ) M M 6 = diag (A4 , A4 ) M 2 M 7 = diag (A4 , A4 ) M 3 M 8 = diag (A4 , A4 ) M 4 = diag (A4 , A4 ) diag (A4 , A4 )I2n = diag (A8 , A8 )I2n . That is, after every 4th power of M , the cycle repeats itself. Now, substituting into our matrix exponential calculation, we get      1 2 2    1 3 3 In 0n 0n −At − 2! A t 0n 0n A t 3! exp(M t) = + + + 0n In At 0n 0n − 1 A2 t 2 − 3!1 A3 t3 0n 1 4 4   4   2!   4   2 1 1 A t 0 A 0 0 −A A 0 −A 0 n n n n n 5 + 4! t + t6 + · · · 1 4 4 + 4 4 A t 0 A A 0 0 A 0 −A 0n 5! 6! n n n n   4!   1 2 2    1 3 3 In 0n 0n −At − 2! A t 0n 0n A t 3! = + + + 0n In At 0n 0n − 2!1 A2 t2 − 3!1 A3 t3 0n 1 4 4      1 5 5 1 6 6 A t 0n 0n − 5! A t − 6! A t 0n + 4! + 1 4 4 + 1 5 5 1 6 6 + ··· 0n 0n 0n 4! A t 5! A t 6! A t   1 2 2 1 4 4 1 6 6 1 3 3 1 5 5 In − 2! A t + 4! A t − 6! A t + · · · −At + 3! A t − 5! A t + 7!1 A7 t7 + · · · = At − 3!1 A3 t3 + 5!1 A5 t5 − 7!1 A7 t7 + · · · In − 2!1 A2 t2 + 4!1 A4 t4 − 6!1 A6 t6 + · · · 9 Now, if you stare at the diagonal entries for long enough, you may recognise that they are the power series expansions of cos(At). Similarly, the off-diagonal elements are the power series expansions of ± sin(At). Thus, we have   cos(At) − sin(At) exp(M t) = . sin(At) cos(At) And now we can finally compute the general solution:     x(t) x0 = exp(M t) y(t) y0    cos(At) − sin(At) x0 = sin(At) cos(At) y0   cos(At)x0 − sin(At)y 0 = sin(At)x0 + cos(At)y 0 This is the n-dimensional simple harmonic oscillator (any physicists or engineers out there?). As a further exercise, you should compute the general solution of ẍ = −a2 x, x ∈ R, a ∈ R and compare it with the result above. 6. The Fibonacci sequence is the sequence of numbers obtained by writing down 1 twice, and obtaining each successive number by adding the previous two numbers together: 1, 1, 2, 3, 5, 8, 13, 21, 32, 55, 89, 144, . . . If we let xn denote the nth Fibonacci number, then x1 = x2 = 1, xn = xn−1 + xn−2 for n ≥ 3. It is possible to show that a generating formula for xn and xn−1 is      n−2     1 1 xn 1 1 1 n−2 1 . , where M = =M = 1 0 xn−1 1 0 1 1 (2) (i). Find matrices P and D such that M = P DP −1 , where D is a diagonal matrix. (ii). Obtain a general formula for the nth Fibonacci number Hint: use (2) and part (i) to compute xn as a function of n. Solution: (i) The eigenvalue-eigenvector pairs are given by √    √ 1 1+ 5 (λ1 , v 1 ) = (1 + 5), 2 2 √    √ 1 1− 5 (λ2 , v 2 ) = (1 − 5), 2 2 Let P be the matrix of eigenvectors P = (v 1 v 2 ) and D = diag (λ1 , λ2 ). Then we are guaranteed that M = P DP −1 , by the eigendecomposition theorem, since the eigenvalues are distinct (i.e. λ1 6= λ2 ). 10 (ii) To get the nth Fibonacci number, we need to compute the M n−2 . So, let’s compute M k for some k: M k = (P DP −1 )k = P Dk P −1 √ √  1 √ −1 √ √ k   (1 + 5) 0√ 1+ 5 1− 5 1+ 5 1− 5 2 = 1 2 2 2 2 (1 − 5) 0 √ k2 √  √ √  1    1 5) 0√ 2 −1 +√ 5 1+ 5 1− 5 k (1 + 2 √ = . 1 2 2 0 (1 − 5)k 4 5 −2 1 + 5 2k Now after lots of matrix multiplication and algebra, we get “  −k−1 “ √ k+1  √ k+1 ” √ k √ k” 2 2−k (1+ 5) −(1− 5) (1+ 5) −(1− 5) √ √   5 “ √ √ k5 √ √ k”  . Mk =  √ √ k k −k−1 1 1 2 (1+ 5)(1− 5) +(−1+ 5)(1+ 5) ( 2 (1+ 5)) −( 2 (1− 5)) √ √ 5 5 Thus, to get M n−2 , we simply replace k by n−2 in the above. Finally, to get the solution, we substitute M n−2 into (2):     xn n−2 1 , =M 1 xn−1 where  M n−2 =  √ n √ √ n √ 2−2n−1 (1+ 5) ((1+ 5)(−3+ 5) +2n (−1+ 5)) √ √ n √ 5 √ n √ 2−2n−1 (1+ 5) ((3+ 5)(−3+ 5) +2n (−3+ 5)) √ − 5 − √ √ n √ √ n 2−n−1 ((3+ 5)(1− 5) +(−3+ 5)(1+ 5) ) √ √ √ n 5 √ √ n 2−n ((2+ 5)(1− 5) +(−2+ 5)(1+ 5) ) √ 5 Multiplying this out and simplifying, we get:   √ n √ n   4−n ((2(1+ 5)) −(2−2 5) ) √ xn 5  . = √ √
n−1 
√
n √ 1 −n xn−1 5+3 5 5 − 3 + 52n+1 4 1+ 5 5 Thus, the formula for the nth element of the Fibonacci sequence is: xn = √ n  √ n o 1 n √ 1+ 5 − 1− 5 2n 5 Think about this result for a second: the Fibonacci sequence √is a bunch of integers and yet, the formula th for the n term involves irrational factors, i.e. factors of 5. Somehow, miraculously, the factors of √ 5 cancel and every term of this formula works out to be an integer! Here are the first 30 terms of the Fibonacci sequence according to our formula: {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040} 11  .