Ch3.2.1: Gaussian Elimination

Systems of Linear Equations

A system of linear equations has the following form, and can be expressed in matrix-vector form \( A\mathbf{x} = \mathbf{b} \):

\[ \matrix{ x_1 & + & 2x_2 & = & 5 \cr 3x_1 & - & 4 x_2 & = & 6 } \, \, \Leftrightarrow \begin{bmatrix} 1 & 2 \\ 3 & -4 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 5 \\ 6 \end{bmatrix} \]

Alternatively, we can express the system as an augmented matrix; this is common when solving by hand.

\[ \matrix{ x_1 & + & 2x_2 & = & 5 \cr 3x_1 & - & 4 x_2 & = & 6 } \, \, \Leftrightarrow \begin{bmatrix} 1 & 2 & 5 \\ 3 & -4 & 6 \end{bmatrix} \]

Overview of Solution Method

We seek to transform our given system of equations into a new system that has same solution set as the original system.
In figure below, the bottom right matrix is in row echelon form (upper triangular form).

Two Jokes



My new thesaurus is terrible.

Not only that, but it's also terrible.



I'm reading a book about anti-gravity.

It's impossible to put down!

Overview of Solution Method

Use elementary row operations to transform system of equations into a easier system with same solution.

Elementary Row Operations

Row swap
Row scale
Replace a row with the sum of that row and a scalar multiple of another row (rotate or “pivot” the line)

Equivalent Systems

Add to get third line (pivot operation).
To save space, third line often replaces one of the other lines.
The sum of two lines (green) preserves solution.
This green line is a pivoted version of the second line.

Pivot Operation

Pivoting applies to \( 3 \times 3 \) systems (planes) and higher dimension systems (hyperplanes).

Example 1

Example 1, continued

Example 2

Example 2, continued

Example 3

Example 4

Example 5

Example 6

Use elementary row operations to transform the matrix into upper triangular form.
Be sure to label your row operations as in previous examples.

Example 6, continued

Example 6: Using R Program refmatrix

(Ab <- matrix(c(1,-2,3,-3,7,-5,2,-8,-9,6,-19,-9),3))

     [,1] [,2] [,3] [,4]
[1,]    1   -3    2    6
[2,]   -2    7   -8  -19
[3,]    3   -5   -9   -9

refmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    1   -3    2    6
[2,]    0    1   -4   -7
[3,]    0    0    1    1

Example 6: Using R Program rrefmatrix

refmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    1   -3    2    6
[2,]    0    1   -4   -7
[3,]    0    0    1    1

rrefmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    1    0    0   -5
[2,]    0    1    0   -3
[3,]    0    0    1    1

Example 7

Use elementary row operations to transform the matrix into upper triangular form.
Be sure to label your row operations as in previous examples.

Example 7, continued

Example 7: Using R Program refmatrix

(Ab <- matrix(c(1,2,4,2,6,3,-4,-6,-15,5,8,13),3))

     [,1] [,2] [,3] [,4]
[1,]    1    2   -4    5
[2,]    2    6   -6    8
[3,]    4    3  -15   13

refmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    1    2   -4    5
[2,]    0    2    2   -2
[3,]    0    0    6  -12

Example 7: Using R Program rrefmatrix

refmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    1    2   -4    5
[2,]    0    2    2   -2
[3,]    0    0    6  -12

rrefmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    1    0    0   -5
[2,]    0    1    0    1
[3,]    0    0    1   -2

Gaussian Elimination for n x n Systems

\[ \scriptsize{ \begin{align} & &\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & a_{1,n+1} \\ a_{21} & a_{22} & \cdots & a_{2n} & | & a_{2,n+1} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} & | & a_{n,n+1} \end{bmatrix} & \begin{matrix} R_2 = R_2 - \frac{a_{21}}{a_{11}}R_1 \\ \vdots \\ R_n = R_n - \frac{a_{n1}}{a_{11}}R_1 \end{matrix} \\ \\ & \rightarrow & \begin{bmatrix} a_{11}^{(2)} & a_{12}^{(2)} & \cdots & a_{1n}^{(2)} & | & a_{1,n+1}^{(2)} \\ 0 & a_{22}^{(2)} & \cdots & a_{2n}^{(2)} & | & a_{2,n+1}^{(2)} \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ 0 & a_{n2}^{(2)} & \cdots & a_{nn}^{(2)} & | & a_{n,n+1}^{(2)} \\ \end{bmatrix} & \begin{array} {llll} a_{1j}^{(2)} = a_{1j}^{(1)}, \, \, j = 1, \ldots, n+1 \\ a_{k1}^{(2)} = 0, \, \, \, \, \, \, k = 1, \ldots, n \\ a_{kj}^{(2)} = a_{kj}^{(1)} - m_{k1} \cdot a_{1j}^{(1)} \\ m_{k1} = \frac{a_{k1}^{(1)}}{a_{11}^{(1)}}, \, \, a_{11}^{(1)} \neq 0 \end{array} \end{align} } \]

