Page 192 - Matrix Analysis & Applied Linear Algebra

4.3 Linear Independence 187

Maximal Independent Subsets
If rank (A m×n )= r, then the following statements hold.

• Any maximal independent subset of columns from A con- (4.3.10)
tains exactly r columns.

• Any maximal independent subset of rows from A contains (4.3.11)
exactly r rows.

• In particular, the r basic columns in A constitute one (4.3.12)
maximal independent subset of columns from A.

Proof. Exactly the same linear relationships that exist among the columns of
A must also hold among the columns of E A —by (3.9.6). This guarantees that
a subset of columns from A is linearly independent if and only if the columns
in the corresponding positions in E A are an independent set. Let

C = c 1 | c 2 |· · · | c k
be a matrix that contains an independent subset of columns from E A so that
rank (C)= k —recall (4.3.3). Since each column in E A is a combination of the
r
r basic (unit) columns in E A , there are scalars β ij such that c j = β ij e i
i=1
for j =1, 2,...,k. These equations can be written as the single matrix equation
 
β 11 β 12 ··· β 1k
 β 21 β 22
··· β 2k 
c 1 | c 2 |· · · | c k = e 1 | e 2 |· · · | e r  . . . . 
 . . .
. . . . . 
β r1 β r2 ··· β rk
or

I r B r×k
C m×k = B r×k = , where B =[β ij ].
0 0
Consequently, r ≥ rank (C)= k, and therefore any independent subset of
columns from E A —and hence any independent set of columns from A —cannot
contain more than r vectors. Because the r basic (unit) columns in E A form
an independent set, the r basic columns in A constitute an independent set.
This proves (4.3.10) and (4.3.12). The proof of (4.3.11) follows from the fact that
T
rank (A)= rank A —recall (3.9.11).