QR Factorization

QR factorization writes a matrix A with linearly independent columns as A = QR. The columns of Q are an orthonormal basis for the column space of A, found with the Gram-Schmidt process, and R is an upper triangular matrix with positive numbers on its diagonal. Once you have Q, R = QᵀA.

Before this lesson: Gram-Schmidt Process, Orthogonal Sets and Orthonormal Bases and Transpose of a Matrix

What QR factorization means

The Gram-Schmidt process turns the columns a₁, …, aₙ of A into orthonormal vectors q₁, …, qₙ. QR factorization keeps a record of that work. Q holds the new vectors, and R holds the numbers that rebuild each old column from the new ones.

Gram-Schmidt builds q₁ from a₁ alone, q₂ from a₁ and a₂, and so on. Turned around, a₁ uses only q₁, a₂ uses only q₁ and q₂, and so on. That is why R is upper triangular: column j of R has zeros below row j.

The QR factorization theorem

If A is an m × n matrix with linearly independent columns, then

A = QR, \qquad R = Q^T A

• Q is an m × n matrix whose columns are an orthonormal basis for the column space of A, so QᵀQ = I.
• R is an n × n upper triangular matrix with positive diagonal entries, so R is invertible.
• The entries of R are rᵢᵢ = ‖vᵢ‖ on the diagonal, rᵢⱼ = qᵢ · aⱼ above it, and 0 below it. Here vᵢ is the vector Gram-Schmidt builds before normalizing.
• A square A gives a square Q, which is an orthogonal matrix. A tall A (more rows than columns) gives a tall Q.

How to find a QR factorization

1. Apply the Gram-Schmidt process to the columns of A to get v₁, …, vₙ.
2. Divide each vᵢ by its length to get qᵢ, and put the qᵢ in Q as columns.
3. Compute R = QᵀA. Entries below the diagonal should come out 0.
4. Check that QR = A.

QR factorization examples

Example 1: A 2 × 2 matrix

Find the QR factorization of A = \begin{bmatrix} 3 & 2 \\ 4 & 11 \end{bmatrix}.

v_1 = a_1 = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\quad \|v_1\| = \sqrt{9 + 16} = 5

v_2 = a_2 - \frac{a_2 \cdot v_1}{v_1 \cdot v_1}\,v_1 = \begin{bmatrix} 2 \\ 11 \end{bmatrix} - \frac{50}{25}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} -4 \\ 3 \end{bmatrix}

\|v_2\| = \sqrt{16 + 9} = 5

Q = \frac{1}{5}\begin{bmatrix} 3 & -4 \\ 4 & 3 \end{bmatrix}

R = Q^T A = \frac{1}{5}\begin{bmatrix} 3 & 4 \\ -4 & 3 \end{bmatrix}\begin{bmatrix} 3 & 2 \\ 4 & 11 \end{bmatrix}

= \frac{1}{5}\begin{bmatrix} 9 + 16 & 6 + 44 \\ -12 + 12 & -8 + 33 \end{bmatrix} = \frac{1}{5}\begin{bmatrix} 25 & 50 \\ 0 & 25 \end{bmatrix}

= \begin{bmatrix} 5 & 10 \\ 0 & 5 \end{bmatrix}

QR = \frac{1}{5}\begin{bmatrix} 15 + 0 & 30 - 20 \\ 20 + 0 & 40 + 15 \end{bmatrix} = \frac{1}{5}\begin{bmatrix} 15 & 10 \\ 20 & 55 \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 4 & 11 \end{bmatrix}

Answer: Q = \frac{1}{5}\begin{bmatrix} 3 & -4 \\ 4 & 3 \end{bmatrix} and R = \begin{bmatrix} 5 & 10 \\ 0 & 5 \end{bmatrix}. The diagonal of R holds the lengths 5 and 5, and r₁₂ = q₁ · a₂ = 50/5 = 10.

Example 2: A tall 3 × 2 matrix

Find the QR factorization of A = \begin{bmatrix} 1 & 3 \\ 2 & 3 \\ 2 & 0 \end{bmatrix}.

v_1 = (1, 2, 2),\quad \|v_1\| = \sqrt{1 + 4 + 4} = 3

\frac{a_2 \cdot v_1}{v_1 \cdot v_1} = \frac{3 + 6 + 0}{9} = 1

v_2 = (3 - 1, 3 - 2, 0 - 2) = (2, 1, -2),\quad \|v_2\| = \sqrt{4 + 1 + 4} = 3

Q = \frac{1}{3}\begin{bmatrix} 1 & 2 \\ 2 & 1 \\ 2 & -2 \end{bmatrix}

