QR Factorization - Linear Algebra

SECTION 1

Historical Context & Motivation

ℹ

Prerequisites

This lesson covers QR factorization, a standard topic in an undergraduate linear algebra course. To get the most out of it, you should already be comfortable with: (1) multiplying matrices together, (2) representing vectors as lists of numbers (e.g., [3, 4]), (3) computing dot products, and (4) finding the length (magnitude) of a vector using the Pythagorean theorem. These skills are typically covered earlier in an introductory linear algebra sequence.

Imagine you have a big pile of tangled wires and you need to sort them into neat, organized bundles. That is basically what QR factorization does to a matrix. It takes a complicated matrix and splits it into two simpler matrices — one with perfectly perpendicular columns (called Q) and one that is upper-triangular (called R). This idea grew out of a long history of mathematicians trying to solve systems of equations and understand geometry in higher dimensions.

1883 • Gram–Schmidt Process Formalized

Jørgen Pedersen Gram published work on orthogonalizing sets of functions. This process turns any set of vectors into a set of perpendicular (orthogonal) vectors, forming the backbone of QR factorization.

1907 • Schmidt's Contribution

Erhard Schmidt extended Gram's work to more abstract spaces. The combined method became known as the Gram–Schmidt process, which is now the most common way to build the Q matrix.

1958 • Householder Reflections

Alston Householder introduced reflection-based methods for QR factorization. These approaches produce smaller rounding errors on a computer and became essential for practical algorithms.

1961 • Givens Rotations Popularized

Wallace Givens developed rotation-based techniques to zero out specific entries of a matrix. This method is especially useful for matrices that are already close to triangular.

Modern Era • Everyday Computing

Today, QR factorization powers search engines, data compression, machine learning algorithms, and engineering simulations. It is one of the most frequently used tools in computational mathematics.

The central question QR factorization answers is: How can we rewrite any matrix as a product of an orthogonal matrix and a triangular matrix? Solving this unlocks faster equation solving, better data fitting, and a clearer understanding of the geometry hidden inside matrices.

SECTION 2

Core Principles & Definitions

Before diving into the mechanics of QR factorization, you need a handful of foundational ideas. Each one builds on the last, so take them in order. If you are comfortable with basic matrix multiplication and the idea of vectors as arrows in space, you are ready to go.

Orthogonal Vectors

Two vectors are orthogonal (perpendicular) when their dot product equals zero. Think of the x-axis and y-axis on a graph — they point in completely independent directions. The dot product of two vectors [a, b] and [c, d] is ac + bd.

Orthonormal Vectors

Vectors that are orthogonal and each have a length (magnitude) of exactly 1 are called orthonormal. You find a vector's length using the Pythagorean theorem: ‖[a, b]‖ = √(a² + b²). These are the building blocks of the Q matrix.

Orthogonal Matrix (Q)

A square matrix whose columns are all orthonormal is called an orthogonal matrix. A special property: its transpose equals its inverse, so Q^TQ = I (the identity matrix). In plain terms: multiplying by Q rotates or reflects vectors without changing their lengths.

Upper-Triangular Matrix (R)

An upper-triangular matrix has all zeros below the main diagonal. For example: [a, b; 0, c]. It looks like a staircase going from top-left to bottom-right. This shape makes solving equations much faster.

The Factorization A = QR

QR factorization states that any matrix A whose columns do not overlap or cancel each other out (technically, columns that are "linearly independent" — no column is a combination of the others) can be written as A = QR, where Q is orthogonal and R is upper-triangular.

✦

KEY TAKEAWAY

Think of QR factorization like organizing a messy closet. Your original matrix A is the cluttered closet. The Q matrix is like sorting everything onto perfectly aligned, perpendicular shelves. The R matrix is a simple set of instructions that tells you exactly how much of each item goes on each shelf. Together, Q and R rebuild the original closet perfectly — but now you can find everything easily.

SECTION 3

Visual Explanation

The diagram below shows the big picture of QR factorization in two dimensions. On the left you see two original column vectors of matrix A. In the middle, the Gram–Schmidt process converts them into orthonormal vectors (the columns of Q). On the right, the upper-triangular matrix R holds the coefficients that relate Q back to A.

Left: the original column vectors a₁ and a₂ of matrix A point in non-perpendicular directions. Center: after the Gram–Schmidt process, the new vectors q₁ and q₂ are orthonormal (perpendicular and unit length). Right: the upper-triangular matrix R stores the coefficients needed so that Q × R = A.

