Solutions — Chapter 10
10.1.1.
(a)u(1) = 2, u(10) = 1024, u(20) = 1048576; unstable.
10.1.2.
(a)u(k+1) = 1.0325 u(k),u(0) = 100, where u(k)represents the balance after kyears.
(b)u(10) = 1.032510 ×100 = 137.69 dollars.
10.1.4. The balance after kyears coming from compounding ntimes per year is
„1 + r
n«n k a−→ er k aas n→ ∞, by a standard calculus limit, [2,58].
10.1.6. The solution u(k)=λku(0) is periodic of period mif and only if λm= 1, and hence λis
♠10.1.7. Let λ=eiθwhere 0 ≤θ < 2π. The solution is then u(k)=a λk=a e ik θ. If θis
a rational multiple of π, the solution is periodic, as in Exercise 10.1.6. When θ/π is irra-
tional, the iterates eventually fill up (i.e., are dense in) the circle of radius |a|in the com-
plex plane.
10.1.9. The equilibrium solution is u⋆=c/(1 −λ). Then v(k)=u(k)−u⋆satisfies the homo-
geneous system v(k+1) =λ v(k), and so v(k)=λkv(0) =λk(a−u⋆). Thus, the solution
10.1.10. Let u(k)represent the balance after kyears. Then u(k+1) = 1.05 u(k)+ 120, with
u(0) = 0. The equilibrium solution is u⋆=−120/.05 = −2400, and so after kyears the
balance is u(k)= (1.05k−1) ·2400. Then
u(10) = $1,509.35, u(50) = $25,121.76, u(200) = $4,149,979.40.
♥10.1.12. The overall yearly growth rate is 1.2−.05 = 1.15, and so the deer population satisfies
the iterative system u(k+1) = 1.15 u(k)−3600, u(0) = 20000. The equilibrium is u⋆=
10.1.13.
(a)u(k)=3k+ (−1)k
2, v(k)=−3k+ (−1)k
2.
10.1.14.
(a)u(k)=c1(−1−√2)k −√2
1!+c2(−1 + √2)k √2
1!;
10.1.15. (a) It suffices to note that the Lucas numbers are the general Fibonacci numbers (10.16)
10.1.16.
The second summand satisfies ˛˛˛˛˛˛˛−1
√50
@1−√5
21
A
k˛˛˛˛˛˛˛
< .448×.62k< .5 for all k≥0. Since
10.1.18.
(a) 5 2
2 2 !k
= 2−1
1 2 ! 6k0
0 1 !0
@
2
51
5
−1
52
51
A,
1 1 1
0 0 (−1)k
−1
201
2
(e)0
B
@
0 1 0
0 0 1
−1 0 2 1
C
A
k
=
280
1 1 1
−1
10.1.20. (a) Since the coefficient matrix Thas all integer entries, its product Tuwith any vec-
tor with integer entries also has integer entries; (b)c1=−2, c2= 3, c2=−3;
(c)u(1) =0
B
@
4
−2
−21
C
A,u(2) =0
B
@−26
10
−21
C
A,u(3) =0
B
@
76
−32
16 1
C
A,u(4) =0
B
@−164
76
−44 1
C
A,u(5) =0
B
@
304
−152
88 1
C
A.
10.1.21. The vectors u(k)=“u(k), u(k+1),…,u(k+j−1) ”T∈Rjsatisfy u(k+1) =Tu(k), where
10.1.22. (a)u(k)=4
3−1
3(−2)k,(b)u(k)=“1
3”k−1+“−1
4”k−1,
(c)u(k)=(5 −3√5)(2 + √5)k+ (5 + 3√5)(2 −√5)k
♣10.1.24.
(a)u(k)=u(k−1) +u(k−2) −u(k−8).
(b) 0,1,1,2,3,5,8,13,21,33,53,84,134,213,339,539,857,1363,2167, . . . .
(c)u(k)=“u(k), u(k+1), . . . , u(k+7) ”Tsatisfies u(k+1) =Au(k)where the 8 ×8 coeffi-
cient matrix Ahas 1’s on the superdiagonal, last row ( −1,0,0,0,0,0,1,1 ) and all other
entries 0.
281
♠10.1.27.
(a)
(b)
E1: principal axes: 1
0!, 0
1!, semi-axes: 1.2, .4, area: .48 π= 1.5080.
(c)
E1: principal axes: .6407
.7678 !, −.7678
.6407 !, semi-axes: 1.0233, .3909, area: .4π= 1.2566.
282
10.1.29. (a) This follows from Exercise 8.5.19(a) with A=Tn. (b) False; see Exercise 10.1.27(c)
for a counterexample. (c) False — the singular values of Tnare not, in general, the nth
powers of the singular values of T. (d) True, since the product of the singular values is the
absolute value of the determinant, and so An=π|det T|n.
10.1.33. According to Theorem 8.20, the eigenvectors of Tare real and form an orthogonal ba-
sis of Rnwith respect to the Euclidean norm. The formula for the coefficients cjthus fol-
lows directly from (5.8).
10.1.34. Since matrix multiplication acts column-wise, cf. (1.11), the jth column of the matrix
equation Tk+1 =T T kis c(k+1)
j=Tc(k)
j. Moreover, T0= I has jth column c(0)
j=ej.
10.1.35. Separating the equation into its real and imaginary parts, we find
♦10.1.36.
(a) Proof by induction:
(b) Each Jordan chain of length jis used to construct jlinearly independent solutions by
formula (10.23). Thus, for an n-dimensional system, the Jordan basis produces the re-
quired number of linearly independent (complex) solutions, and the general solution is
283
10.1.37.
(a)u(k)= 2k“c1+1
2k c2”, v(k)=1
32kc2;
(b)u(k)= 3k“c1+“1
0
B
B
B
B
B
B
λkk λk−1“k
2”λk−2“k
3”λk−3. . . “k
n−1”λk−n+1
0λkk λk−1“k
2”λk−2. . . “k
n−2”λk−n+2
1
C
C
C
C
C
C
10.1.39. (a) Yes, if Tis nonsingular. Indeed, in this case, the solution formula u(k)=Tk−k0u(k0)
is valid even when k < k0. But if Tis singular, then one can only assert that u(k)=e
u(k)
for k≥k0. (b) If Tis nonsingular, then u(k)=e
u(k−k0+k1)for all k; if Tis singular, then
this only holds when k≥max{k0, k1}.
♥10.1.40.
(a) The system has an equilibrium solution if and only if (T−I )u⋆=b. In particular, if 1
is not an eigenvalue of T, every bleads to an equilibrium solution.
(b) Since v(k+1) =Tv(k), the general solution is
284
(iv )u(k)=0
B
B
B
@
1
6
5
3
3
2
1
C
C
C
A+7
2“−1
2”k0
B
B
@
1
1
0
1
C
C
A−7
2“−1
3”k0
B
B
@
1
2
1
1
C
C
A+7
3“1
6”k0
B
B
@
0
1
2
1
1
C
C
A.
(d) In general, using induction, the solution is
♣10.1.41.
(a) The sequence is 3, 7, 0, 7, 7, 4, 1, 5, 6, 1, 7, 8, 5, 3, 8, 1, 9, 0, 9, 9, 8, 7, 5, 2, 7, 9, 6, 5,
1, 6, 7, 3, 0, 3, 3, 6, 9, 5, 4, 9, 3, 2, 5, 7, 2, 9, 1, 0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0,
and repeats when u(60) =u(0) = 3, u(61) =u1= 7.
10.2.1.
(a) Eigenvalues: 5+√33
2≈5.3723,5−√33
2≈ −.3723; spectral radius: 5+√33
2≈5.3723.
10.2.2.
(a) Eigenvalues: 2 ±3 i ; spectral radius: √13 ≈3.6056; not convergent.
10.2.3.
(a) Unstable: eigenvalues −1,−3;
10.2.4.
(a)λ1= 3, λ2= 1 + 2 i , λ3= 1 −2 i , ρ(T) = 3.
285
u(k)≈c1“3
5”k(−1,−1,1 )T.
10.2.5.
(a)Thas a double eigenvalue of 1, so ρ(T) = 1.
(b) Set u(0) = a
b!. Then Tk= 1k
0 1 !, and so u(k)= a+k b
b!→ ∞ provided b6= 0.
10.2.6. A solution u(k)→0if and only if the initial vector u(0) =c1v1+···+cjvjis a linear
combination of the eigenvectors (or more generally, Jordan chain vectors) corresponding to
eigenvalues satisfying |λi|<1 for i= 1, . . . , j.
♦10.2.8.
(a) Let u1,…,unbe a unit eigenvector basis for T, so kujk= 1. Let
mj= max n|cj|˛˛˛kc1u1+··· +cnunk ≤ 1o,
which is finite since we are maximizing a continuous function over a closed, bounded set.
10.2.9. Assume u(0) =c1v1+··· +cnvnwith c16= 0. For k≫0, u(k)≈c1λk
1v1since
|λk
1| ≫ |λk
j|for all j > 1. Thus, the entries satisfy u(k+1)
i≈λ1u(k)
iand so, if nonzero, are
signs alterate at each step of the iteration.
♥10.2.10. Writing u(0) =c1v1+··· +cnvn, then for k≫0,
u(k)≈c1λk
1v1+c2λk
2v2,(∗)
286
eigenvalues λ1, λ2are the roots of the quadratic equation λ2=aλ +b, which gives an effec-
tive algorithm for determining them. To prove the claim, for k≫0, by formula (∗),
10.2.11. If Thas eigenvalues λj, then cT +dI has eigenvalues cλj+d. However, it is not nec-
essarily true that the dominant eigenvalue of cT +dI is c λ1+dwhen λ1is the dominant
eigenvalue of T. For instance, if λ1= 3, λ2=−2, so ρ(T) = 3, then λ1−2 = 1, λ2=−4,
so ρ(T−2 I ) = 4 6=ρ(T)−2. Thus, you need to know all the eigenvalues to predict ρ(T),
or, more accurately, the extreme eigenvalues, i.e., those such that all other eigenvalues lie in
their convex hull in the complex plane.
♥10.2.14.
(a) The entries of u(k)are u(k)
i=
n
X
j= 1
cj β+ 2αcos j π
n+ 1 !k
sin ij π
n+ 1 , i = 1, . . . , n.
(b) The system is asymptotically stable if and only if
unstable.
10.2.16.
(a) False: ρ(c A) = |c|ρ(A).
(b) True, since the eigenvalues of Aand S−1AS are the same.
287
For the exclusive use of adopters of the book Applied Linear Algebra, by Peter J. Olver and Cheri Shakiban. ISBN 0-13-147382-4.
10.2.18. False. The first requires its eigenvalues satisfy Re λj<0; the second requires |λj|<1.
10.2.19. (a)A2=„lim
k→∞ Tk«2= lim
k→∞ T2k=A. (b) The only eigenvalues of Aare 1 and 0.
10.2.20. If vhas integer entries, so does Akvfor any k, and so the only way in which Akv→0
is if Akv=0for some k. Now consider the basis vectors e1, . . . , en. Let kibe such that
Akiei=0. Let k= max{k1, . . . , kn}, so Akei=0for all i= 1, . . . , n. Then AkI = Ak=
O, and hence Ais nilpotent. The simplest example is 0 1
0 0 !.
Thus, the quadratic eigenvalues are the same as the ordinary eigenvalues of C, and hence
stability requires they all satisfy |λ|<1.
♦10.2.22. Set σ=µ/λ > 1. If p(x) = ckxk+··· +c1x+c0has degree k, then p(n)≤ankfor all
♦10.2.24.
(a) Rewriting the system as u(n+1) =M−1u(n), stability requires ρ(M−1)<1. The eigen-
values of M−1are the reciprocals of the eigenvalues of M, and hence ρ(M−1)<1 if and
only if 1/|µi|<1 for all i.
288
10.2.25. (a) All scalar multiples of 1
1!; (b) 0
0!; (c) all scalar multiples of 0
B
@−1
−2
C
A;
10.2.26.
(a) The eigenvalues are 1,1
2, so the fixed points are stable, while all other solutions go to a
unique fixed point at rate “1
10.2.27. Since Tis symmetric, its eigenvectors v1,…,vnform an orthogonal basis of Rn. Writ-
ing u(0) =c1v1+···+cnvn, the coefficients are given by the usual orthogonality for-
mula (5.7): ci=u(0) ·vi/kv1k2. Moreover, since λ1= 1, while |λj|<1 for j≥2,
than 1 in modulus.
10.2.29. True. In this case Tu=ufor all u∈Rnand hence T= I .
♥10.2.30.
(a) The iterative system has a period 2 solution if and only if Thas an eigenvalue of −1.
Indeed, the condition u(k+2) =T2u(k)=u(k)implies that u(k)6=0is an eigenvector of
T2with eigenvalue of 1. Thus, u(k)is an eigenvector of Twith eigenvalue −1 because if
close to u⋆=v1, then |c1−1|,|c2|, . . . , |cn|< ε for εsmall. Then the corresponding
289
and hence any solution that starts near u⋆stays near.
(b) If Ahas an incomplete eigenvalue of modulus |λ|= 1, then, according to the solution
10.3.1. (a)3
4, convergent; (b) 3, inconclusive; (c)8
7, inconclusive; (d)7
4, inconclusive;
(e)8
7, inconclusive; (f).9, convergent; (g)7
3, inconclusive; (h) 1, inconclusive.
10.3.4. (a)kAkk∞=k2+k, (b)kAkk2=k2+ 1, (c)ρ(Ak) = 0. (d) Thus, a conver-
gent matrix can have arbitrarily large norm. (e) Because the norm in the inequality will
depend on k.
10.3.8. True: this implies kAk2= max σi<1.
10.3.9. For example, if A=0
@
1
21
01
21
A, then ρ(A) = 1
2. The singular values of Aare σ1=
√3+2 √2
2= 1.2071 and σ2=√3−2√2
2=.2071.
10.3.10.
290
♦10.3.12. (i) The 1 matrix norm is the maximum absolute column sum:
kAk1= max 8
<
:
n
X
i= 1 |aij |˛˛˛˛˛˛1≤j≤n9
=
;.
(ii ) (a)5
6, convergent; (b)17
6, inconclusive; (c)8
7, inconclusive; (d)11
4, inconclusive;
(e)12
7, inconclusive; (f).9, convergent; (g)7
3, inconclusive; (h)2
3, convergent.
♦10.3.14. kAk= max{σ1, . . . , σn}is the largest generalized singular value, meaning σi=qλi
where λ1,…,λnare the generalized eigenvalues of the positive definite matrix pair ATK A
and K, satisfying ATK Av=λ K vfor some v6=0, or, equivalently, the eigenvalues of
K−1ATK A.
10.3.15.
(a)kAk=7
2. The “unit sphere” for this norm is the rectangle with corners “±1
2,±1
3”T.
It is mapped to the parallelogram with corners ±“5
♥10.3.16. If we identify an n×nmatrix with a vector in Rn2, then the Frobenius norm is the
same as the ordinary Euclidean norm, and so the norm axioms are immediate. To check
the multiplicative property, let rT
1, . . . , rT
ndenote the rows of Aand c1, . . . , cnthe columns
291
10.3.17.
(a) This is a restatement of Proposition 10.28.
(b)kσk2
2=
n
X
i= 1
σ2
i=
n
X
i= 1
λi= tr(ATA) =
n
X
i,j = 1
a2
ij =kAk2
F.
10.3.18. If we identify a matrix Awith a vector in Rn2, then this agrees with the ∞norm on
10.3.19. First, if x= a
♦10.3.20.
(a) This follows from the formula (10.40) since |aij | ≤ si≤ kAk∞, where siis the ith
absolute row sum.
10.3.21. (a) Choosing a matrix norm such that a=kAk<1, the norm series is bounded by a
convergent geometric series:
∞
X
k k= 0
An≤∞
X
k k= 0
An=∞
X
n= 0
an=1
1−a.
292
10.3.22.
(a) Gerschgorin disk: |z−1| ≤ 2; eigenvalues: 3,−1;
-2 -1 1 2 3 4
-2
-1
1
2
1
(d) Gerschgorin disks: |z−3| ≤ 1, |z−2| ≤ 2;
eigenvalues: 4,3,1;
12 3 4
-2
-1
1
2
293
-2
(h) Gerschgorin disks: |z−3| ≤ 2, |z−2| ≤ 1, |z| ≤ 1,
|z−1| ≤ 2; eigenvalues: 1
2±√5
2,5
2±√5
2;-2 2 46
-3
-2
-1
1
2
3
10.3.23. False. Almost any non-symmetric matrix, e.g., 2 1
0 1 !provides a counterexample.
♦10.3.24.
(b) Gerschgorin disks: |z−1| ≤ 1
2,˛˛˛z+1
6˛˛˛≤2
3;
eigenvalues: 1
2,1
3;
-1 -0.5 0.5 1 1.5 2
-1
-0.75
-0.5
-0.25
0.25
0.5
0.75
1
3
294
(e) Gerschgorin disks: |z+ 1 | ≤ 2, |z−2| ≤ 4, |z+ 4 | ≤ 2;
eigenvalues: −2.69805 ±.806289,2.3961;
-8 -6 -4 -2 2 46 8
-4
-2
2
4
(h) Gerschgorin disks: |z−3| ≤ 1, |z−2| ≤ 2, |z| ≤ 2,
|z−1| ≤ 1; eigenvalues: 1
2±√5
2,5
2±√5
2;
-2 2 46
-3
-2
-1
1
2
3
10.3.26. (a) The absolute row sums of Aare bounded by si=
n
X
j= 1 |aij |<1, and so
295
© 2006 Pearson Education, Inc., Upper Saddle River, NJ. All rights reserved.
This material is protected under all copyright laws as they currently exist. No portion of this material may be reproduced,
in any form or by any means, without permission in writing from the publisher.
For the exclusive use of adopters of the book Applied Linear Algebra, by Peter J. Olver and Cheri Shakiban. ISBN 0-13-147382-4.
10.3.27. Using Exercise 10.3.25, we find ρ(A)≤s= max{s1,…,sn} ≤ n a⋆.
10.3.28. For instance, any diagonal matrix whose diagonal entries satisfy 0 <|aii |<1.
10.3.31.
10.3.32. The ith Gerschgorin disk is centered at aii <0 and, by diagonal dominance, its radius
10.4.1. (a) Not a transition matrix; (b) not a transition matrix; (c) regular transition ma-
trix: “8
17 ,9
17 ”T; (d) regular transition matrix: “1
6,5
6”T; (e) not a regular transition
10.4.2. (a) 20.5%; (b) 9.76% farmers, 26.83% laborers, 63.41% professionals
10.4.3. 2004: 37,000 city, 23,000 country; 2005: 38,600 city, 21,400 country; 2006: 39,880
10.4.4. 58.33% of the nights.
10.4.5. When in Atlanta he always goes to Boston; when in Boston he has a 50% probability of
going to either Atlanta or Chicago; when in Chicago he has a 50% probability of going to