R = Q^T A = \frac{1}{3}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 1 & -2 \end{bmatrix}\begin{bmatrix} 1 & 3 \\ 2 & 3 \\ 2 & 0 \end{bmatrix}

= \frac{1}{3}\begin{bmatrix} 1 + 4 + 4 & 3 + 6 + 0 \\ 2 + 2 - 4 & 6 + 3 - 0 \end{bmatrix} = \frac{1}{3}\begin{bmatrix} 9 & 9 \\ 0 & 9 \end{bmatrix} = \begin{bmatrix} 3 & 3 \\ 0 & 3 \end{bmatrix}

QR = \frac{1}{3}\begin{bmatrix} 3 + 0 & 3 + 6 \\ 6 + 0 & 6 + 3 \\ 6 + 0 & 6 - 6 \end{bmatrix} = \begin{bmatrix} 1 & 3 \\ 2 & 3 \\ 2 & 0 \end{bmatrix}

Answer: Q = \frac{1}{3}\begin{bmatrix} 1 & 2 \\ 2 & 1 \\ 2 & -2 \end{bmatrix} and R = \begin{bmatrix} 3 & 3 \\ 0 & 3 \end{bmatrix}.

Example 3: A 3 × 3 matrix

Find the QR factorization of A = \begin{bmatrix} 1 & 3 & 1 \\ 2 & 3 & 0 \\ 2 & 0 & 5 \end{bmatrix}. Its columns are the vectors from Example 3 of the Gram-Schmidt lesson.

v_1 = (1, 2, 2),\quad v_2 = (2, 1, -2),\quad v_3' = (2, -2, 1)

\|v_1\| = \|v_2\| = \|v_3'\| = 3

Q = \frac{1}{3}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 1 & -2 \\ 2 & -2 & 1 \end{bmatrix}

R = Q^T A = \frac{1}{3}\begin{bmatrix} 1 + 4 + 4 & 3 + 6 + 0 & 1 + 0 + 10 \\ 2 + 2 - 4 & 6 + 3 - 0 & 2 + 0 - 10 \\ 2 - 4 + 2 & 6 - 6 + 0 & 2 - 0 + 5 \end{bmatrix}

= \frac{1}{3}\begin{bmatrix} 9 & 9 & 11 \\ 0 & 9 & -8 \\ 0 & 0 & 7 \end{bmatrix} = \begin{bmatrix} 3 & 3 & \tfrac{11}{3} \\ 0 & 3 & -\tfrac{8}{3} \\ 0 & 0 & \tfrac{7}{3} \end{bmatrix}

\tfrac{11}{3}q_1 - \tfrac{8}{3}q_2 + \tfrac{7}{3}q_3 = \tfrac{1}{9}(11 - 16 + 14,\ 22 - 8 - 14,\ 22 + 16 + 7) = \tfrac{1}{9}(9, 0, 45) = (1, 0, 5)

Answer: Q = \frac{1}{3}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 1 & -2 \\ 2 & -2 & 1 \end{bmatrix} and R = \begin{bmatrix} 3 & 3 & 11/3 \\ 0 & 3 & -8/3 \\ 0 & 0 & 7/3 \end{bmatrix}. The last diagonal entry, 7/3, is the length of the unscaled v₃ = (14/9, −14/9, 7/9).

Example 4: Solving Ax = b with QR

Use the QR factorization from Example 1 to solve Ax = b, where b = \begin{bmatrix} 1 \\ 18 \end{bmatrix}.

QRx = b \;\Rightarrow\; Rx = Q^T b

Q^T b = \frac{1}{5}\begin{bmatrix} 3(1) + 4(18) \\ -4(1) + 3(18) \end{bmatrix} = \frac{1}{5}\begin{bmatrix} 75 \\ 50 \end{bmatrix} = \begin{bmatrix} 15 \\ 10 \end{bmatrix}

\begin{bmatrix} 5 & 10 \\ 0 & 5 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 15 \\ 10 \end{bmatrix}

5x_2 = 10 \;\Rightarrow\; x_2 = 2

5x_1 + 10(2) = 15

5x_1 = -5 \;\Rightarrow\; x_1 = -1

A\begin{bmatrix} -1 \\ 2 \end{bmatrix} = \begin{bmatrix} -3 + 4 \\ -4 + 22 \end{bmatrix} = \begin{bmatrix} 1 \\ 18 \end{bmatrix}

Answer: x = (−1, 2). No row reduction of A was needed, only one multiplication by Qᵀ and back substitution.

Example 5: Fitting a sales trend line with QR

A shop sold y = (10, 14, 15, 21) units in weeks t = 1, 2, 3, 4. The manager wants the line y = c + mt that fits best. The equations c + mt = y form the system Ax = y with A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \\ 1 & 4 \end{bmatrix} and x = (c, m). No line passes through all four points, so solve Rx = Qᵀy, which gives the best fit.