Gaussian Elimination: k-th Step

\[ \scriptsize{ \begin{bmatrix} a_{11}^{(k)} & a_{12}^{(k)} & \cdots & a_{1,k-1}^{(k)} & a_{1,k}^{(k)} & \cdots & a_{1n}^{(k)} & | & a_{1,n+1}^{(k)} \\ 0 & a_{22}^{(k)} & \cdots & a_{2,k-1}^{(k)} & a_{2,k}^{(k)} & \cdots & a_{2,n}^{(k)} & | & a_{2,n+1}^{(k)} \\ 0 & 0 & \ddots & \vdots & \vdots & \cdots & \vdots & | & \vdots \\ 0 & 0 & \cdots & a_{k-1,k-1}^{(k)} & a_{k-1,k}^{(k)} & \cdots & a_{k-1,n}^{(k)} & | & a_{k-1,n+1}^{(k)} \\ 0 & 0 & \cdots & 0 & a_{k,k}^{(k)} & \cdots & a_{k,n}^{(k)} & | & a_{k,n+1}^{(k)} \\ 0 & 0 & \cdots & 0 & a_{k+1,k}^{(k)} & \cdots & a_{k+1,n}^{(k)} & | & a_{k+1,n+1}^{(k)} \\ 0 & 0 & \cdots & \vdots & \vdots & \cdots & \vdots & | & \vdots \\ 0 & 0 & \cdots & 0 & a_{n,k}^{(k)} & \cdots & a_{n.n}^{(k)} & | & a_{n,n+1}^{(k)} \\ \end{bmatrix}} \]

Row Replacement Formulas: k-th Step

\[ \scriptsize{ \begin{array} {llll} a_{ij}^{(k)} & = & a_{ij}^{(k-1)}, & 1 \leq i \leq k-1, & 1 \leq j \leq n+1 \\ a_{ij}^{(k)} & = & 0, & k \leq i \leq n, & 1 \leq j \leq k-1 \\ a_{ij}^{(k)} & = & a_{ij}^{(k-1)} - m_{i,k-1} \cdot a_{k-1,j}^{(k-1)}, & k \leq i \leq n, & k \leq j \leq n+1 \\ m_{i,k-1} & = & \frac{a_{i,k-1}^{(k-1)}}{a_{k-1,k-1}^{(k-1)}}, & {a_{k-1,k-1}^{(k-1)}} \neq 0 & k \leq i \leq n \end{array} } \]

Gaussian Elimination: n-th Step

\[ \scriptsize{ \begin{bmatrix} a_{11}^{(n)} & a_{12}^{(n)} & \cdots & a_{1,k}^{(n)} & \cdots & a_{1n}^{(n)} & | & a_{1,n+1}^{(n)} \\ 0 & a_{22}^{(n)} & \cdots & a_{2,k}^{(n)} & \cdots & a_{2,n}^{(n)} & | & a_{2,n+1}^{(n)} \\ 0 & 0 & \ddots & \vdots & \ddots & \vdots & | & \vdots \\ 0 & 0 & \cdots & a_{k,k}^{(n)} & \cdots & a_{k,n}^{(n)} & | & a_{k,n+1}^{(n)} \\ \vdots & \vdots & \cdots & \vdots & \ddots & \vdots & | & \vdots \\ 0 & 0 & \cdots & 0 & \cdots & a_{n,n}^{(n)} & | & a_{n,n+1}^{(n)} \\ \end{bmatrix} } \]

System of Equations: n-th Step

\[ \scriptsize{ \begin{array}{rcrcccccccc} a_{11}^{(n)}x_1 & + & a_{12}^{(n)}x_2 & + & \cdots & + & a_{1k}^{(n)}x_k & + & \cdots & + & a_{1n}^{(n)}x_n & = & a_{1,n+1}^{(n)} \\ 0x_1 & + & a_{22}^{(n)}x_{2} & + & \cdots & + & a_{2k}^{(n)}x_k & + & \cdots & + & a_{2,n}^{(n)}x_n & = & a_{2,n+1}^{(n)} \\ 0x_1 & + & 0x_{2} & + & \cdots & \vdots &\vdots &\vdots & \cdots & \vdots & \vdots & = & \vdots \\ 0x_1 & + & 0x_{2} & + & \cdots & + & a_{kk}^{(n)}x_k & + & \cdots & + & a_{k,n}^{(n)}x_n & = & a_{k,n+1}^{(n)} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \cdots &\cdots &\ddots & \vdots & \vdots & = & \vdots \\ 0x_1 & + & 0x_{2} & + & \cdots & + & 0x_k & + & \cdots & + & a_{n,n}^{(n)}x_n & = & a_{n,n+1}^{(n)} \\ \end{array} } \]

