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$

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 8

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Suggested prompts:

Can you give me some example quiz questions based on the material?

What types of questions would be good for testing understanding of LU and QR decomposition?

Can you help me fill in the quiz with appropriate questions and answers?

Awesome!

Completion rate improved to 1.89

Introduction to Matrix Decomposition

Glissez pour afficher le menu

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$

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 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?