Page 214 - Matrix Analysis & Applied Linear Algebra

4.4 Basis and Dimension 209

4.4.17. Suppose that A is a matrix with m rows such that the system Ax = b
m
has a unique solution for every b ∈ . Explain why this means that
A must be square and nonsingular.

4.4.18. Let S be the solution set for a consistent system of linear equations
Ax = b.
(a) If S max = {s 1 , s 2 ,..., s t } is a maximal independent subset of
S, and if p is any particular solution, prove that

span (S max )= span {p} + N (A).

Hint: First show that x ∈S implies x ∈ span (S max ) , and
then demonstrate set inclusion in both directions with the aid
of Exercise 4.2.10.
(b) If b = 0 and rank (A m×n )= r, explain why Ax = b has
n − r + 1 “independent solutions.”

4.4.19. Let rank (A m×n )= r, and suppose Ax = b with b = 0 is a consistent
system. If H = {h 1 , h 2 ,..., h n−r } is a basis for N (A), and if p is a
particular solution to Ax = b, show that

S max = {p, p + h 1 , p + h 2 ,. . . , p + h n−r }

is a maximal independent set of solutions.

4.4.20. Strongly Connected Graphs. In Example 4.4.6 we started with a
graph to construct a matrix, but it’s also possible to reverse the situation
by starting with a matrix to build an associated graph. The graph of
A n×n (denoted by G(A)) is defined to be the directed graph on n
nodes {N 1 ,N 2 ,...,N n } in which there is a directed edge leading from
N i to N j if and only if a ij =0. The directed graph G(A) is said to
be strongly connected provided that for each pair of nodes (N i ,N k )
there is a sequence of directed edges leading from N i to N k . The matrix
A is said to be reducible if there exists a permutation matrix P such
X Y
T
that P AP = , where X and Z are both square matrices.
0 Z
Otherwise, A is said to be irreducible. Prove that G(A) is strongly
connected if and only if A is irreducible. Hint: Prove the contrapositive:
G(A)is not strongly connected if and only if A is reducible.