Introduction to Matrix Decomposition

Solving systems like $A \vec{x} = \vec{b}$ can be computationally intensive, especially for large systems.

Matrix decomposition simplifies this process by breaking matrix $A$ into simpler parts — which we can then solve in stages.

LU vs QR – When and Why

We decompose the matrix $A$ into other structured matrices.

LU Decomposition

Break $A$ into a Lower and Upper triangular matrix:

Built using Gaussian elimination
Works best for square matrices

A = LU

QR Decomposition

Break $A$ into an Orthogonal and Upper matrix:

Often used for non-square matrices
Ideal for least squares problems or when LU fails

A = QR

LU Decomposition – Setup

Start with a square matrix:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Our goal is to write this as:

A = LU

Where:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

This decomposition is possible if A is square and invertible.

Important Points:

Lower triangular matrices have all zero entries above the diagonal, simplifying forward substitution;
Upper triangular matrices have zeros below the diagonal, making backward substitution straightforward;
An orthogonal matrix has columns that are orthonormal vectors (vectors of length 1 that are perpendicular);
This property preserves vector length and angles, which is useful in solving least squares and improving numerical stability.

Gaussian Elimination

Apply Gaussian elimination to eliminate the entry below the top-left pivot:

R_2 \rarr R_2 - \frac{6}{4}R_1

This gives us:

R'_2 = [0, -1.5]

So the updated matrices become:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

And from our row operation, we know:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Important Points:

Gaussian elimination systematically eliminates entries below the pivot element in each column by subtracting scaled versions of the pivot row from the rows beneath;
This process transforms A into an upper triangular matrix U.
The multipliers used to eliminate these entries are stored in L, allowing us to represent A as the product LU.

Final Result – LU Decomposition Complete

We verify:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Now the system $A \vec{x} = \vec{b}$ can be solved in two steps:

Solve $L \vec{y} = \vec{b}$ by forward substitution;
Solve $U \vec{x} = \vec{y}$ by backward substitution.

QR Decomposition – Concept Overview

We want to express a matrix $A$ as a product of two matrices:

A = QR

Where:

$A$ is your input matrix (e.g. data, coefficients, etc.);
$Q$ is an orthogonal matrix (its columns are orthonormal vectors);
$R$ is an upper triangular matrix.

An example shape breakdown:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

This decomposition is often used when:

Matrix A is not square;
Solving least squares problems;
LU decomposition isn't stable.

What Are Orthonormal Vectors?

Orthogonal vectors

Two vectors $u, v$ are orthogonal if their dot product is zero: $u \cdot v = 0$

Normalized vector

A vector $u$ is normalized when $|u| = 1$

Orthonormal set

A set of vectors $\{q_1, q_2, ..., q_k\}$ is orthonormal if each is unit length and they are mutually orthogonal:

q_i \cdot q_j = \begin{cases} 1,\ \text{if}\ \ i = j,\\ 0,\ \text{if}\ \ i \neq j. \end{cases}

Why it matters: orthonormal columns in $Q$ preserve geometry, simplify projections, and improve numerical stability.

QR Decomposition - Setup

Define the Matrix A

Let's start with this example:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

We will use the Gram-Schmidt process to find matrices $Q$ and $R$ such that $A=QR$ . The Gram-Schmidt process creates an orthonormal set of vectors from the columns of $A$ .

This means the vectors in $Q$ are all perpendicular (orthogonal) to each other and have unit length (normalized). This property simplifies many calculations and improves numerical stability when solving systems.

So, here the goal is to:

Make the columns of $Q$ orthonormal;
Create the matrix $R$ which will encode the projections.

Compute First Basis Vector

We extract the first column of $A$ :

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

To normalize this, we compute the norm:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Then:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

This is the first orthonormal vector for $Q$ .

How to Normalize a Vector

Given a vector:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

We compute its norm:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Then normalize:

\hat{v} = \frac{1}{|v|}v

Example:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

So, our normalized vector is:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Once we know how to normalize and orthogonalize vectors, we can apply the Gram-Schmidt process to form the $Q$ matrix, and use it to compute $R$ in the QR decomposition.

Compute q₂ Using Gram-Schmidt

To compute $q_2$ , we start with the second column of $A$ :

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Next, you project $a_2$ onto $q_1$ :

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Remove the projection from $a_2$ :

u_2 = a_2 - r_{12}q_1

Then normalize (as was shown above):

q_2 = \frac{u_2}{|u_2|}

Now both $q_1$ and $q_2$ form the orthonormal basis for $Q$ . You now assemble the final result:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