v_1 = (1, 1, 1, 1),\quad \|v_1\| = 2,\quad q_1 = \tfrac{1}{2}(1, 1, 1, 1)

v_2 = (1, 2, 3, 4) - \tfrac{10}{4}(1, 1, 1, 1) = \left(-\tfrac{3}{2}, -\tfrac{1}{2}, \tfrac{1}{2}, \tfrac{3}{2}\right)

\|v_2\| = \sqrt{\tfrac{9}{4} + \tfrac{1}{4} + \tfrac{1}{4} + \tfrac{9}{4}} = \sqrt{5},\quad q_2 = \tfrac{1}{2\sqrt{5}}(-3, -1, 1, 3)

r_{11} = 2,\quad r_{12} = q_1 \cdot a_2 = \tfrac{1 + 2 + 3 + 4}{2} = 5,\quad r_{22} = \sqrt{5}

q_1 \cdot y = \tfrac{10 + 14 + 15 + 21}{2} = \tfrac{60}{2} = 30

q_2 \cdot y = \tfrac{-30 - 14 + 15 + 63}{2\sqrt{5}} = \tfrac{34}{2\sqrt{5}} = \tfrac{17}{\sqrt{5}}

\sqrt{5}\,m = \tfrac{17}{\sqrt{5}} \;\Rightarrow\; m = \tfrac{17}{5} = 3.4

2c + 5(3.4) = 30 \;\Rightarrow\; 2c = 13 \;\Rightarrow\; c = 6.5

Answer: the best line is y = 6.5 + 3.4t, so sales grow by about 3.4 units a week, and the line predicts 6.5 + 3.4(5) = 23.5 units in week 5. This is the same line as the least-squares regression line for these data.

Common mistakes

Related ideas

QR compared with LU. LU decomposition splits A into triangular pieces using row operations. QR uses an orthonormal Q instead, which keeps rounding errors small, so software often prefers QR for least-squares problems.

Least squares. Example 5 is a preview. When Ax = b has no exact solution, Rx = Qᵀb gives the best approximate solution. Least-Squares Solutions explains why, using the normal equations.

Determinants. For a square A, the determinant of Q is 1 or −1, so |det A| is the product of the diagonal entries of R.

Eigenvalues. Repeating the steps “factor A = QR, then form RQ” gives the QR algorithm, which computers use to find eigenvalues of large matrices.

Practice problems

1. Find the QR factorization of A = [1 4; 2 3].
2. Find the QR factorization of the 3 × 2 matrix whose columns are (1, 0, 1) and (3, 2, 1).
3. Check that QᵀQ = I for the matrix Q in Example 2.
4. Q = [0.6 −0.8; 0.8 0.6] and R = [10 5; 0 5]. Find A = QR.
5. Use your answer to Problem 1 to solve Ax = (3, 1).
6. In any QR factorization, why is r₂₁ = q₂ · a₁ equal to 0?
7. Find the QR factorization of the 3 × 2 matrix whose columns are (2, 1, 2) and (1, 1, 0).
8. Find the QR factorization of A = [3 −4; 4 3], whose columns are already orthogonal.
9. Use the QR factorization from Example 1 to find det A.
10. Sales in weeks 1 to 4 were y = (8, 9, 13, 14). Use Q and R from Example 5 to find the best line y = c + mt.

v_1 = (1, 2),\quad v_2 = (4, 3) - 2(1, 2) = (2, -1)

\|v_1\| = \|v_2\| = \sqrt{5},\quad Q = \tfrac{1}{\sqrt{5}}\begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}

R = Q^T A = \tfrac{1}{\sqrt{5}}\begin{bmatrix} 1 + 4 & 4 + 6 \\ 2 - 2 & 8 - 3 \end{bmatrix} = \tfrac{1}{\sqrt{5}}\begin{bmatrix} 5 & 10 \\ 0 & 5 \end{bmatrix}

= \begin{bmatrix} \sqrt{5} & 2\sqrt{5} \\ 0 & \sqrt{5} \end{bmatrix}

v_1 = (1, 0, 1),\quad v_2 = (3, 2, 1) - 2(1, 0, 1) = (1, 2, -1)

\|v_1\| = \sqrt{2},\quad \|v_2\| = \sqrt{6}

Q = \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{6} \\ 0 & 2/\sqrt{6} \\ 1/\sqrt{2} & -1/\sqrt{6} \end{bmatrix}

r_{11} = \sqrt{2},\quad r_{12} = \tfrac{3 + 0 + 1}{\sqrt{2}} = \tfrac{4}{\sqrt{2}} = 2\sqrt{2},\quad r_{22} = \tfrac{3 + 4 - 1}{\sqrt{6}} = \tfrac{6}{\sqrt{6}} = \sqrt{6}