Notice how the original vectors a₁ and a₂ in the left panel are tilted at an awkward angle relative to each other. After the Gram–Schmidt process, the vectors q₁ and q₂ in the center panel meet at a perfect 90° angle and each has a length of exactly 1. The small square symbol at the corner confirms the right angle. The matrix R on the right is the "recipe" that tells you how to combine the q-vectors to recover the original a-vectors.

SECTION 4

Mathematical Framework

Now let's put the visual ideas into precise formulas. The Gram–Schmidt process is the standard algorithm for computing Q and R. We start with the columns of A and systematically build orthonormal vectors one at a time.

QR FACTORIZATION

A = Q × R

A is the original m × n matrix, Q is an m × n matrix with orthonormal columns, and R is an n × n upper-triangular matrix.

GRAM–SCHMIDT STEP 1: FIRST ORTHONORMAL VECTOR

u₁ = a₁ , q₁ = u₁ / ‖u₁‖

Take the first column a₁ of A. Divide it by its length (‖u₁‖) to get a unit vector q₁. The symbol ‖ ‖ means "magnitude" or "length" of the vector, computed using the Pythagorean theorem.

GRAM–SCHMIDT STEP 2: SUBTRACT PROJECTIONS

u₂ = a₂ − (a₂ · q₁)q₁ , q₂ = u₂ / ‖u₂‖

From the second column a₂, subtract the piece that points along q₁. The dot product (a₂ · q₁) measures how much a₂ overlaps with q₁ — it is the sum of the products of matching components. What remains, u₂, is perpendicular to q₁. Normalize it to get q₂.

BUILDING THE R MATRIX

r₁₁ = ‖u₁‖ , r₁₂ = a₂ · q₁ , r₂₂ = ‖u₂‖

The entries of R come from the dot products and lengths computed during the Gram–Schmidt process. The diagonal entries are the lengths of the u-vectors, and the off-diagonal entries are the dot products of the a-columns with the q-vectors.

💡

Why does this work?

Subtracting the projection is like peeling away the part of a₂ that is "already explained" by q₁. What is left must be perpendicular to q₁. If you had a third column, you would subtract projections along both q₁ and q₂ to get something perpendicular to both. The pattern repeats for as many columns as you have.

SECTION 5

Detailed Breakdown: The Gram–Schmidt Process

The diagram below walks through the Gram–Schmidt process step by step for a 2-column matrix. Follow the arrows from left to right to see how each stage transforms the vectors.

Top row: the three main steps of the Gram–Schmidt process, ending with the orthonormal matrix Q. Bottom panel: how R is assembled from the lengths of intermediate vectors (diagonal) and dot products (off-diagonal). Notice R is upper-triangular — the zero appears in the lower-left.

For a matrix with more than two columns, you repeat the pattern. For the third column a₃, you subtract projections along both q₁ and q₂ before normalizing. For the fourth column, you subtract projections along q₁, q₂, and q₃, and so on. Each new column "looks at" all the orthonormal vectors found so far and removes any overlap with them.

Column of A	Projections to Subtract	Result Before Normalizing
a₁ (first)	None	u₁ = a₁
a₂ (second)	(a₂ · q₁)q₁	u₂ = a₂ − (a₂ · q₁)q₁
a₃ (third)	(a₃ · q₁)q₁ and (a₃ · q₂)q₂	u₃ = a₃ − (a₃ · q₁)q₁ − (a₃ · q₂)q₂

Pattern for Gram–Schmidt: each column subtracts more projections

SECTION 6

Worked Example

Let's find the QR factorization of a concrete 2 × 2 matrix. We will use the Gram–Schmidt process on:

GIVEN MATRIX

A = [ 1 2 ] (first column a₁ = [1, 1], second column a₂ = [2, 0]) [ 1 0 ]

We treat each column as a vector: a₁ = (1, 1) and a₂ = (2, 0).

QR Factorization of a 2×2 Matrix

1
Step 1 — Find the length of a₁

Compute ‖a₁‖ = √(1² + 1²) = √2 ≈ 1.414. This length will become the entry r₁₁ in the R matrix.

‖a₁‖ = √2
2
Step 2 — Normalize a₁ to get q₁

Divide a₁ by its length: q₁ = a₁ / ‖a₁‖ = (1/√2, 1/√2) ≈ (0.707, 0.707). This is the first column of Q.

q₁ = (1/√2, 1/√2)
3
Step 3 — Compute the projection of a₂ onto q₁

The dot product a₂ · q₁ = (2)(1/√2) + (0)(1/√2) = 2/√2 = √2. This value becomes the off-diagonal entry r₁₂.