These satisfy:

A = QR

Quiz

1. What is the shape of matrix $R$ in QR decomposition for a $3 \times 2$ matrix $A$ ?

2. Which of the following correctly defines an orthonormal column vector?

3. If $u \cdot v = 0$ and $|u| = 1$ , what identity holds true?

4. What is the first step in the Gram-Schmidt process for QR decomposition?

5. In QR decomposition using Gram-Schmidt, what does the projection of $a_2$ onto $q_1$ represent?

6. Let $A$ be a $3 \times 2$ matrix. Which of the following is correct after QR decomposition?

What is the shape of matrix $R$ in QR decomposition for a $3 \times 2$ matrix $A$ ?

Select the correct answer

$2 \times 2$

$3 \times 3$

$3 \times 2$

$2 \times 3$

Which of the following correctly defines an orthonormal column vector?

Select the correct answer

Any non-zero vector

A unit vector perpendicular to others

A vector with length > 1

None of the above

If $u \cdot v = 0$ and $|u| = 1$ , what identity holds true?

Select the correct answer

$u = v$

$u = -v$

$u \perp v$

None

What is the first step in the Gram-Schmidt process for QR decomposition?

Select the correct answer

Compute $q_2$ using $a_2$ and $q_1$ .

Subtract projection of $a_2$ from $a_1$ .

Normalize $a_1$ to get $q_1$ .

Multiply $a_1$ by $R$ .

In QR decomposition using Gram-Schmidt, what does the projection of $a_2$ onto $q_1$ represent?

Select the correct answer

Orthogonal complement

Inner product

Component of $a_2$ along $q_1$

Residual vector

Let $A$ be a $3 \times 2$ matrix. Which of the following is correct after QR decomposition?

Select the correct answer

$Q$ is $3 \times 2$ , $R$ is $2 \times 2$

$Q$ is $2 \times 2$ , $R$ is $2 \times 3$

$Q$ is $3 \times 3$ , $R$ is $3 \times 2$

$Q$ is $2 \times 3$ , $R$ is $3 \times 3$

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 8

Spør AI

Spør om hva du vil, eller prøv ett av de foreslåtte spørsmålene for å starte chatten vår

Awesome!

Completion rate improved to 1.89

Introduction to Matrix Decomposition

Sveip for å vise menyen

Solving systems like $A \vec{x} = \vec{b}$ can be computationally intensive, especially for large systems.

Matrix decomposition simplifies this process by breaking matrix $A$ into simpler parts — which we can then solve in stages.

LU vs QR – When and Why

We decompose the matrix $A$ into other structured matrices.

LU Decomposition

Break $A$ into a Lower and Upper triangular matrix:

Built using Gaussian elimination
Works best for square matrices

A = LU

QR Decomposition

Break $A$ into an Orthogonal and Upper matrix:

Often used for non-square matrices
Ideal for least squares problems or when LU fails

A = QR

LU Decomposition – Setup

Start with a square matrix:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Our goal is to write this as:

A = LU

Where:

L = \begin{bmatrix} 1 & 0 \\ l_{21} & 1 \end{bmatrix},\ \ U = \begin{bmatrix} u_{11} & u_{12} \\ 0 & u_{22} \end{bmatrix}

This decomposition is possible if A is square and invertible.

Important Points:

Lower triangular matrices have all zero entries above the diagonal, simplifying forward substitution;
Upper triangular matrices have zeros below the diagonal, making backward substitution straightforward;
An orthogonal matrix has columns that are orthonormal vectors (vectors of length 1 that are perpendicular);
This property preserves vector length and angles, which is useful in solving least squares and improving numerical stability.

Gaussian Elimination

Apply Gaussian elimination to eliminate the entry below the top-left pivot:

R_2 \rarr R_2 - \frac{6}{4}R_1

This gives us:

R'_2 = [0, -1.5]

So the updated matrices become:

U = \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix}

And from our row operation, we know:

L = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix}

Important Points:

Gaussian elimination systematically eliminates entries below the pivot element in each column by subtracting scaled versions of the pivot row from the rows beneath;
This process transforms A into an upper triangular matrix U.
The multipliers used to eliminate these entries are stored in L, allowing us to represent A as the product LU.

Final Result – LU Decomposition Complete

We verify:

A = LU = \begin{bmatrix} 1 & 0 \\ 1.5 & 1 \end{bmatrix} \begin{bmatrix} 4 & 3 \\ 0 & -1.5 \end{bmatrix} = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

Now the system $A \vec{x} = \vec{b}$ can be solved in two steps:

