6.4. INVARIANT SUBSPACES 69
k dimensional “right projection” A
P
k
t=1
v
(t)
v
(t)
T
, we also can get the optimal
“left projection”
k
X
t=1
u
(t)
u
(t)
T
A.
Counting dimensions, it also follows that for any vector w orthogonal to such
a set of v
(1)
, v
(2)
, . . . v
(k)
, we have that Aw is orthogonal to u
(1)
, u
(2)
, . . . u
(k)
.
This yields the standard decomposition into the direct sum of subspaces.
Exercise 6.5. Prove Theorem 6.6.
6.4.1 Approximate invariance
The theorem below proves that even if the hypothesis of the previous theorem
|Av
(t)
|
2
= σ
2
t
(A) is only approximately satisfied, an approximate conclusion fol-
lows. We give below a fairly clean statement and proof formalizing this intuition.
It will be useful to define the error measure
∆(A, v
(1)
, v
(2)
, . . . v
(k)
) = Max
1≤t≤k
t
X
i=1
(σ
2
i
(A) − |Av
(i)
|
2
). (6.7)
Theorem 6.7. Let A be a matrix of rank r and v
(1)
, v
(2)
, . . . v
(r)
be an or-
thonormal set of vectors spanning the row space of A (so that {Av
(t)
} span the
column space of A). Then, for t, 1 ≤ t ≤ r, we have
r
X
s=t+1
v
(t)
T
A
T
Av
(s)
2
≤ |Av
(t)
|
2
σ
2
1
(A) + σ
2
2
(A) + . . . σ
2
t
(A) − |Av
(1)
|
2
− |Av
(2)
|
2
− . . . |Av
(t)
|
2
.
Note that v
(t)
T
A
T
Av
(s)
is the (t, s) th entry of the matrix A
T
A when written
with respect to the basis {v
(t)
}. So, the quantity
P
r
s=t+1
v
(t)
T
A
T
Av
(s)
2
is
the sum of squares of the above diagonal entries of the t th row of this matrix.
Theorem (6.7) implies the classical Theorem (6.6) : σ
t
(A) = |Av
(t)
| implies that
the right hand side of the inequality above is zero. Thus, v
(t)
T
A
T
A is colinear
with v
(t)
T
and so |v
(t)
T
A
T
A| = |Av
(t)
|
2
and so on.
Proof. First consider the case when t = 1. We have
r
X
s=2
(v
(1)
T
A
T
Av
(s)
)
2
= |v
(1)
T
A
T
A|
2
− (v
(1)
T
A
T
Av
(1)
)
2
≤ |Av
(1)
|
2
σ
1
(A)
2
− |Av
(1)
|
4
≤ |Av
(1)
|
2
(σ
1
(A)
2
− |Av
(1)
|
2
). (6.8)