Principles of Mathematics in Operations Research

38 3 Orthogonality

Proof. (ATA)T = AT{AT)T = ATA.

Claim: N{A) = H{AT A).

i. M{A) C M{ATA) : x e M(A) =• Ax = 6 =>• 4rAr -iT9 = »4i£

ii. Af(ATA) C M{A) : x e M{ATA) => A^7 'Ax = 6 => a;ri4rAc = 0 4*

||Ar||^2 = 0 & Ax = 9, x € M(A). D

Remark 3.1.21 ATA has n columns, so does A. Since Af(A) = N(ATA),

dimhf(A) = n — r => dimR(ATA) = n - {n - r) = r.

Corollary 3.1.22 // rank(A) = n =>• ATA is a square, symmetric, and in-

vertible (non-singular) matrix.

3.2 Projections and Least Squares Approximations

Ax = 6 is solvable if b e R(A). If b £ R(A), then our problem is choose

x 3 \\b — Ax\\ is as small as possible.

Ax - b J. R(A) <S> (Ay)T(Ax - b) = 0 <^>

yT[ATAx - .4T6] = 0 (yT jt 6) => ATAx -ATb = 9^ ATAx = ATb.

Proposition 3.2.1 The least squares solution to an inconsistent system

Ax — b of m equations and n unknowns satisfies ATAx = ATb (normal

equations).

If columns of A are independent, then AT A is invertible, and the solution is

x = (ATA)-^1 ATb.

The projection of b onto the column space is therefore

p = Ax = A{ATA)~lATb = Pb,

where the matrix P = A(ATA)"^1 AT that describes this construction is known

as projection matrix.

Remark 3.2.2 (I — P) is another projection matrix which projects any vector
b onto the orthogonal complement: (I — P)b — b — Pb.

Proposition 3.2.3 The projection matrix P = A(ATA)~^1 AT has two basic
properties:

a. it is idempotent: P^2 — P.

b. it is symmetric: PT — P.