Solve $L \vec{y} = \vec{b}$ by forward substitution;
Solve $U \vec{x} = \vec{y}$ by backward substitution.

QR Decomposition – Concept Overview

We want to express a matrix $A$ as a product of two matrices:

A = QR

Where:

$A$ is your input matrix (e.g. data, coefficients, etc.);
$Q$ is an orthogonal matrix (its columns are orthonormal vectors);
$R$ is an upper triangular matrix.

An example shape breakdown:

A = \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} = \begin{bmatrix} q_1 & q_2 \\ q_3 & q_4 \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

This decomposition is often used when:

Matrix A is not square;
Solving least squares problems;
LU decomposition isn't stable.

What Are Orthonormal Vectors?

Orthogonal vectors

Two vectors $u, v$ are orthogonal if their dot product is zero: $u \cdot v = 0$

Normalized vector

A vector $u$ is normalized when $|u| = 1$

Orthonormal set

A set of vectors $\{q_1, q_2, ..., q_k\}$ is orthonormal if each is unit length and they are mutually orthogonal:

q_i \cdot q_j = \begin{cases} 1,\ \text{if}\ \ i = j,\\ 0,\ \text{if}\ \ i \neq j. \end{cases}

Why it matters: orthonormal columns in $Q$ preserve geometry, simplify projections, and improve numerical stability.

QR Decomposition - Setup

Define the Matrix A

Let's start with this example:

A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}

We will use the Gram-Schmidt process to find matrices $Q$ and $R$ such that $A=QR$ . The Gram-Schmidt process creates an orthonormal set of vectors from the columns of $A$ .

So, here the goal is to:

Make the columns of $Q$ orthonormal;
Create the matrix $R$ which will encode the projections.

Compute First Basis Vector

We extract the first column of $A$ :

a_1 = \begin{bmatrix} 4 \\ 6 \end{bmatrix}

To normalize this, we compute the norm:

|a_1| = \sqrt{4^2 + 6^2} = \sqrt{16 + 36} = \sqrt{52}

Then:

q_1 = \frac{1}{\sqrt{52}} \begin{bmatrix} 4 \\ 6 \end{bmatrix} = \begin{bmatrix} \frac{4}{\sqrt{52}} \\ \frac{6}{\sqrt{52}} \end{bmatrix}

This is the first orthonormal vector for $Q$ .

How to Normalize a Vector

Given a vector:

v = \begin{bmatrix} v_1 \\ v_2 \\ \vdots \\ v_n \end{bmatrix}

We compute its norm:

|v| = \sqrt{v_1^2 + v_2^2 + ... + v^2_n}

Then normalize:

\hat{v} = \frac{1}{|v|}v

Example:

v = \begin{bmatrix} 3 \\ 4 \end{bmatrix},\ \ |v| = \sqrt{3^2 + 4^2} = 5

So, our normalized vector is:

\hat{v} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 0.6 \\ 0.8 \end{bmatrix}

Once we know how to normalize and orthogonalize vectors, we can apply the Gram-Schmidt process to form the $Q$ matrix, and use it to compute $R$ in the QR decomposition.

Compute q₂ Using Gram-Schmidt

To compute $q_2$ , we start with the second column of $A$ :

a_2 = \begin{bmatrix} 3 \\ 3 \end{bmatrix}

Next, you project $a_2$ onto $q_1$ :

r_{12} = q_1^Ta_2 = \frac{1}{\sqrt{52}}(4 \cdot 3 + 6 \cdot 3) = \frac{1}{\sqrt{52}} \cdot 30

Remove the projection from $a_2$ :

u_2 = a_2 - r_{12}q_1

Then normalize (as was shown above):

q_2 = \frac{u_2}{|u_2|}

Now both $q_1$ and $q_2$ form the orthonormal basis for $Q$ . You now assemble the final result:

Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix},\ \ R = \begin{bmatrix} r_{11} & r_{12} \\ 0 & r_{22} \end{bmatrix}

These satisfy:

A = QR

Quiz

1. What is the shape of matrix $R$ in QR decomposition for a $3 \times 2$ matrix $A$ ?

2. Which of the following correctly defines an orthonormal column vector?

3. If $u \cdot v = 0$ and $|u| = 1$ , what identity holds true?

4. What is the first step in the Gram-Schmidt process for QR decomposition?

5. In QR decomposition using Gram-Schmidt, what does the projection of $a_2$ onto $q_1$ represent?

6. Let $A$ be a $3 \times 2$ matrix. Which of the following is correct after QR decomposition?

