then choose another vector vm+2 not in the span of v1, . . . , vm+1, and so v1, . . . , vm+2
are also linearly independent. We continue on in this fashion until we arrive at nlin-
early independent vectors v1,…,vnwhich necessarily form a basis of Rn.
(c) (i)“1,1,1
2”T,( 1,0,0 )T,( 0,1,0 )T; (ii ) ( 1,0,−1 )T,( 0,1,−2 )T,( 1,0,0 )T.
♦2.4.25.
(a) If dim V=∞, then the inequality is trivial. Also, if dim W=∞, then one can find
infinitely many linearly independent elements in W, but these are also linearly indepen-
♦2.4.26. (a) Every v∈Vcan be uniquely decomposed as v=w+zwhere w∈W, z∈Z. Write
w=c1w1+…+cjwjand z=d1z1+···+dkzk. Then v=c1w1+. . . +cjwj+d1z1+
···+dkzk, proving that w1,…,wj,z1,…,zkspan V. Moreover, by uniqueness, v=0if
and only if w=0and z=0, and so the only linear combination that sums up to 0∈Vis
the trivial one c1=· · · =cj=d1=··· =dk= 0, which proves linear independence of the
full collection. (b) This follows immediately from part (a): dim V=j+k= dim W+dim Z.
♦2.4.27. Suppose the functions are linearly independent. This means that for every 06=c=
(c1, c2, . . . , cn)T∈Rn, there is a point xc∈Rsuch that
n
X
i= 1
cifi(xc)6= 0. The as-
2.5.1.
(a) Range: all b= b1
b2!such that 3
4b1+b2= 0; kernel spanned by 1
2
1!.
57
2.5.2. (a)0
B
B
@
−5
2
0
1
1
C
C
A,0
B
B
@
1
2
1
0
1
C
C
A: plane; (b)0
B
B
B
@
1
4
3
8
1
1
C
C
C
A: line; (c)0
B
@
2
0
11
C
A,0
B
@
−3
1
01
C
A: plane;
1
2.5.4. (a)b=0
B
@
−1
2
−11
C
A; (b)x=0
B
@
1 + t
2 + t
3 + t1
C
Awhere tis arbitrary.
2.5.5. In each case, the solution is x=x⋆+z, where x⋆is the particular solution and zbelongs
to the kernel:
(a)x⋆=0
B
@
1
0
01
C
A,z=y0
B
@
1
1
01
C
A+z0
B
@
−3
0
11
C
A; (b)x⋆=0
B
@
1
−1
01
C
A,z=z0
B
B
@
−2
7
1
7
1
1
C
C
A;
2.5.6. The ith entry of A( 1,1,…,1 )Tis ai1+…+ain which is ntimes the average of the en-
tries in the ith row. Thus, A( 1,1, . . . , 1 )T=0if and only if each row of Ahas average 0.
2.5.7. The kernel has dimension n−1, with basis −rk−1e1+ek=“−rk−1,0, . . . , 0,1,0, . . . , 0”T
−1−1!then 1
1!is in both ker Aand rng A.
♦2.5.10. Let r1,…,rm+kbe the rows of C, so r1, . . . , rmare the rows of A. For v∈ker C, the
ith entry of Cv=0is riv= 0, but then this implies Av=0and so v∈ker A. As an
example, A= ( 1 0 ) has kernel spanned by 1
0!, while C= 1 0
0 1 !has ker C={0}.
58
♦2.5.11. If b=Ax∈rng A, then b=Czwhere z= x
0!, and so b∈rng C. As an example,
A= 0
0!has rng A={0}, while the range of C= 0 1
0 0 !is the xaxis.
31
2.5.14.
(a) By direct matrix multiplication: Ax⋆
1=Ax⋆
2=0
B
@
1
−3
51
C
A.
(b) The general solution is x=x⋆
1+t(x⋆
2−x⋆
1) = (1 −t)x⋆
1+tx⋆
2=0
B
@
1
1
C
A+t0
B
@
−4
2
C
A.
2.5.17. x=c1x⋆
1+c2x⋆
2where c1= 1 −c2.
2.5.18. False: in general, (A+B)x⋆= (A+B)x⋆
1+ (A+B)x⋆
2=c+d+Bx⋆
1+Ax⋆
2, and the
third and fourth terms don’t necessarily add up to 0.
2.5.21.
(a) range: 1
2!; corange: 1
−3!; kernel: 3
1!; cokernel: −2
1!.
59
(d) range: 0
B
B
B
B
B
@
1
0
2
3
1
1
C
C
C
C
C
A
,0
B
B
B
B
B
@
−3
3
−3
−3
0
1
C
C
C
C
C
A
,0
B
B
B
B
B
@
1
−2
0
3
3
1
C
C
C
C
C
A
; corange: 0
B
B
B
B
B
@
1
−3
2
2
1
1
C
C
C
C
C
A
,0
B
B
B
B
B
@
0
3
−6
0
−2
1
C
C
C
C
C
A
,0
B
B
B
B
B
@
0
0
0
0
4
1
C
C
C
C
C
A
;
kernel: 0
B
B
B
B
B
@
4
2
1
0
0
1
C
C
C
C
C
A
,0
B
B
B
B
B
@
−2
0
0
1
0
1
C
C
C
C
C
A
; cokernel: 0
B
B
B
B
B
@
−2
−1
1
0
0
1
C
C
C
C
C
A
,0
B
B
B
B
B
@
2
1
0
−1
1
1
C
C
C
C
C
A
.
41
01
41
11
01
41
2.5.24.
(i) rank = 1; dim rng A= dim corng A= 1, dim ker A= dim coker A= 1;
kernel basis: −2
1!; cokernel basis: 2
1!; compatibility conditions: 2b1+b2= 0;
example: b= 1
−2!, with solution x= 1
0!+z −2
1!.
(ii ) rank = 1; dim rng A= dim corng A= 1, dim ker A= 2, dim coker A= 1; kernel basis:
21
01
(iv ) rank = 2; dim rng A= dim corng A= 2, dim ker A= dim coker A= 1;
kernel basis: 0
B
@
−2
−1
11
C
A; cokernel basis: 0
B
@
−2
1
11
C
A; compatibility conditions:
2
1
−2
60
(vi ) rank = 3; dim rng A= dim corng A= 3, dim ker A= dim coker A= 1; kernel basis:
0
B
B
B
B
B
@
13
4
13
8
−7
2
1
1
C
C
C
C
C
A
; cokernel basis: 0
B
B
B
@
−1
−1
1
1
1
C
C
C
A; compatibility conditions: −b1−b2+b3+b4= 0;
example: b=0
B
B
B
@
1
3
1
3
1
C
C
C
A, with solution x=0
B
B
B
B
B
@
1
0
0
0
1
C
C
C
C
C
A
+w0
B
B
B
B
B
@
13
4
13
8
−7
2
1
1
C
C
C
C
C
A
.
(vii ) rank = 4; dim rng A= dim corng A= 4, dim ker A= 1, dim coker A= 0; kernel basis:
0
1
2.5.25. (a) dim = 2; basis: 0
B
@
1
2
−11
C
A,0
B
@
2
2
01
C
A; (b) dim = 1; basis: 0
B
@
1
1
−11
C
A;
(c) dim = 3; basis: 0
B
B
B
@
1
0
1
0
1
C
C
C
A,0
B
B
B
@
1
0
0
1
1
C
C
C
A,0
B
B
B
@
2
2
1
0
1
C
C
C
A; (d) dim = 3; basis: 0
B
B
B
@
1
0
−3
2
1
C
C
C
A,0
B
B
B
@
0
1
2
−3
1
C
C
C
A,0
B
B
B
@
1
−3
−8
7
1
C
C
C
A;
61
2.5.28. First method: 0
B
B
B
@
1
0
2
1
1
C
C
C
A,0
B
B
B
@
2
3
−4
5
1
C
C
C
A; second method: 0
B
B
B
@
1
0
2
1
1
C
C
C
A,0
B
B
B
@
0
3
−8
3
1
C
C
C
A. The first vectors are the
same, while 0
B
B
B
@
2
3
−4
5
1
C
C
C
A= 20
B
B
B
@
1
0
2
1
1
C
C
C
A+0
B
B
B
@
0
3
−8
3
1
C
C
C
A;0
B
B
B
@
0
3
−8
3
1
C
C
C
A=−20
B
B
B
@
1
0
2
1
1
C
C
C
A+0
B
B
B
@
2
3
−4
5
1
C
C
C
A.
2.5.30.
(a) If A=AT, then ker A={Ax=0}={ATx=0}= coker A, and rng A={Ax}=
2.5.31.
(a) Yes. This is our method of constructing the basis for the range, and the proof is out-
lined in the text.
(b) No. For example, if A=0
B
B
B
@
1 0 0 0
1 0 0 0
0 1 0 0
1
C
C
C
A, then U=0
B
B
B
@
1 0 0 0
0 1 0 0
0 0 1 0
1
C
C
C
Aand the first three
2.5.32. (a) Example: 0 0
1 0 !. (b) No, since then the first rrows of Uare linear combina-
tions of the first rrows of A. Hence these rows span corng A, which, by Theorem 2.31c,
implies that they form a basis for the corange.
2.5.33. Examples: any symmetric matrix; any permutation matrix since the row echelon form is
the identity. Yet another example is the complex matrix 0
B
@
0 0 1
1 i i
0 i i 1
C
A.
62
row echelon form U= 1 1
0 0 !is spanned by 1
0!.
♦2.5.37.
(a) Method 1: choose the nonzero rows in the row echelon form of A. Method 2: choose the
♦2.5.38. If v∈ker Athen Av=0and so B Av=B0=0, so v∈ker(B A). The first statement
follows from setting B=A.
♦2.5.39. If v∈rng A B then v=A B xfor some vector x. But then v=Aywhere y=Bx, and
so v∈rng A. The first statement follows from setting B=A.
2.5.40. First note that B A and A C also have size m×n. To show rank A= rank B A, we prove
that ker A= ker B A, and so rank A=n−dim ker A=n−dim ker B A = rank B A.
Indeed, if v∈ker A, then Av=0and hence B A v=0so v∈ker B A. Conversely, if v∈
ker B A then B Av=0. Since Bis nonsingular, this implies Av=0and hence v∈ker A,
2.5.42. True if the matrices have the same size, but false in general.
♦2.5.43. Since we know dim rng A=r, it suffices to prove that w1, . . . , wrare linearly indepen-
dent. Given
0=c1w1+· · · +crwr=c1Av1+···+crAvr=A(c1v1+· · · +crvr),
♦2.5.44.
(a) Since they have the same kernel, their ranks are the same. Choose a basis v1, . . . , vnof
Rnsuch that vr+1,…,vnform a basis for ker A= ker B. Then w1=Av1, . . . , wr=
Avrform a basis for rng A, while y1=Bv1,…,yr=Bvrform a basis for rng B.
Let Mbe any nonsingular m×mmatrix such that Mwj=yj,j= 1, . . . , r, which
63
“B|c”by applying the elementary row operations that make up M.
♦2.5.45. (a) First, W⊂rng Asince every w∈Wcan be written as w=Avfor some v∈
V⊂Rn, and so w∈rng A. Second, if w1=Av1and w2=Av2are elements of W, then
♦2.5.46.
(a) To have a left inverse requires an n×mmatrix Bsuch that B A = I . Suppose dim rng A=
rank A < n. Then, according to Exercise 2.5.45, the subspace W={Bv|v∈rng A}
has dim W≤dim rng A < n. On the other hand, w∈Wif and only if w=Bvwhere
2.6.1. (a) (b) (c)
2.6.2. (a)
2.6.3. (a)0
B
B
B
@
−1 0 1 0
0−1 1 0
0 1 0 −1
0 0 1 −1
1
C
C
C
A; (b)0
B
B
B
B
B
@
−1 1 0 0
−1 0 0 1
1 0 −1 0
0 1 0 −1
0 0 −1 1
1
C
C
C
C
C
A
; (c)
0
B
B
B
B
B
B
B
@
−1 0 1 0 0
−1 1 0 0 0
0−1 0 1 0
0−1 0 0 1
0 0 1 −1 0
0 0 0 1 −1
1
C
C
C
C
C
C
C
A
;
2.6.4. (a) 1 circuit: 0
B
B
B
@
0
−1
−1
1
1
C
C
C
A; (b) 2 circuits: 0
B
B
B
B
B
@
−1
1
0
1
0
1
C
C
C
C
C
A
,0
B
B
B
B
B
@
0
−1
−1
0
1
1
C
C
C
C
C
A
; (c) 2 circuits:
0
B
B
B
B
B
B
B
@
−1
1
1
0
1
0
1
C
C
C
C
C
C
C
A
,
0
B
B
B
B
B
B
B
@
0
0
−1
1
0
1
1
C
C
C
C
C
C
C
A
;
♥2.6.5. (a)0
B
B
B
B
B
@
1−1 0 0
1 0 −1 0
1 0 0 −1
0 1 −1 0
010−1
1
C
C
C
C
C
A
; (b) rank = 3; (c) dim rng A= dim corng A= 3,
1
1
65
(e)b1−b2+b4= 0, b1−b3+b5= 0; (f) example: b=0
B
B
B
B
B
@
1
1
1
0
0
1
C
C
C
C
C
A
;x=0
B
B
B
@
1 + t
t
t
t
1
C
C
C
A.
♦2.6.6.
(a)0
B
B
B
1−1 0 0 0 0 0 0
1 0 −1 0 0 0 0 0
1
C
C
C
Cokernel basis: v1=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
−1
1
0
−1
0
1
0
0
0
0
0
0
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
,v2=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
−1
0
1
0
−1
0
0
1
0
0
0
0
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
,v3=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
0
−1
1
0
0
0
−1
0
1
0
0
0
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
,v4=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
0
0
0
−1
1
0
0
0
0
−1
1
0
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
,v5=
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
@
0
0
0
0
0
−1
1
0
0
−1
0
1
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
A
.
66
number of circuits = dim coker A= 3, number of faces = 4;
(b) Octahedron: 0
B
B
B
B
B
B
1−1 0 0 0 0
1 0 −1 0 0 0
1 0 0 −1 0 0
1
C
C
C
C
C
C
(c) Dodecahedron:
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
1−1000000000000000000
10000−100000000000000
0 1 −100000000000000000
010000−10000000000000
001−10000000000000000
0010000−1000000000000
0 0 0 1 −1000000000000000
00010000−100000000000
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
67
(d) Icosahedron:
0
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
B
1−1 0 0 0 0 0 0 0 0 0 0
1 0 −1 0 0 0 0 0 0 0 0 0
1 0 0 −1 0 0 0 0 0 0 0 0
1 0 0 0 −1 0 0 0 0 0 0 0
1 0 0 0 0 −1 0 0 0 0 0 0
0 1 −1 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 −1 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 −1 0
1
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
♥2.6.8.
(a) (i)0
B
@
−1 1 0 0
0 1 −1 0
0 1 0 −11
C
A, (ii )0
B
B
B
@
−1 1 0 0 0
0−1 1 0 0
0 0 −1 1 0
0 1 0 0 −1
1
C
C
C
A,
(iii )0
B
B
B
B
B
@
−1 1 0 0 0 0
0 1 −1 0 0 0
0 0 1 −1 0 0
0 1 0 0 −1 0
0 1 0 0 0 −1
1
C
C
C
C
C
A
, (iv )0
B
B
B
B
B
@
−1 1 0 0 0 0
0−1 1 0 0 0
0 0 −1 1 0 0
0 1 0 0 −1 0
0 0 1 0 0 −1
1
C
C
C
C
C
A
.
68
(c) Let mdenote the number of edges. Since the graph is connected, its incidence matrix
Ahas rank n−1. There are no circuits if and only if coker A={0}, which implies
0 = dim coker A=m−(n−1), and so m=n−1.
♥2.6.9.
(a)
♥2.6.10.
(a)
69
♥2.6.11.
(a)A=
0
B
B
B
B
B
B
B
B
B
B
@
1−1 0 0 0 0 0 0
−1 0 0 1 0 0 0 0
0−1 0 1 0 0 0 0
0 0 −1 0 0 1 0 0
0 0 0 0 −1 0 1 0
0 0 0 0 −1 0 0 1
0 0 0 0 0 0 1 −1
1
C
C
C
C
C
C
C
C
C
C
A
.
♦2.6.12. If the incidence matrix has rank r, then # circuits
= dim coker A=n−r= dim ker A≥1,
since ker Aalways contains the vector ( 1,1,…,1 )T.
2.6.13. Changing the direction of an edge is the same as multiplying the corresponding row of
the incidence matrix by −1. The dimension of the cokernel, being the number of indepen-
dent circuits, does not change. Each entry of a cokernel vector that corresponds to an edge
that has been reversed is multiplied by −1. This can be realized by left multiplying the
70
2.6.15. False. For example, any two inequivalent trees, cf. Exercise 2.6.8, with the same num-
ber of nodes have incidence matrices of the same size, with trivial cokernels: coker A=
coker B={0}. As another example, the incidence matrices
1
1
both have cokernel basis ( 1,1,1,0,0 )T, but do not represent equivalent digraphs.
2.6.16.
(a) If the first kvertices belong to one component and the last n−kto the other, then there
is no edge between the two sets of vertices and so the entries aij = 0 whenever i=
1, . . . , k,j=k+ 1, . . . , n, or when i=k+ 1, . . . , n,j= 1,…,k, which proves that Ahas