Mathematics 372 – Numerical Linear Algebra Selected Solutions – Problem Set 6 March 7, 2007

3.5.24. a) If x ∈ R^{n} is any vector then

x^{t}(A^{t}A)x = (Ax)^{t}(Ax) = ∥Ax∥_{2}^{2}.

This is always ≥ 0 by the properties of vector norms. Hence A^{t}A is positive semi-definite for all A.

b) If A ∈ M_{n×m}(R) and n < m, then there are fewer equations than variables in the homogeneous system Ax = 0. This means that there is a nontrivial solution x_{p} ≠ 0 with Ax_{p} = 0 (set at least one of the free variables to a nonzero value). Hence

x_{p}(A^{t}A)x_{p} = ∥Ax_{p}∥_{2}^{2} = 0

but x_{p} ≠ 0. This shows that A^{t}A is not positive-definite.

c) Now assume A ∈ M_{n×m}(R) and n ≥ m. We want to show that A^{t}A is positive definite if and only if A has full rank. (That is, rank(A) = m, or equivalently, that the columns of A are linearly independent – recall that the rank of a matrix is, by definition, the dimension of its column space.) By the same reasoning as above, we have A^{t}A is positive definite if and only if x^{t}(A^{t}A)x = ∥Ax∥_{2}^{2} = 0 implies x = 0, so Ax = 0 implies x = 0. But if x ∈ R^{m}, then

Ax = x_{1}a_{1} + ⋯ + x_{m}a_{m},

where a_{i} are the columns of A. Hence Ax = 0 implies x = 0 is equivalent to the assertion that the columns of A are linearly independent.

3.5.26. Note: A, B here are n × m matrices. a) ⇒: Assume that x is the least-squares solution of Ax = b. Then we know b − Ax ∈ R(A)^{⊥} = N(A^{t}) by Corollary 3.5.20 in the text. But we are assuming R(B) = R(A) so by Theorem 3.5.10:

N(B^{t}) = R(B)^{⊥} = R(A)^{⊥} = N(A^{t}).

Therefore B^{t}(b − Ax) = 0. Rearranging algebraically, we get B^{t}Ax = B^{t}b.

⇐: Conversely, suppose B^{t}Ax = B^{t}b. Then B^{t}(b − Ax) = 0, so b − Ax ∈ N(B^{t}) = R(B)^{⊥}. Since we assume R(A) = R(B), R(A)^{⊥} = R(B)^{⊥}, so b − Ax ∈ R(A)^{⊥}. Hence x is the least-squares solution of Ax = b by Corollary 3.5.20.

b) ⇐: Assume A = BC for some nonsingular m × m matrix C. This matrix equation shows that each column of A is a linear combination of the columns of B so R(A) ⊆ R(B) (using 3.5.13 part a). But C is nonsingular, so we also know B = AC^{−1}. Then the same reasoning shows that every column of B is a linear combination of the columns of A, so R(B) ⊆ R(A). The two inclusions show R(A) = R(B).

⇒: We must show that if R(A) = R(B), then there is a nonsingular matrix C such that A = BC. First, note that R(A) = R(B) implies rank(A) = rank(B). Let us consider the special case first where the first k columns of A form a basis for R(A) and similarly the first k columns of B form a basis for R(B). Write A = (Â A′) and B = (B̂ B′) where Â and B̂ are the first k columns in each case. Since the columns of Â and B̂ are bases of R(A) = R(B), each of the first k columns of A can be written uniquely as a linear combination of the first k columns of B, and vice versa. This says that there are k × k matrices Ĉ and D̂ such that

(1)  ÂD̂ = B̂

and

(2)  B̂Ĉ = Â.

It follows that Â(D̂Ĉ) = Â and B̂(ĈD̂) = B̂. Then, since the columns of Â and B̂ are linearly independent, we get ĈD̂ = I_{k} and D̂Ĉ = I_{k}, so Ĉ and D̂ are inverse matrices of each other.

Furthermore, since the first k columns of B form a basis for R(B) again, the last m−k columns of A (the matrix A′) can be written in terms of the entries in the matrix B in the form

(3)  A′ = B′ + B̂P

for some k × (m − k) matrix P. Similarly,

(4)  B′ = A′ + ÂQ

for some k × (m − k) matrix Q. But then consider the m × m matrices

C = ( \begin{matrix}Ĉ & P \\ 0 & I_{m−k} \end{matrix} )

and

D = ( \begin{matrix}D̂ & Q \\ 0 & I_{m−k} \end{matrix} )

We have

BC = ( B̂ B′) ( \begin{matrix}Ĉ & P \\ 0 & I_{m−k} \end{matrix} ) = ( Â A′) = A

by (2) and (3) above. Furthermore, C is invertible since Ĉ is invertible as above.

(In fact, although this is not necessary for the problem, it can be seen that C^{−1} = D. This is true since

B(CD) = ( B̂ B′) ( \begin{matrix}Ĉ & P \\ 0 & I_{m−k} \end{matrix} ) ( \begin{matrix}D̂ & Q \\ 0 & I_{m−k} \end{matrix} ) = ( B̂(ĈD̂) B̂ĈQ + B̂P + B′) .

From (2), (3), and (4),

B̂ĈQ + B̂P + B′ = ÂQ + B̂P + B′ = B′ − A′ + A′ − B′ + B′ = B′

But this shows

B̂(ĈQ + P) = 0,

so, since the columns of B̂ are linearly independent, ĈQ + P = 0. Hence CD = I_{m}, and similarly DC = I_{m}.)

The general case now follows since we can find some collections of columns of A and B that are bases for R(A) and R(B) respectively and reorder the columns to put those bases in the first k columns. This can be done by multiplying by suitable m × m permutation matrices Π, Σ. Let

A_{1} = AΠ and B_{1} = BΣ.

Then by the above if R(A) = R(A_{1}) = R(B_{1}) = R(B), there is an invertible m×m matrix C such that B_{1}C_{1} = A_{1}. But then

A = A_{1}Π^{−1} = B_{1}C_{1}Π^{−1} = B(ΣC_{1}Π^{−1}),

so A = BC where C = ΣC_{1}Π^{−1}. This is invertible since Π, Σ, C_{1} are.