Solved Exercises on QR Decomposition Introduction in Linear Algebra

Master QR decomposition: Gram-Schmidt process, orthogonal matrices, and matrix factorization through these 5 detailed exercises.

QR Decomposition Fundamentals
\(A = QR\)
QR Decomposition Formula
Key Definitions:

QR Decomposition: Any matrix A can be factored as A = QR where Q is orthogonal and R is upper triangular

Orthogonal Matrix: Q^T Q = I (columns are orthonormal vectors)

Upper Triangular Matrix: All entries below diagonal are zero

Gram-Schmidt Process:
  1. Start with linearly independent vectors {v₁, v₂, ..., vₙ}
  2. Initialize: u₁ = v₁, e₁ = u₁/||u₁||
  3. Iterate: For k = 2 to n, uₖ = vₖ - Σᵢ₌₁ᵏ⁻¹ projuᵢ(vₖ)
  4. Normalize: eₖ = uₖ/||uₖ||
Tip 1: Always normalize vectors to get orthonormal basis.
Tip 2: Check orthogonality by computing dot products.
Tip 3: Verify A = QR by matrix multiplication.
Tip 4: Use projection formula: proju(v) = (u·v)/(u·u) × u
Key Properties: Q^T = Q^(-1), ||Qx|| = ||x||, determinant of Q is ±1
Applications: Least squares, eigenvalue computation, solving linear systems
Essential Formulas:

• Vector projection: proju(v) = (u·v)/(u·u) × u

• Gram-Schmidt: uₖ = vₖ - Σᵢ₌₁ᵏ⁻¹ projuᵢ(vₖ)

• Normalization: eₖ = uₖ/||uₖ||

• Orthogonal matrix: Q^T Q = I

Solution: Exercises 1 to 3
1 Basic QR Decomposition
Exercise 1
Find the QR decomposition of: A =
[
3
1
4
0
]
Definition:

QR Decomposition: A = QR where Q has orthonormal columns and R is upper triangular

Gram-Schmidt Method:
  1. Take columns of A as input vectors
  2. Apply Gram-Schmidt process
  3. Form Q from normalized vectors
  4. Compute R using inner products
Step 1: Identify column vectors

v₁ = [3, 4], v₂ = [1, 0]

Step 2: Apply Gram-Schmidt process

u₁ = v₁ = [3, 4]

||u₁|| = √(3² + 4²) = √25 = 5

e₁ = u₁/||u₁|| = [3/5, 4/5]

Step 3: Compute u₂

proju₁(v₂) = (u₁·v₂)/(u₁·u₁) × u₁

u₁·v₂ = 3×1 + 4×0 = 3

u₁·u₁ = 3² + 4² = 25

proju₁(v₂) = (3/25) × [3, 4] = [9/25, 12/25]

u₂ = v₂ - proju₁(v₂) = [1, 0] - [9/25, 12/25] = [16/25, -12/25]

Step 4: Normalize u₂

||u₂|| = √((16/25)² + (-12/25)²) = √(256 + 144)/25 = √400/25 = 20/25 = 4/5

e₂ = u₂/||u₂|| = [16/25, -12/25] ÷ (4/5) = [4/5, -3/5]

Step 5: Form matrices Q and R

Q = [e₁ e₂] =

[
3/5
4/5
4/5
-3/5
]

R =

[
||u₁||
e₁·v₂
0
||u₂||
]
=
[
5
3/5
0
4/5
]

Q =
[
3/5
4/5
4/5
-3/5
]
, R =
[
5
3/5
0
4/5
]
Final answer:

A = QR where Q has orthonormal columns and R is upper triangular

Applied rules:

• Gram-Schmidt: Orthogonalize vectors systematically

• Normalization: Divide by norm to get unit vectors

• Projection: Remove components parallel to previous vectors

2 3x3 Matrix QR
Exercise 2
Find QR decomposition of: A =
[
1
1
0
1
0
1
0
1
1
]
Definition:

3x3 QR Decomposition: Extend Gram-Schmidt to higher dimensions

Step 1: Identify column vectors

v₁ = [1, 1, 0], v₂ = [1, 0, 1], v₃ = [0, 1, 1]

Step 2: Compute u₁ and e₁

u₁ = v₁ = [1, 1, 0]