Q^T Q = \tfrac{1}{9}\begin{bmatrix} 1 + 4 + 4 & 2 + 2 - 4 \\ 2 + 2 - 4 & 4 + 1 + 4 \end{bmatrix} = \tfrac{1}{9}\begin{bmatrix} 9 & 0 \\ 0 & 9 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix}

QR = \begin{bmatrix} 0.6(10) + (-0.8)(0) & 0.6(5) + (-0.8)(5) \\ 0.8(10) + 0.6(0) & 0.8(5) + 0.6(5) \end{bmatrix}

= \begin{bmatrix} 6 & 3 - 4 \\ 8 & 4 + 3 \end{bmatrix} = \begin{bmatrix} 6 & -1 \\ 8 & 7 \end{bmatrix}

Q^T b = \tfrac{1}{\sqrt{5}}(3 + 2,\ 6 - 1) = \tfrac{1}{\sqrt{5}}(5, 5) = (\sqrt{5}, \sqrt{5})

\sqrt{5}\,x_2 = \sqrt{5} \;\Rightarrow\; x_2 = 1

\sqrt{5}\,x_1 + 2\sqrt{5}(1) = \sqrt{5} \;\Rightarrow\; x_1 = -1

a_1 = r_{11}q_1

q_2 \cdot a_1 = r_{11}(q_2 \cdot q_1) = r_{11}(0) = 0

v_1 = (2, 1, 2),\quad v_2' = (1, 2, -2),\quad \|v_1\| = \|v_2'\| = 3

Q = \tfrac{1}{3}\begin{bmatrix} 2 & 1 \\ 1 & 2 \\ 2 & -2 \end{bmatrix}

R = Q^T A = \tfrac{1}{3}\begin{bmatrix} 4 + 1 + 4 & 2 + 1 + 0 \\ 2 + 2 - 4 & 1 + 2 + 0 \end{bmatrix} = \begin{bmatrix} 3 & 1 \\ 0 & 1 \end{bmatrix}

(3, 4) \cdot (-4, 3) = -12 + 12 = 0

\|a_1\| = \|a_2\| = 5,\quad Q = \tfrac{1}{5}\begin{bmatrix} 3 & -4 \\ 4 & 3 \end{bmatrix}

R = Q^T A = \tfrac{1}{5}\begin{bmatrix} 9 + 16 & -12 + 12 \\ -12 + 12 & 16 + 9 \end{bmatrix} = \begin{bmatrix} 5 & 0 \\ 0 & 5 \end{bmatrix}

\det Q = \tfrac{9}{25} + \tfrac{16}{25} = 1,\quad \det R = 5 \cdot 5 = 25

\det A = \det Q \cdot \det R = 1 \cdot 25 = 25

q_1 \cdot y = \tfrac{8 + 9 + 13 + 14}{2} = 22,\quad q_2 \cdot y = \tfrac{-24 - 9 + 13 + 42}{2\sqrt{5}} = \tfrac{11}{\sqrt{5}}

\sqrt{5}\,m = \tfrac{11}{\sqrt{5}} \;\Rightarrow\; m = 2.2

2c + 5(2.2) = 22 \;\Rightarrow\; c = 5.5

QR factorization FAQ

What is QR factorization used for?

It is used to solve least-squares problems, to solve linear systems in a numerically stable way and, through the QR algorithm, to find eigenvalues.

How do you find R in a QR factorization?

After you build Q with the Gram-Schmidt process, multiply R = QᵀA. The diagonal entries are the lengths of the Gram-Schmidt vectors, and the entries below the diagonal are 0.

Does every matrix have a QR factorization?

Every matrix with linearly independent columns has one, with positive diagonal entries in R, and it is unique. Matrices with dependent columns also have QR factorizations, but they need methods beyond basic Gram-Schmidt.

What is the difference between QR and LU decomposition?

LU writes A as a lower triangular matrix times an upper triangular matrix using row operations. QR writes A as a matrix with orthonormal columns times an upper triangular matrix, and it works for tall matrices too.

Summary

• A = QR, where Q has orthonormal columns and R is upper triangular with a positive diagonal.
• Build Q with the Gram-Schmidt process on the columns of A, then normalize.
• Find R = QᵀA. Its diagonal holds the lengths ‖vᵢ‖, and its entries below the diagonal are 0.
• To solve Ax = b, solve the triangular system Rx = Qᵀb by back substitution.
• For a tall A, the same steps give the best-fit (least-squares) solution.

Previous lesson: Gram-Schmidt Process

Next lesson: Least-Squares Solutions

Back to the Linear Algebra Index