Published on

Notes on Strang Lecture - 2

Lecture link

Gaussian elimination

This lecture covers Gaussian elimination for solving systems of linear equations - transforms a matrix into an upper triangular form through row operations.

The elimination process

Consider solving the system Ax⃗=b⃗A\vec{x} = \vec{b} where

x+2y+z=23x+8y+z=124y+z=2\begin{align*} x + 2y + z &= 2 \\ 3x + 8y + z &= 12 \\ 4y + z &= 2 \end{align*}

In matrix form as:

[121381041][xyz]=[2122]\begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix}

Step 1: First pivot elimination

The first pivot (the coefficient in position (1,1)(1,1)) is not 00. We eliminate below the first pivot:

[12102−2041][xyz]=[262]\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} 2 \\ 6 \\ 2 \end{bmatrix}

Here we performed the operation: Row 2 → Row 2 - 3×Row 1

Step 2: Second pivot elimination

Continue eliminating below the second pivot:

[12102−2005][xyz]=[26−10]\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix} \begin{bmatrix} x \\ y \\ z \end{bmatrix} = \begin{bmatrix} 2 \\ 6 \\ -10 \end{bmatrix}

We performed: Row 3 → Row 3 - 2×Row 2

This upper triangular matrix is denoted as UU.

When elimination fails

Elimination can fail when:

  1. There is a 0 at a pivot position, and
  2. We cannot perform row exchanges to fix it
A zero at pivot that cannot be fixed by row exchanges indicates that the matrix is not invertible.

Elimination matrices

The elimination process can be represented using matrices. These matrices encode the row operations performed during elimination.

Note on matrix multiplication

For a matrix AA

A=[−a⃗1−−a⃗2−−a⃗3−]A = \begin{bmatrix} - \vec{a}_1 - \\ - \vec{a}_2 - \\ - \vec{a}_3 - \end{bmatrix}

with rows a⃗1,a⃗2\vec{a}_1, \vec{a}_2, and a⃗3\vec{a}_3, and a row vector x⃗=[x1,x2,x3]T\vec{x} = [x_1, x_2, x_3]^T. The operation:

x⃗A=x1a⃗1+x2a⃗2+x3a⃗3\vec{x}A = x_1\vec{a}_1 + x_2\vec{a}_2 + x_3\vec{a}_3

is a linear combination of the rows of AA.

Example elimination matrix

For our previous example, the elimination matrix that transforms Row 2 by subtracting 3 times Row 1 is:

E21=[100−310001]E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}

Similarly, the elimination matrix for the second step (eliminating below the second pivot) is:

E32=[1000100−21]E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix}

The complete elimination process

The complete elimination (LU decomposition) can be written as a sequence of matrix multiplications:

E32E21A=UE_{32}E_{21}A = U

Where UU is the upper triangular matrix obtained after elimination.