a₂ · q₁ = √2
4
Step 4 — Subtract the projection to get u₂

u₂ = a₂ − (a₂ · q₁)q₁ = (2, 0) − √2 × (1/√2, 1/√2) = (2, 0) − (1, 1) = (1, −1). This vector is perpendicular to q₁, which you can verify: u₂ · q₁ = (1)(1/√2) + (−1)(1/√2) = 0. ✓

u₂ = (1, −1)
5
Step 5 — Normalize u₂ to get q₂

‖u₂‖ = √(1² + (−1)²) = √2. So q₂ = u₂ / ‖u₂‖ = (1/√2, −1/√2). This is the second column of Q, and r₂₂ = √2.

q₂ = (1/√2, −1/√2)
6
Step 6 — Assemble Q and R

Q = [ 1/√2 1/√2 ] and R = [ √2 √2 ]. You can verify: Q × R = [ (1/√2)(√2)+(1/√2)(0) (1/√2)(√2)+(1/√2)(√2) ] = [1 2] in the first row, and similarly the second row gives [1 0]. That matches A! ✓

Q = [1/√2 1/√2; 1/√2 −1/√2], R = [√2 √2; 0 √2]

SECTION 7

Strengths, Limitations & Comparisons

QR factorization is powerful, but like every tool in mathematics, it has strengths and weaknesses. Understanding these helps you know when QR is the right choice and when another method might be better.

Feature	Strengths ✓	Limitations ✗
Accuracy on a computer	Much more accurate than LU factorization for many matrices. Rounding errors (small mistakes computers make with decimals) stay small.	Classical Gram–Schmidt can lose accuracy for nearly parallel vectors. Modified Gram–Schmidt or Householder reflections fix this.
Speed	Efficient for finding best-fit solutions to overdetermined systems (more equations than unknowns).	Slower than LU factorization for simple square systems of equations.
Applicability	Works on any matrix whose columns are independent (no column is a combination of the others) — it does not need to be square.	If columns are dependent (one column is a combination of others), the process breaks down (you get a zero vector during normalization).
Geometric insight	Q preserves lengths and angles — multiplying by Q is like rotating or reflecting without stretching, so the geometry of your data is not distorted.	The factorization is not unique unless we require the diagonal entries of R to be positive.

Strengths and limitations of QR factorization

✦

KEY TAKEAWAY

QR factorization is like a Swiss Army knife — it is not always the fastest tool for a single specific task, but it is incredibly reliable and works well in a huge variety of situations. When you need to solve equations, fit data, or analyze a matrix's structure, QR is often the safest bet.

SECTION 8

Connection to Advanced Theory

QR factorization is not just a stand-alone technique — it connects to some of the most important ideas in advanced linear algebra and data science. Here is how it fits into the bigger picture. These topics go beyond this lesson and are typically studied in a later course on numerical linear algebra or applied matrix methods, but it is useful to know where QR factorization leads.

QR Factorization (this lesson)	Advanced Topic	How They Connect
A = QR	Least-Squares Regression	To find the best-fit line through data, you need to solve a system with more equations than unknowns. With QR, this simplifies to solving Rx = Qᵀb, a triangular system solved by back substitution — very fast and accurate.
Q has orthonormal columns	QR Algorithm for Eigenvalues	An eigenvalue of a matrix A is a special number λ where A stretches a vector by exactly the factor λ. By repeatedly computing A = QR and then forming A' = RQ, the matrix converges to a form that reveals these special stretching factors. This is how computers find eigenvalues in practice.
Gram–Schmidt orthogonalization	Singular Value Decomposition (SVD)	SVD is a more powerful factorization that splits any matrix into three parts: UΣVᵀ. It is used in image compression and data analysis. QR factorization often serves as a building block in the algorithms that compute SVD.
R is upper-triangular	Back Substitution	Because R is triangular, solving Rx = c starts at the bottom row and works up. Each variable is found one at a time — very fast and clean.

How QR factorization connects to advanced topics

As you continue studying linear algebra, you will encounter eigenvalues (special scaling factors of a matrix), singular value decomposition (a more powerful three-part matrix factorization used in image compression and data analysis), and principal component analysis (a technique for finding the most important patterns in large datasets). All of these rely on the same core idea: breaking a matrix into simpler parts. Mastering QR factorization gives you a strong foundation for all of them.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

In the factorization A = QR, what special property do the columns of Q have? Why is this property useful?

Show answer

