1.5.26. Applying Gaussian Elimination:
E1=0
@1 0
−1
√311
A, E1A=0
B
@
√3
2−1
2
02
√3
1
C
A,
1.5.27. (a)0
@−i
2
1
2
1
2−i
21
A, (b) −1 1 −i
1 + i −1!,
1.5.28. No. If they have the same solution, then they both reduce to “I|x”under elementary
♥1.5.29.
(a) If e
A=ENEN−1··· E2E1Awhere E1, . . . , ENrepresent the row operations applied to
A, then e
C=e
A B =ENEN−1··· E2E1A B =ENEN−1··· E2E1C, which represents
1.5.30. (a)0
@
1
2
1
2
1
4−1
41
A 1
−2!=0
@−1
2
3
41
A; (b)0
@
5
17
2
17
−1
17
3
17 1
A 2
12 != 2
2!;
(g)0
B
B
B
B
B
@
1 1 0 1
−5
2−23
2−3
2
−4−3 2 −3
−1
2−11
2−1
2
1
C
C
C
C
C
A
0
B
B
B
B
B
@
−2
3
3
2
1
C
C
C
C
C
A
=0
B
B
B
B
B
@
3
1
2
−1
−3
2
1
C
C
C
C
C
A
.
8
1.5.32.
(a) 1 2
−3 1 != 1 0
−3 1 ! 1 0
0 7 ! 1 2
0 1 !;
(b) 0 1
1 0 ! 0 4
−7 2 != 1 0
0 1 ! −7 0
0 4 ! 1−2
7
0 1 !
(c)0
B
@
2 1 2
2 4 −1
C
A=0
B
@
1 0 0
1 1 0
C
A0
B
@
2 0 0
0 3 0
C
A0
B
@
11
21
0 1 −1
C
A;
1.5.33.
(a)0
@−3
7
5
71
A, (b) −8
3!, (c)0
B
B
B
@
1
6
−2
3
2
3
1
C
C
C
A, (d)0
B
@
1
−2
01
C
A, (e)0
B
@−12
−3
71
C
A, (f)0
B
B
B
B
@
7
3
2
5
−5
3
1
C
C
C
C
A, (g)0
B
B
B
@
0
1
0
−2
1
C
C
C
A.
22
(e)0
B
@
1
2
−31
C
A, (f) 135
2 4 6 !, (g)0
B
@
1 0 1
2 3 1
−1 2 5 1
C
A.
1.6.3. If Ahas size m×nand Bhas size n×p, then (AB)Thas size p×m. Further, AThas
size n×mand BThas size p×n, and so unless m=pthe product ATBTis not defined.
If m=p, then ATBThas size n×n, and so to equal (AB)T, we must have m=n=p,
so the matrices are square. Finally, taking the transpose of both sides, A B = (ATBT)T=
(BT)T(AT)T=B A, and so they must commute.
♦1.6.4. The (i, j) entry of C= (AB)Tis the (j, i) entry of AB, so
♦1.6.7. If A= a b
c d !, then ATA=AATif and only if b2=c2and (a−d)(b−c) = 0.
So either b=c, or c=−b6= 0 and a=d. Thus all normal 2 ×2 matrices are of the form
a b
b d !or a b
−b a !.
1.6.8.
(a) (AB)−T= ((AB)T)−1= (BTAT)−1= (AT)−1(BT)−1=A−TB−T.
1.6.9. If Ais invertible, then so is ATby Lemma 1.32; then by Lemma 1.21 A ATand ATAare
invertible.
1.6.10. No; for example, 1
2!( 3 4 ) = 3 4
6 8 !while 3
4!( 1 2 ) = 3 6
4 8 !.
23
all the entries in b
eT
iare zero except the ith entry, multiplication by the jth column of A
will produce aij .
♦1.6.13.
(a) Using Exercise 1.6.12, aij =eT
iAej=eT
iBej=bij for all i, j.
♦1.6.14.
(a) If pij = 1, then P A maps the jth row of Ato its ith row. Then Q=PThas qji = 1,
sin θcos θ!also has this property. See Section 5.3.
♦1.6.15.
(a) Note that (AP T)T=P AT, which permutes the rows of AT, which are the columns of
♥1.6.16.
(a) Note that w vTis a scalar, and so
1.6.17. (a)a= 1; (b)a=−1, b = 2, c = 3; (c)a=−2, b =−1, c =−5.
1.6.18.
(a)0
B
@
1 0 0
0 1 0
0 0 1 1
C
A,0
B
@
0 1 0
1 0 0
0 0 1 1
C
A,0
B
@
0 0 1
0 1 0
1 0 0 1
C
A,0
B
@
1 0 0
0 0 1
0 1 0 1
C
A.
24
♦1.6.21. False. For example 0 1
1 0 ! 2 1
1 3 != 1 3
2 1 !.
1.6.22.
(a) If Dis a diagonal matrix, then for all i6=jwe have aij =aji = 0, so Dis symmetric.
1.6.23.
(a) Since Ais symmetric we have (An)T= (AA . . . A)T=ATAT. . . AT=A A . . . A =An
1.6.24. If Ahas size m×n, then AThas size n×mand so both products are defined. Also,
KT= (ATA)T=AT(AT)T=ATA=Kand LT= (AAT)T= (AT)TAT=AAT=L.
1.6.25.
(a) 1 1
1 4 != 1 0
1 1 ! 1 0
0 3 ! 1 1
0 1 !,
1.6.26. M2= 1 0
1
21! 1 0
03
2!0
@11
2
0 1 1
A, M3=0
B
B
@
1 0 0
1
21 0
1
C
C
A0
B
B
@
200
03
20
1
C
C
A0
B
B
B
@
11
20
0 1 2
3
C
C
C
A,
♦1.6.27. The matrix is not regular, since after the first set of row operations the (2,2) entry is 0.
More explicitly, if
p ap bp
1
♦1.6.28. Write A=L D V , then AT=VTD UT=e
Le
U, where e
L=VTand e
U=De
L. Thus, AT
is regular since the diagonal entries of e
U, which are the pivots of AT, are the same as those
25
of Dand U, which are the pivots of A.
♥1.6.29. (a) The diagonal entries satisfy jii =−jii and so must be 0. (b) 0 1
1.6.30.
(a) Let S=1
2(A+AT), J=1
2(A−AT). Then ST=S,JT=−J, and A=S+J.
(b) 1 2
3 4 != 15
2
5
24!+ 0−1
2
1
20!;0
B
@
123
4 5 6
7891
C
A=0
B
@
1 3 5
3 5 7
5 7 9 1
C
A+0
B
@
0−1−2
1 0 −1
2 1 0 1
C
A.
1.7.1.
(a) The solution is x=−10
7, y =−19
7. Gaussian Elimination and Back Substitution re-
quires 2 multiplications and 3 additions; Gauss–Jordan also uses 2 multiplications and 3
additions; finding A−1=0
@
1
7
2
7
−3
1
Aby the Gauss–Jordan method requires 2 additions
1.7.2.
(a) For a general matrix A, each entry of A2requires nmultiplications and n−1 additions,
for a total of n3multiplications and n3−n2additions, and so, when compared with
the efficient version of the Gauss–Jordan algorithm, takes exactly the same amount of
26
Exercise 1.7.8 and [11] for more sophisticated ways to speed up the computation.
1.7.3. Back Substitution requires about one half the number of arithmetic operations as multi-
plying a matrix times a vector, and so is twice as fast.
♦1.7.4. We begin by proving (1.61). We must show that 1 + 2 + 3 + . . . + (n−1) = n(n−1)/2
for n= 2,3, . . .. For n= 2 both sides equal 1. Assume that (1.61) is true for n=k. Then
♥1.7.5. We may assume that the matrix is regular, so P= I , since row interchanges have no
effect on the number of arithmetic operations.
(a) First, according to (1.60), it takes 1
3n3−1
3nmultiplications and 1
3n3−1
2n2+1
6n
additions to factor A=LU. To solve Lcj=ejby Forward Substitution, the first j−1
multiplications and n(n−1)2additions.
(b) Starting with the large augmented matrix M=“A|I”, it takes 1
2n2(n−1) multipli-
cations and 1
2n(n−1)2additions to reduce it to triangular form “U|C”with Uupper
triangular and Clower triangular, then n2multiplications to obtain the special upper
1.7.6. Combining (1.60–61), we see that it takes 1
3n3+1
2n2−5
6nmultiplications and 1
3n3−1
3n
additions to reduce the augmented matrix to upper triangular form “U|c”. Dividing the
1.7.7. Less efficient, by, roughly, a factor of 3
2. It takes 1
2n3+n2−1
2nmultiplications and
1
2n3−1
2nadditions.
27
♥1.7.8.
(a)D1+D3−D4−D6= (A1+A4)(B1+B4) + (A2−A4) (B3+B4)−
−(A1+A2)B4−A4(B1−B3) = A1B1+A2B3=C1,
−(A3+A4)B1+A1(B2−B4) = A3B2+A4B4=C4.
(b) To compute D1, . . . , D7requires 7 multiplications and 10 additions; then to compute
C1, C2, C3, C4requires an additional 8 additions for a total of 7 multiplications and 18
additions. The traditional method for computing the product of two 2 ×2 matrices re-
quires 8 multiplications and 4 additions.
(c) The method requires 7 multiplications and 18 additions of n×nmatrices, for a total of
7n3and 7n2(n−1)+18 n2≈7n3additions, versus 8n3multiplications and 8n2(n−1) ≈
(e) One way is to use block matrix multiplication, in the trivial form AO
O I ! BO
O I !=
CO
O I !where C=A B. Thus, choosing I to be an identity matrix of the appropriate
size, the overall size of the block matrices can be arranged to be a power of 2, and then
1.7.9.
(a)0
B
@
1 2 0
−1−1 1
0−2 3 1
C
A=0
B
@
1 0 0
−1 1 0
0−2 1 1
C
A0
B
@
120
0 1 1
0051
C
A,x=0
B
@−2
3
01
C
A;
28
5
1.7.10.
(a)0
B
@
2−1 0
−1 2 −1
0−1 2 1
C
A=0
B
@
1 0 0
−1
21 0
0−2
1
C
A0
B
@
2−1 0
03
2−1
0 0 4
1
C
A,
♠1.7.11.
(a)0
B
@
2 1 0
−1 2 1
0−1 2 1
C
A=0
B
@
1 0 0
−1
21 0
0−2
1
C
A0
B
@
2 1 0
05
21
0 0 12
1
C
A,
1.7.12. Both false. For example,
0
B
B
B
@
1 1 0 0
1 1 1 0
0 1 1 1
0 0 1 1
1
C
C
C
A0
B
B
B
@
1 1 0 0
1 1 1 0
0 1 1 1
0 0 1 1
1
C
C
C
A=0
B
B
B
@
2 2 1 0
2 3 2 1
1 2 3 2
0 1 2 2
1
C
C
C
A,0
B
B
B
@
1 1 0 0
1 1 1 0
0 1 1 1
0 0 1 1
1
C
C
C
A
−1
=0
B
B
B
@
1 0 −1 1
0 0 1 −1
−1 1 0 0
1−1 0 1
1
C
C
C
A.
29
0
B
B
B
B
B
@
4 1 0 1
1 4 1 0
0 1 4 1
1 0 1 4
1
C
C
C
C
C
A
=0
B
B
B
B
B
@
1 0 0 0
1
41 0 0
04
15 1 0
1
4−1
15
2
71
1
C
C
C
C
C
A
0
B
B
B
B
B
@
4 1 0 1
015
41−1
4
0 0 56
15
16
15
0 0 0 24
7
1
C
C
C
C
C
A
0
1
0
1
♥1.7.14.
(a) Assuming regularity, the only row operations required to reduce Ato upper triangular
form Uare, for each j= 1,…,n−1, to add multiples of the jth row to the (j+1)st and
(b)0
B
@
1−1−1
−1 2 −1
−1−1 3 1
C
A=0
B
@
1 0 0
−110
−1 2 1 1
C
A0
B
@
1−1−1
0 1 −2
0 0 2 1
C
A,
0
B
B
1−1 0 0 −1
−1 2 −1 0 0
1
C
C
B
B
1 0 0 0 0
−1 1 0 0 0
1
C
C
0
B
B
1−1 0 0 −1
0 1 −1 0 −1
1
C
C
30
♥1.7.15.
(a) If matrix Ais tridiagonal, then the only nonzero elements in ith row are ai,i−1, aii, ai,i+1.
So aij = 0 whenever |i−j|>1.
0
B
2 1 1 0 0 0
1 2 1 1 0 0
1
C
0
B
2 1 1 1 0 0
1 2 1 1 1 0
1
C
0
B
B
B
B
2 1 1 0 0 0
1 2 1 1 0 0
1 1 2 1 1 0
1
C
C
C
C
0
B
B
B
B
B
B
1 0 0 0 0 0
1
21 0 0 0 0
1
2
1
31 0 0 0
1
C
C
C
C
C
C
0
B
B
B
B
B
B
211000
03
2
1
21 0 0
0 0 4
3
2
31 0
1
C
C
C
C
C
C
0 0 3
4
5
41
000003
4
(e)“1
3,1
3,0,0,1
3,1
3”T,“2
3,1
3,−1
3,−1
3,1
3,2
3”T.
(f) For Awe still need to compute kmultipliers at each stage and update at most 2k2en-
tries, so we have less than (n−1)(k+ 2 k2) multiplications and (n−1)2k2additions. For
the right-hand side we have to update at most kentries at each stage, so we have less
1.7.16. (a) ( −8,4 )T, (b) ( −10,−4.1 )T, (c) ( −8.1,−4.1 )T. (d) Partial pivoting reduces
the effect of round off errors and results in a significantly more accurate answer.
31