14.2. THE QR ALGORITHM 371
14.2 The QR Algorithm
14.2.1 Basic Properties and Definition
Recall the theorem about the QR factorization in Theorem 5.7.5. It says that given an n×nreal matrix A, there exists a real orthogonal matrix Q and an upper triangular matrix R suchthat A = QR and that this factorization can be accomplished by a systematic procedure.One such procedure was given in proving this theorem.
Theorem 14.2.1 Let A be an m × n complex matrix. Then there exists a unitary Q andR, where R is all zero below the main diagonal (Rij = 0if i > j) such that A = QR.
Proof: This is obvious if m = 1.(a1 · · · an
)= (1)
(a1 · · · an
)Suppose true for m− 1 and let
A =(
a1 · · · an
), A is m× n
There exists Q1 a unitary matrix such that Q1 (a1/ |a1|) = e1 in case a1 ̸= 0. ThusQ1a1 = |a1| e1. If a1 = 0, let Q1 = I. Thus
Q1A =
(a b
0 A1
)where A1 is (m− 1)× (n− 1). If n = 1, this obtains
Q1A =
(a
0
), A = Q∗
1
(a
0
), let Q = Q∗
1.
That which is desired is obtained. So assume n > 1. By induction, there exists Q′2 an
(m− 1)× (n− 1) unitary matrix such that Q′2A1 = R′, R′
ij = 0 if i > j. Then(1 0
0 Q′2
)Q1A =
(a b
0 R′
)= R
Since the product of unitary matrices is unitary, there exists Q unitary such that Q∗A = Rand so A = QR. ■ ▶ ▶
The QR algorithm is described in the following definition.
Definition 14.2.2 The QR algorithm is the following. In the description of this algorithm,Q is unitary and R is upper triangular having nonnegative entries on the main diagonal.Starting with A an n× n matrix, form
A0 ≡ A = Q1R1 (14.6)
ThenA1 ≡ R1Q1. (14.7)
In general givenAk = RkQk, (14.8)
obtain Ak+1 byAk = Qk+1Rk+1, Ak+1 = Rk+1Qk+1 (14.9)