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:

1. Solve $L \vec{y} = \vec{b}$ by forward substitution;
2. 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

---

---

---

---

---