Schurs Triangularization Theorem
Math 422
The characteristic polynomial p (t) of a square complex matrix A splits as a product of linear factors of
the form (t )m . Of course, finding these factors is a dicult problem, but having factored p (t) we can
triangularize A whether or not A is diagonalizable.
Example 1 The characteristic polynomial p (t) = t2 of the triangular matrix
0 1
A=
0 0
has the single root = 0, which is an eigenvalue
of algebraic multiplicity 2. The eigenspace of is one
dimensional and is spanned by the single vector 10 , so the geometric multiplicity of is 1. Therefore A is
defective and is not diagonalizable (one needs two linearly independent eigenvectors to construct a transition
matrix P that diagonalizes A).
Let V n be an n-dimensional complex inner product space with Euclidean inner product.
Definition 2 A hyperplane in V n is a translation of an (n 1)-dimensional subspace.
Note that the orthogonal complement u of a non-zero vector u Cn is a hyperplane through the origin.
Consider the matrix
1
P =I
2 uu ;
kuk
then Q = P
kuk
uu = I
kuk2
uu is the Householder matrix associated with u.
Proposition 3 N (P ) = span {u} and multiplication by P is orthogonal projection on u , i.e., for all
x Cn ,
P x = proju x.
xu
u = 0 or equivalently x =
u. Thus x = tu for some t C, and
kuk2
kuk2
N (P ) = span {u} . Furthermore, for all x Cn , P x = x proju x = proju x.
Proof. If P x = 0, then x
xu
Definition 4 Let x, y, u Cn with u 6= 0. Then y is the reflection of x in the hyperplane u i
x y = 2 proju x.
Proposition 5 Let u Cn be a non-zero vector. The Householder transformation associated with u is
reflection in the hyperplane u .
!
xu
n
Proof. Note that for all x C , Qx = x 2
= x 2 proju x. Thus x Qx = 2 proju x.
2u
kuk
Exercise 6 Earlier we proved that a real Householder matrix Q is symmetric and orthogonal, i.e.,QT = Q
and Q1 = QT . Generalize this result for complex matrices: Prove that complex Householder matrices Q
are Hermitian and unitary.
Let v = (v1 , . . . , vn ) be a non-zero vector in Cn and set x =
vector with x1 R. Let u = x e1 then
kuk2
v1 v
. Then x = (x1 , . . . , xn ) Cn is a unit
kv1 vk
= (x e1 ) (x e1 ) = x x x e1 e1 x + e1 e1 = 2 2x1 = 2 (1 x1 )
x u = x (x e1 ) = x x x e1 = 1 x1 .
1
If x 6= e1 , then u 6= 0 and we may apply the Householder transformation Q associated with u to x and e1 :
Qx = x 2
xu
kuk
2u
=x
2 (1 x1 )
u = x u = x (x e1 ) = e1 ;
2 (1 x1 )
(1)
applying Q to both sides of (1) and using the fact that Q2 = I we have
x = Q2 x = Qe1 .
If x = e1 , set Q = I; then in either case
x = Qe1 and e1 = Qx
are reflection of each other in the hyperplane (x e1 ) . For a unit vector x R2 , the line (x e1 ) bisects
the angle between x and e1 . We are ready to prove our main theorem in this lecture:
Theorem 7 (Schurs Triangularization Theorem) Every n n complex matrix A is unitarily similar to an
upper-triangular matrix T , i.e., there exists a unitary matrix U such that U AU = T.
Proof. Use induction on the size of A. For n = 1 there is nothing to prove. So assume n > 1 and that
the result holds for all matrices of size less than n. Since every complex matrix has an eigenvalue, choose
v1 v
an eigenvalue of A and an associated eigenvector v = (v1 , . . . , vn ) . Let x =
and set u = x e1 ;
kv1 vk
if x 6= e1 , let Q be the Householder matrix associated with u; if x = e1 let Q = I. Then x = Qe1 by the
discussion above, so x is the first column of Q. By Exercise
6, Q is Hermitian and unitary, so x is the first
row of Q. Since Q = Q1 = Q we have Q = [x | V ] = Vx and
x
x AV
QAQ = QA [x | V ] = Q [x | AV ] = e1 |
AV =
.
0 V AV
V
Now apply the induction hypothesis to V AV, which is an (n 1) (n 1) matrix, and obtain an (n 1)
(n 1) unitary matrix R such that Tn1 = R (V AV ) R is upper-triangular. Let
1 0
U =Q
;
0 R
then
U U =
1 0
0 R
Q Q
1 0
0 R
1
0
0 R R
=I
so U is unitary. Hence
T
= U
1 0
1 0
QAQ
AU =
0 R
0 R
1 0
x AV
1 0
0 R
0 V AV
0 R
x AV R
1 0
0 R
0 V AV R
x AV R
x AV R
=
0 R V AV R
0
Tn1
is upper triangular as desired.
Remark 8 Since similar matrices have the same eigenvalues, the eigenvalues of A are the diagonal entries
of every Schur triangularization T = U AU.
When all eigenvalues of A are real, Schurs Triangularization Theorem tells us that A is orthogonally
similar to a triangular matrix. Our next example demonstrates this.
2
Example 9 Lets find a Schur triangularization of the matrix
1 1 2
8 11 8 .
A=
10
11
7
The eigenvalues of A are 1 = 1, 2 = 3 and 3 = 3. Arbitrarily choose an eigenvalue, say 1 = 1, then
2 1 2
1 0 12
8 12 8 0 1 1
AI =
10
11
6
0 0 0
1/3
4/3
and x = 2/3 is an associated unit eigenvector. Let u = xe1 = 2/3 and let Q be the associated
2/3
2/3
Householder matrix, i.e.,
1 2 2
1
3 T
2
2 1 = [x | V ] ,
Q = I uu =
4
3
2
1 2
where
Then
2 2
1
V = 2 1 .
3
1 2
3
64 13
1 13 1
1
T
0 13 1
and V AV =
.
QAQ =
16 5
3
3
0
16 5
1
Now triangularize the 2 2 matrix V T AV, which has the single eigenvalue 3. The vector x = 117 4
is a
117
1
unit vector associated with 3. Let u = x e1 = 17 4 and let R be the Householder matrix associated
with u, i.e.,
0.242 54 0.970 14
R=
.
0.970 14 0.242 54
Then
RV T AV R =
3 17/3
0
3
is a Schur triangularization of V T AV . Finally, let
U =Q
then
1 0
0 R
1 0.970 25 21.747
5.6667
U T AU = 0 3.000
0
0
3.000
is a (numerically approximate) Schur triangularization of A.
In summary, every matrix is triangularizable but only non-defective matrices are diagonalizable.
Exercise 10 Show that the matrix
1 1 2
8 11 8 .
A=
10
11
7
in Example 9 is defective and hence not diagonalizable.
3
Following the proof of Schurs Triangularization Theorem, find an orthogonal matrix P such that P T AP is
upper triangular:
1 1
Exercise 11 A =
1 3
2 1
Exercise 12 A =
1 2
13 9
Exercise 13 A =
16 11