||u₁|| = √(1² + 1² + 0²) = √2

e₁ = [1/√2, 1/√2, 0]

Step 3: Compute u₂

proju₁(v₂) = (u₁·v₂)/(u₁·u₁) × u₁ = (1×1 + 1×0 + 0×1)/(1² + 1² + 0²) × [1, 1, 0] = (1/2) × [1, 1, 0] = [1/2, 1/2, 0]

u₂ = v₂ - proju₁(v₂) = [1, 0, 1] - [1/2, 1/2, 0] = [1/2, -1/2, 1]

||u₂|| = √((1/2)² + (-1/2)² + 1²) = √(1/4 + 1/4 + 1) = √3/2

e₂ = [1/(√6), -1/(√6), 2/(√6)]

Step 4: Compute u₃

proju₁(v₃) = (u₁·v₃)/(u₁·u₁) × u₁ = (1×0 + 1×1 + 0×1)/2 × [1, 1, 0] = [1/2, 1/2, 0]

proju₂(v₃) = (u₂·v₃)/(u₂·u₂) × u₂ = (1/2×0 + (-1/2)×1 + 1×1)/3/2 × [1/2, -1/2, 1] = (1/2)/(3/2) × [1/2, -1/2, 1] = [1/6, -1/6, 1/3]

u₃ = v₃ - proju₁(v₃) - proju₂(v₃) = [0, 1, 1] - [1/2, 1/2, 0] - [1/6, -1/6, 1/3] = [-2/3, 2/3, 2/3]

Q =
[
1/√2
1/√6
-1/√3
1/√2
-1/√6
1/√3
0
2/√6
1/√3
]
, R =
[
√2
1/√2
1/√2
0
√3/2
1/√6
0
0
2/√3
]
Final answer:

Q has orthonormal columns, R is upper triangular

Applied rules:

• Higher dimensions: Extend Gram-Schmidt iteratively

• Multiple projections: Subtract all previous projections

• Orthogonality check: Verify eᵢ·eⱼ = 0 for i ≠ j

3 Verification Exercise
Exercise 3
Verify that the matrices Q and R from Exercise 1 satisfy A = QR
Definition:

Verification: Confirm QR decomposition by computing QR and comparing to A

Step 1: Recall matrices from Exercise 1

Q =

[
3/5
4/5
4/5
-3/5
]
, R =
[
5
3/5
0
4/5
]

Step 2: Compute QR

QR =

[
(3/5)×5 + (4/5)×0
(3/5)×(3/5) + (4/5)×(4/5)
(4/5)×5 + (-3/5)×0
(4/5)×(3/5) + (-3/5)×(4/5)
]

=

[
3
9/25 + 16/25
4
12/25 - 12/25
]
=
[
3
1
4
0
]

QR =
[
3
1
4
0
]
= A ✓
Final answer:

QR = A, confirming our decomposition is correct

Applied rules:

• Matrix multiplication: Row by column rule

• Verification: Essential to confirm correctness

• Arithmetic: Careful calculation of fractions

Solution: Exercises 4 to 5
4 Orthogonal Matrix Properties
Exercise 4
Prove that Q from Exercise 1 is orthogonal: Q^T Q = I
Definition:

Orthogonal Matrix: Q is orthogonal if Q^T Q = I (identity matrix)

Step 1: Recall matrix Q from Exercise 1

Q =

[
3/5
4/5
4/5
-3/5
]

Step 2: Compute transpose Q^T

Q^T =

[
3/5
4/5
4/5
-3/5
]
(since Q is symmetric in this case)

Step 3: Compute Q^T Q

Q^T Q =

[
(3/5)×(3/5) + (4/5)×(4/5)
(3/5)×(4/5) + (4/5)×(-3/5)
(4/5)×(3/5) + (-3/5)×(4/5)
(4/5)×(4/5) + (-3/5)×(-3/5)
]

=

[
9/25 + 16/25
12/25 - 12/25
12/25 - 12/25
16/25 + 9/25
]
=
[
1
0
0
1
]
= I

Q^T Q = I =
[
1
0
0
1
]
✓
Final answer:

Q is indeed orthogonal since Q^T Q = I

Applied rules:

• Transpose property: (Q^T)ᵢⱼ = Qⱼᵢ

