LINEAR-ALGEBRA · Unit 16 · Video 4 · Interactive Practice

Why Gram-Schmidt Secretly Builds an Upper Triangular Matrix

IKey Formulas

Formula	Name	Description
$A = QR$	QR Factorization	$Q$ has orthonormal columns, $R$ is upper triangular
$r_{ij} = \mathbf{q}_i^\top \mathbf{a}_j$	Entry of $R$	Inner product of $i$ -th Q-column with $j$ -th A-column
$R = Q^\top A$	Direct formula	Follows from $Q^\top Q = I$
$Q^{-1} = Q^\top$	Orthonormal inverse	The power of orthonormality

IIVisualization 1 — Filling R Column by Column

With $A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}$ , each Gram-Schmidt step rewrites one column of $A$ in the orthonormal $\mathbf{q}$ -basis, filling exactly one column of $R$ .

Gram-Schmidt step 0

IIIVisualization 2 — Why the Sub-Diagonal Zeros Appear

Gram-Schmidt forces $\mathbf{q}_2 \perp \operatorname{span}\{\mathbf{a}_1\}$ , so $r_{21} = \mathbf{q}_2^\top \mathbf{a}_1 = 0$ for every pair of vectors.

💡 If $\mathbf{a}_1$ and $\mathbf{a}_2$ line up, $r_{22} = 0$ and Gram-Schmidt breaks down — the columns must be linearly independent.

IVVisualization 3 — R Is Always Upper Triangular

For any matrix with independent columns, $A = QR$ yields an upper-triangular $R$ — the sub-diagonal zeros are guaranteed by orthogonality.

Choose A

💡 Equivalently $R = Q^\top A$ , since $Q^\top Q = I$ — once you have $Q$ , no Gram-Schmidt is needed.

VQuiz Questions

Question 1

In the QR factorization $A = QR$ , what does the entry $r_{ij}$ (row $i$ , column $j$ of $R$ ) equal?

✅ Correct! Each R entry is the inner product of a Q-column with an A-column.

❌ Not quite. Think about what $R = Q^\top A$ tells us about individual entries: row $i$ , column $j$ of $R$ is $\mathbf{q}_i^\top \mathbf{a}_j$ .

Show solution

Solution:

Each entry of $R$ is computed as: $r_{ij} = \mathbf{q}_i^\top \mathbf{a}_j$

This is the dot product of the $i$ -th column of $Q$ with the $j$ -th column of $A$ .

This follows directly from $R = Q^\top A$ : the $(i,j)$ entry of $Q^\top A$ is $\mathbf{q}_i^\top \mathbf{a}_j$ .

Question 2

Why is $r_{21} = \mathbf{q}_2^\top \mathbf{a}_1 = 0$ in the QR factorization?

✅ Correct! The zeros are forced by Gram-Schmidt's orthogonalization — by construction, not coincidence.

❌ Not quite. The zeros aren't a convention or coincidence — they're a consequence of how Gram-Schmidt builds each q vector perpendicular to the span of earlier columns.

Show solution

Solution:

Gram-Schmidt builds $\mathbf{q}_2$ by subtracting from $\mathbf{a}_2$ its projection onto $\mathbf{q}_1$ : $\mathbf{v}_2 = \mathbf{a}_2 - (\mathbf{q}_1^\top \mathbf{a}_2)\,\mathbf{q}_1$

This makes $\mathbf{v}_2$ (and hence $\mathbf{q}_2 = \mathbf{v}_2/\|\mathbf{v}_2\|$ ) perpendicular to $\text{span}\{\mathbf{a}_1\}$ .

Since $\mathbf{a}_1 \in \text{span}\{\mathbf{a}_1\}$ , we get $\mathbf{q}_2^\top \mathbf{a}_1 = 0$ .

In general: for $i > j$ , $\mathbf{q}_i \perp \text{span}\{\mathbf{a}_1, \ldots, \mathbf{a}_{i-1}\}$ and $\mathbf{a}_j$ lives in that span (since $j < i$ ), so $r_{ij} = \mathbf{q}_i^\top \mathbf{a}_j = 0$ .

The zeros are forced by construction, not by convention.

Question 3

True or False: If $Q$ is the matrix with orthonormal columns from $A = QR$ , then $Q^{-1} = Q^\top$ .

✅ Correct! Orthonormal columns give $Q^\top Q = I$ , so $Q^{-1} = Q^\top$ . That's the power of orthonormality!

❌ Incorrect. Since $Q$ has orthonormal columns, $Q^\top Q = I$ , which means $Q^{-1} = Q^\top$ .

Show solution

Solution: True

Since $Q$ has orthonormal columns: $Q^\top Q = I$ .

For a square matrix, this means $Q^{-1} = Q^\top$ .

This is what makes QR especially powerful:

Inverting $Q$ is trivial — just transpose it!
This gives us $R = Q^\top A$ directly from $A = QR$ : $A = QR \;\Longrightarrow\; Q^\top A = Q^\top QR = IR = R$

Compare with LU, where computing $L^{-1}$ requires actual work.

Question 4

When using QR factorization to solve the least-squares problem $A\mathbf{x} \approx \mathbf{b}$ , what system do you actually solve?

✅ Correct! QR turns least squares into simple back-substitution, avoiding the numerically dangerous $A^\top A$ .

❌ Close, but not the QR approach. The normal equations work but are numerically unstable. The whole point of QR is to avoid forming $A^\top A$ ! Instead: $R\mathbf{x} = Q^\top \mathbf{b}$ .

❌ Not quite. Start from $A = QR$ , multiply both sides by $Q^\top$ , and use $Q^\top Q = I$ to get $R\mathbf{x} = Q^\top \mathbf{b}$ .

Show solution

Solution:

Starting from $A\mathbf{x} \approx \mathbf{b}$ with $A = QR$ :

Substitute: $QR\mathbf{x} \approx \mathbf{b}$
Multiply left by $Q^\top$ : $Q^\top QR\mathbf{x} = Q^\top \mathbf{b}$
Since $Q^\top Q = I$ : $R\mathbf{x} = Q^\top \mathbf{b}$

Since $R$ is upper triangular, we solve by back-substitution — fast and numerically stable.

The normal equations $A^\top A\mathbf{x} = A^\top \mathbf{b}$ also work, but forming $A^\top A$ amplifies numerical errors. QR avoids this entirely, which is why it's preferred in practice.

Solved: 0 / 4