What is the shape of matrix $R$ in QR decomposition for a $3 \times 2$ matrix $A$ ?

Select the correct answer

$2 \times 2$

$3 \times 3$

$3 \times 2$

$2 \times 3$

Which of the following correctly defines an orthonormal column vector?

Select the correct answer

Any non-zero vector

A unit vector perpendicular to others

A vector with length > 1

None of the above

If $u \cdot v = 0$ and $|u| = 1$ , what identity holds true?

Select the correct answer

$u = v$

$u = -v$

$u \perp v$

None

What is the first step in the Gram-Schmidt process for QR decomposition?

Select the correct answer

Compute $q_2$ using $a_2$ and $q_1$ .

Subtract projection of $a_2$ from $a_1$ .

Normalize $a_1$ to get $q_1$ .

Multiply $a_1$ by $R$ .

In QR decomposition using Gram-Schmidt, what does the projection of $a_2$ onto $q_1$ represent?

Select the correct answer

Orthogonal complement

Inner product

Component of $a_2$ along $q_1$

Residual vector

Let $A$ be a $3 \times 2$ matrix. Which of the following is correct after QR decomposition?

Select the correct answer

$Q$ is $3 \times 2$ , $R$ is $2 \times 2$

$Q$ is $2 \times 2$ , $R$ is $2 \times 3$

$Q$ is $3 \times 3$ , $R$ is $3 \times 2$

$Q$ is $2 \times 3$ , $R$ is $3 \times 3$

Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 4. Kapittel 8

Introduction to Matrix Decomposition

LU vs QR – When and Why

LU Decomposition

QR Decomposition

LU Decomposition – Setup

Gaussian Elimination

Final Result – LU Decomposition Complete

QR Decomposition – Concept Overview

What Are Orthonormal Vectors?

Orthogonal vectors

Normalized vector

Orthonormal set

QR Decomposition - Setup

Define the Matrix A

Compute First Basis Vector

How to Normalize a Vector

Compute q₂ Using Gram-Schmidt

Quiz

1. What is the shape of matrix RRR in QR decomposition for a 3×23 \times 23×2 matrix AAA?

2. Which of the following correctly defines an orthonormal column vector?

3. If u⋅v=0u \cdot v = 0u⋅v=0 and ∣u∣=1|u| = 1∣u∣=1, what identity holds true?

4. What is the first step in the Gram-Schmidt process for QR decomposition?

5. In QR decomposition using Gram-Schmidt, what does the projection of a2a_2a2​ onto q1q_1q1​ represent?

6. Let AAA be a 3×23 \times 23×2 matrix. Which of the following is correct after QR decomposition?

Awesome!

Introduction to Matrix Decomposition

LU vs QR – When and Why

LU Decomposition

QR Decomposition

LU Decomposition – Setup

Gaussian Elimination

Final Result – LU Decomposition Complete

QR Decomposition – Concept Overview

What Are Orthonormal Vectors?

Orthogonal vectors

Normalized vector

Orthonormal set

QR Decomposition - Setup

Define the Matrix A

Compute First Basis Vector

How to Normalize a Vector

Compute q₂ Using Gram-Schmidt

Quiz

1. What is the shape of matrix RRR in QR decomposition for a 3×23 \times 23×2 matrix AAA?

2. Which of the following correctly defines an orthonormal column vector?

3. If u⋅v=0u \cdot v = 0u⋅v=0 and ∣u∣=1|u| = 1∣u∣=1, what identity holds true?

4. What is the first step in the Gram-Schmidt process for QR decomposition?

5. In QR decomposition using Gram-Schmidt, what does the projection of a2a_2a2​ onto q1q_1q1​ represent?

6. Let AAA be a 3×23 \times 23×2 matrix. Which of the following is correct after QR decomposition?

1. What is the shape of matrix $R$ in QR decomposition for a $3 \times 2$ matrix $A$ ?

3. If $u \cdot v = 0$ and $|u| = 1$ , what identity holds true?

5. In QR decomposition using Gram-Schmidt, what does the projection of $a_2$ onto $q_1$ represent?

6. Let $A$ be a $3 \times 2$ matrix. Which of the following is correct after QR decomposition?

1. What is the shape of matrix $R$ in QR decomposition for a $3 \times 2$ matrix $A$ ?

3. If $u \cdot v = 0$ and $|u| = 1$ , what identity holds true?

5. In QR decomposition using Gram-Schmidt, what does the projection of $a_2$ onto $q_1$ represent?

6. Let $A$ be a $3 \times 2$ matrix. Which of the following is correct after QR decomposition?