Back Substitution

The method fails if one of the pivots \( \small{ a_{11}^{(1)}, a_{22}^{(2)},\ldots, a_{nn}^{(n)}} \) is zero.
In this case, use a row switch during row operations stage.
Otherwise, the solution is found using back substitution:

\[ \scriptsize{ \begin{aligned} x_n & = \frac{a_{n,n+1}^{(n)}}{a_{n,n}^{(n)}} \\ x_i & = \frac{ a_{i,n+1}^{(n)}-a_{i,n}^{(n)}x_n-a_{i,n-1}^{(n)}x_{n-1} -\ldots-a_{i,i+1}^{(n)}x_{i+1} } {a_{i,i}^{(n)}} \\ & = \frac{ a_{i,n+1}^{(n)}- \sum_{j \, = \, i+1}^n a_{i,j}^{(n)}x_j }{a_{i,i}^{(n)}}, \,\, i = n-1, n-2, \ldots, 1 \end{aligned} } \]

Example 8

Use elementary row operations to transform the matrix into upper triangular form. Do not use row switches.

Example 8, continued

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Example 8, continued

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Example 8, continued

Use back substitution to solve for \( x_3, x_2, x_1 \) (in this order).

Example 8, continued

Example 8: Using R Programs

refmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    2    3    1    2
[2,]    0   -1    4    0
[3,]    0    0    2    2

rrefmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    1    0    0 -5.5
[2,]    0    1    0  4.0
[3,]    0    0    1  1.0

Example 8, continued

Use R to check that \( A = LU \).

(L <- matrix(c(1,-3,2,0,1,1,0,0,1),3))

     [,1] [,2] [,3]
[1,]    1    0    0
[2,]   -3    1    0
[3,]    2    1    1

(U <- matrix(c(2,0,0,3,-1,0,1,4,2),3))

     [,1] [,2] [,3]
[1,]    2    3    1
[2,]    0   -1    4
[3,]    0    0    2

Example 8, continued

Use R to check that \( A = LU \).

(A <- matrix(c(2,-6,4,3,-10,5,1,1,8),3))

     [,1] [,2] [,3]
[1,]    2    3    1
[2,]   -6  -10    1
[3,]    4    5    8

L %*% U

     [,1] [,2] [,3]
[1,]    2    3    1
[2,]   -6  -10    1
[3,]    4    5    8

Example 8, continued

Use R to check that \( A = LU \).

(L <- matrix(c(1,-3,2,0,1,1,0,0,1),3))

     [,1] [,2] [,3]
[1,]    1    0    0
[2,]   -3    1    0
[3,]    2    1    1

(U <- matrix(c(2,0,0,3,-1,0,1,4,2),3))

     [,1] [,2] [,3]
[1,]    2    3    1
[2,]    0   -1    4
[3,]    0    0    2

Example 8, continued

Use R to check that \( A = LU \).

(A <- matrix(c(2,-6,4,3,-10,5,1,1,8),3))

     [,1] [,2] [,3]
[1,]    2    3    1
[2,]   -6  -10    1
[3,]    4    5    8

L %*% U

     [,1] [,2] [,3]
[1,]    2    3    1
[2,]   -6  -10    1
[3,]    4    5    8

Example 9

Use elementary row operations to transform the matrix into upper triangular form. Do not use row switches.

Example 9, continued

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Example 9, continued

Find the matrices \( L \) and \( U \) for which \( A = LU \).

Example 9, continued

Use back substitution to solve for \( x_3, x_2, x_1 \) (in this order).

Example 9, continued

Example 9: Using R Programs

refmatrix(Ab)

     [,1] [,2] [,3] [,4]
[1,]    3    2    1    0
[2,]    0    1    2    1
[3,]    0    0    3    6

rrefmatrix(Ab)

     [,1] [,2] [,3]      [,4]
[1,]    1    0    0  1.333333
[2,]    0    1    0 -3.000000
[3,]    0    0    1  2.000000

Example 9, continued

Use R to check that \( A = LU \).

(L <- matrix(c(1,1,-4,0,1,-2,0,0,1),3))

     [,1] [,2] [,3]
[1,]    1    0    0
[2,]    1    1    0
[3,]   -4   -2    1

(U <- matrix(c(3,0,0,2,1,0,1,2,3),3))

     [,1] [,2] [,3]
[1,]    3    2    1
[2,]    0    1    2
[3,]    0    0    3

Example 9, continued

Use R to check that \( A = LU \).

(A <- matrix(c(3,3,-12,2,3,-10,1,3,-5),3))

     [,1] [,2] [,3]
[1,]    3    2    1
[2,]    3    3    3
[3,]  -12  -10   -5

L %*% U

     [,1] [,2] [,3]
[1,]    3    2    1
[2,]    3    3    3
[3,]  -12  -10   -5