The columns of Q are orthonormal — they are mutually perpendicular (orthogonal) and each has a length of exactly 1. This is useful because orthonormal vectors simplify computations dramatically. For example, the inverse of Q is simply its transpose (Qᵀ), which means you never have to do expensive matrix inversion. It also means multiplying by Q rotates or reflects vectors without changing their lengths or the angles between them, so the geometry of the data is preserved.

Question 2: BASIC CALCULATION

Given a₁ = (3, 4), find q₁ (the normalized version of a₁) and the value of r₁₁.

Show answer

First, compute the length: ‖a₁‖ = √(3² + 4²) = √(9 + 16) = √25 = 5. Then q₁ = a₁ / ‖a₁‖ = (3/5, 4/5) = (0.6, 0.8). The diagonal entry r₁₁ equals the length ‖a₁‖ = 5. You can verify that q₁ has unit length: √(0.6² + 0.8²) = √(0.36 + 0.64) = √1 = 1. ✓

Question 3: INTERMEDIATE

Perform QR factorization on A = [1 0; 0 1; 1 1]. This is a 3×2 matrix. Find Q (3×2) and R (2×2).

Show answer

Column a₁ = (1, 0, 1). Its length is ‖a₁‖ = √(1+0+1) = √2, so q₁ = (1/√2, 0, 1/√2) and r₁₁ = √2. For a₂ = (0, 1, 1): compute a₂ · q₁ = (0)(1/√2) + (1)(0) + (1)(1/√2) = 1/√2. So the projection is (1/√2)q₁ = (1/2, 0, 1/2). Then u₂ = a₂ − projection = (0 − 1/2, 1 − 0, 1 − 1/2) = (−1/2, 1, 1/2). The length ‖u₂‖ = √(1/4 + 1 + 1/4) = √(3/2) = √6/2. So q₂ = u₂/‖u₂‖ = (−1/√6, 2/√6, 1/√6). The entries are r₁₂ = 1/√2 and r₂₂ = √6/2. Final answer: Q = [1/√2 −1/√6; 0 2/√6; 1/√2 1/√6] and R = [√2 1/√2; 0 √6/2].

Question 4: APPLIED

A scientist collects three data points and sets up the equation Ax = b, where A = [1 1; 1 2; 1 3] and b = (2, 3, 5). Explain how QR factorization helps find the best-fit line through these points (the least-squares solution).

Show answer

The system Ax = b has 3 equations but only 2 unknowns, so it likely has no exact solution. The least-squares approach finds the values of x that make the total squared error as small as possible — this gives the best-fit line. Normally you would rearrange to solve a related system, but that approach can introduce inaccuracies with real data. Instead, factor A = QR using Gram–Schmidt. Then the least-squares problem simplifies to Rx = Qᵀb, because QᵀQ = I. Since R is upper-triangular (zeros below the diagonal), you can solve this by back substitution — starting from the last row and working upward. This is faster and more accurate than other approaches.

Question 5: CRITICAL THINKING

Suppose you start the Gram–Schmidt process and after subtracting all projections, you get u₃ = (0, 0, 0) — the zero vector. What does this tell you about the columns of A? Can you still complete the QR factorization? Explain your reasoning.

Show answer

If u₃ = (0, 0, 0), it means the third column a₃ is a combination of the first two columns — in other words, a₃ is completely "explained" by q₁ and q₂, so it adds no new direction. The columns of A are dependent (at least one column can be built from the others). You cannot normalize the zero vector (dividing by ‖0‖ = 0 is undefined), so the standard QR factorization breaks down. However, you can still write a "reduced" QR factorization using only the first two orthonormal vectors. The R matrix would have a row of zeros corresponding to the dependent column. This situation actually reveals important structural information: the column space of A is only 2-dimensional, not 3-dimensional — meaning the matrix cannot span all of 3D space.

SUMMARY

Summary

QR factorization decomposes any matrix A whose columns are independent into the product of an orthogonal matrix Q and an upper-triangular matrix R. The columns of Q are orthonormal — perpendicular and unit-length — and are built using the Gram–Schmidt process, which subtracts projections one column at a time to create independent directions.

The R matrix stores the dot products and vector lengths computed along the way, and its triangular shape makes back substitution simple and fast. QR factorization is widely used in least-squares problems, algorithms that find eigenvalues (special scaling factors of a matrix), and modern computing applications from search engines to machine learning. As you progress further in linear algebra, you will encounter QR factorization again alongside more powerful decompositions like the singular value decomposition (SVD), making it a foundational tool worth mastering now.