• Orthogonality: Columns are orthonormal vectors

• Identity verification: Diagonal ones, off-diagonal zeros

5 Application Problem
Exercise 5
Solve the system Ax = b using QR decomposition where A =
[
3
1
4
0
]
and b =
[
5
6
]
Definition:

QR Solution Method: Ax = b becomes QRx = b, then Rx = Q^T b

Step 1: Use QR decomposition from Exercise 1

Q =

[
3/5
4/5
4/5
-3/5
]
, R =
[
5
3/5
0
4/5
]

Step 2: Transform the system

Ax = b → QRx = b → Rx = Q^T b

Step 3: Compute Q^T b

Q^T b =

[
3/5
4/5
4/5
-3/5
]
[
5
6
]
=
[
(3/5)×5 + (4/5)×6
(4/5)×5 + (-3/5)×6
]
=
[
3 + 24/5 = 39/5
4 - 18/5 = 2/5
]

Step 4: Solve Rx = Q^T b by back substitution

[
5
3/5
0
4/5
]
[
x₁
x₂
]
=
[
39/5
2/5
]

From second equation: (4/5)x₂ = 2/5 → x₂ = 1/2

From first equation: 5x₁ + (3/5)(1/2) = 39/5 → 5x₁ + 3/10 = 39/5 → 5x₁ = 39/5 - 3/10 = 78/10 - 3/10 = 75/10 = 15/2 → x₁ = 3/2

x =
[
3/2
1/2
]
Final answer:

x₁ = 3/2, x₂ = 1/2

Applied rules:

• QR method: More stable than direct inversion

• Back substitution: Solve upper triangular systems efficiently

• Orthogonality advantage: Q^T = Q^(-1) simplifies computation

Questions & Answers

Question: I don't understand why we need QR decomposition when we can just solve systems directly. What makes QR decomposition special?

Answer: Great question! QR decomposition offers several advantages over direct methods:

  • Numerical stability: QR is more stable than Gaussian elimination for ill-conditioned matrices
  • Least squares problems: QR naturally handles overdetermined systems (more equations than unknowns)
  • Eigenvalue computation: QR algorithm is fundamental for finding eigenvalues
  • Geometric insight: Shows the underlying structure of the transformation

In Exercise 5, notice how Q^T acts as a rotation/reflection that preserves lengths (orthogonal matrices preserve norms), making the system easier to solve via back substitution on the triangular matrix R.

Direct methods like Cramer's rule become computationally expensive for large matrices (O(n!) vs O(n³) for QR), making QR more practical for real applications.

Question: In the Gram-Schmidt process, why do we subtract projections from the original vector? What's the geometric intuition?

Answer: The geometric intuition is beautiful! When we compute uₖ = vₖ - Σᵢ₌₁ᵏ⁻¹ projuᵢ(vₖ), we're:

  • Removing components: Taking out all parts of vₖ that lie in the span of {u₁, u₂, ..., uₖ₋₁}
  • Creating perpendicularity: Making uₖ orthogonal to all previous vectors
  • Preserving direction: Keeping only the part of vₖ that extends beyond the existing subspace

Think of it like this: if vₖ represents a direction, subtracting its projections onto previous directions gives us the "new" part of vₖ that's perpendicular to everything we've already found. This ensures our new vector is orthogonal to all previous ones.

In Exercise 2, when we computed u₂, we removed the part of v₂ that was parallel to u₁, leaving only the component of v₂ that's perpendicular to u₁.

Question: How can I quickly verify if my QR decomposition is correct without manually multiplying the matrices?

Answer: Here are quick verification checks for QR decomposition:

  1. Check R is upper triangular: All entries below main diagonal should be 0
  2. Check orthogonality of Q: Verify columns of Q have unit length and are mutually orthogonal
  3. Check dimensions: If A is m×n, then Q is m×n and R is n×n
  4. Verify rank preservation: rank(A) = rank(R)

For Q, check that ||qᵢ|| = 1 for each column qᵢ, and qᵢ · qⱼ = 0 for i ≠ j. For R, verify Rᵢⱼ = 0 when i > j.

In Exercise 1, we verified Q^T Q = I to confirm orthogonality. This is often faster than full matrix multiplication for verification purposes.