Learn Introduction to Matrix Decomposition | Linear Algebra Foundations

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

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

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.

LU Decomposition Result

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

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.

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

Everything was clear?

Thanks for your feedback!

Section 4. Chapter 8

Ask AI

Ask anything or try one of the suggested questions to begin our chat

Suggested prompts:

Can you explain the main differences between LU and QR decomposition?

How do I know when to use LU decomposition versus QR decomposition?

Can you walk me through the steps of the Gram-Schmidt process in more detail?

Awesome!

Completion rate improved to 1.96

Swipe to show 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

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

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.

LU Decomposition Result

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

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.

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

Everything was clear?

Thanks for your feedback!

Section 4. Chapter 8