Review of Gauss Elimination

Daniel C. Simkins, Jr.

University of South Florida

September 22, 2020

1/15

Matrices and Linear Equations

There is a very close relationship between matrices and systems of linear equations. .

2x − 9 = −4y (1a)

7x − y = 8. (1b)

By convention, we respect the following rules:

1 write all pure numbers on the right-hand side (RHS), and all terms with avariable on the left-hand side (LHS)

4y + 2x = 9

7x − y = 8.

2 write the terms on the LHS in the same order according to the unknowns

2x + 4y = 9

7x − y = 8.

3 label the unknowns as elements of a vector, i.e. xi .

2×1 + 4×2 = 9 (2a)

7×1 − x2 = 8. (2b)

Then, the only thing that distinguishes one equation from another is the value of thecoefficient of each variable and the number on the right.

2/15

Matrices and Linear Equations

There is a very close relationship between matrices and systems of linear equations. .

2x − 9 = −4y (1a)

7x − y = 8. (1b)

By convention, we respect the following rules:

1 write all pure numbers on the right-hand side (RHS), and all terms with avariable on the left-hand side (LHS)

4y + 2x = 9

7x − y = 8.

2 write the terms on the LHS in the same order according to the unknowns

2x + 4y = 9

7x − y = 8.

3 label the unknowns as elements of a vector, i.e. xi .

2×1 + 4×2 = 9 (2a)

7×1 − x2 = 8. (2b)

Then, the only thing that distinguishes one equation from another is the value of thecoefficient of each variable and the number on the right.

2/15

Matrices and Linear Equations

There is a very close relationship between matrices and systems of linear equations. .

2x − 9 = −4y (1a)

7x − y = 8. (1b)

By convention, we respect the following rules:

1 write all pure numbers on the right-hand side (RHS), and all terms with avariable on the left-hand side (LHS)

4y + 2x = 9

7x − y = 8.

2 write the terms on the LHS in the same order according to the unknowns

2x + 4y = 9

7x − y = 8.

3 label the unknowns as elements of a vector, i.e. xi .

2×1 + 4×2 = 9 (2a)

7×1 − x2 = 8. (2b)

Then, the only thing that distinguishes one equation from another is the value of thecoefficient of each variable and the number on the right.

2/15

Matrices and Linear Equations

There is a very close relationship between matrices and systems of linear equations. .

2x − 9 = −4y (1a)

7x − y = 8. (1b)

By convention, we respect the following rules:

4y + 2x = 9

7x − y = 8.

2 write the terms on the LHS in the same order according to the unknowns

2x + 4y = 9

7x − y = 8.

3 label the unknowns as elements of a vector, i.e. xi .

2×1 + 4×2 = 9 (2a)

7×1 − x2 = 8. (2b)

2/15

Matrix Form

Following this convention allows us to write this as a matrix equation[2 47 −1

] [x1

x2

]=

[98

]or, in matrix notation,

Ax = b

where,

A =

[2 47 −1

]; x =

[x1

x2

]; and b =

[98

].

Thus, sets of simultaneous linear equations can be conveniently written inmatrix-vector form.

3/15

Solving

If we wanted to solve the set of equations Eq. 2, we could simply solve for, say, x2 inEq. 2b

x2 = 7×1 − 8

and substitute into Eq. 2a:2×1 + 4(7×1 − 8) = 9

to find30x1 = 41

x1 =41

30

We can find x2 by back substituting x1 into one of the equations. To automate thesolution of linear systems, we would like to find a systematic procedure to accomplishthe same result.

4/15

Let’s consider a very special set of equations:

2×1 + 3×2 − 4×3 + 9×4 = 12

x2 + 2×3 − 7×4 = 9

4×3 − x4 = 2

3×4 = 1

or, in matrix form, 2 3 −4 90 1 2 −70 0 4 −10 0 0 3

x1

x2

x3

x4

=

12921

(3)

Here the coefficient matrix is in upper-triangular form. Notice that if we start with thelast equation, we can immediately solve for x4. Once we have x4, we can immediatelyuse the second to last equation to get x3, etc. until the entire system is solved. Thisprocess is called back-substitution. We see that upper-triangular systems are especiallyeasy to solve.

Goal: Our goal is to develop a systematic way to take a general coefficient matrix andreduce it to upper-triangular form.

5/15

A systematic procedure for reducing a general matrix to upper triangular form isknown as Gaussian elimination. There are several variations, we will present thesimplest. The basis for Gauss elimination is the repetitive use of basic operations,based on the following observations:

re-writing the order of the equations does not change their solution

2×1 + 4×2 = 9

7×1 − x2 = 8.

is the same as

7×1 − x2 = 8

2×1 + 4×2 = 9.

multiplying an entire equation by a scalar does not change the solution

2 (2×1 + 4×2) = 2 (9)

7×1 − x2 = 8.

6/15

we can replace any equation by the sum of itself with another equation does notchange the solution. For example replace the second equation by the sum of thefirst and second:

2×1 + 4×2 = 9

9×1 − 3×2 = 17.

7/15

Row operations

1 Swap two rows. This operation merely interchanges two rows in the matrix and isanalagous to re-ordering the linear equations.Example: 1 2 0

3 4 1−1 −2 −3

−→ 3 4 1

1 2 0−1 −2 −3

2 Row scaling. Here, a single row is multiplied by a scalar, rather than the entire

matrix. Example, scale row 3 by 12

: 1 2 03 4 1−1 −2 −3

−→ 1 2 0

3 4 1− 1

2−1 − 3

2

3 Linear combination of two rows. Here we take the scalar multiple of one row and

add it to another row, replacing the last row. In equations,

a′jk = α aik + ajk ; k = 1, …, n

for rows i and j .Example: for α = 2, take the linear combination of rows 1 and 3 in the followingmatrix: 1 2 0

3 4 1−1 −2 −3

−→ 1 2 0

3 4 12 · 1− 1 2 · 2− 2 2 · 0− 3

=

1 2 03 4 11 2 −3

8/15

Gauss Procedure

The procedure to reduce a general matrix to upper-triangular form is simple:

1 Start with first row and column

2 swap rows so that the row containing the largest element (in absolute value), inthe column at or below the diagonal is on the diagonal for the first row

3 Use linear combinations of the first row using α = − ai1a11

for each row below the

diagonal. This will make all the entries in the first column below the diagonalzero.

4 Repeat but move to the second row, second column, etc until the entire matrix isin upper-triangular form.

9/15

Example

First move largest element in column 1 to be the first row 1 2 03 4 1−1 −2 −3

−→ 3 4 1

1 2 0−1 −2 −3

Use linear combination of row 1 and 2 with α = − 1

3to put a zero in the second

row, first column: 3 4 11 2 0−1 −2 −3

−→ 3 4 1− 1

3· 3 + 1 − 1

3· 4 + 2 − 1

3· 1 + 0

−1 −2 −3

=

3 4 10 2

3− 1

3−1 −2 −3

Use linear combination of row 1 and row 3 with α = 1

3 3 4 10 2

3− 1

3−1 −2 −3

−→ 3 4 1

0 23

− 13

13· 3− 1 1

3· 4− 2 1

3· 1− 3

=

3 4 10 2

3− 1

30 − 2

3− 8

3

Move to second row, second column. Since |a22| = |a32|, there is no need to swaprows.

Use linear combination of row 2 and row 3 to eliminate a32 using α = 13 4 10 2

3− 1

30 − 2

3− 8

3

−→3 4 1

0 23− 1

30 0 −3

which is now reduced to upper-triangular form.

10/15

So, we see that a sequence of row operations changes the matrix A into the matrix U:

Arow operations−−−−−−−−−−−→ U

Important!

It is crucial to note that what ever we do to the LHS, must also be done to the RHS,i.e. swapping rows and linear combinations.

11/15

Solution Example

Using the Gauss elimination procedure given in class, reduce the following matrix toupper-triangular form and modify the right hand side appropriately.

6 7 −5 20 9 2 60 −8 1 1−7 −4 −10 3

x1

x2

x3

x4

=

1348−9−33

(4)

12/15

LU Decomposition

Factor matrixColumn 1Pivot row 1 and row 4

−7 −4 −10 30 9 2 60 −8 1 16 7 −5 2

x1

x2

x3

x4

=

−3348−913

Eliminate row 4 with row 1 using alpha= 0.857143

−7 −4 −10 30 9 2 60 −8 1 10 3.57143 −13.5714 4.57143

x1

x2

x3

x4

=

−3348−9

−15.2857

13/15

Column 2

Eliminate row 3 with row 2 using alpha= 0.888889−7 −4 −10 30 9 2 60 0 2.77778 6.333330 3.57143 −13.5714 4.57143

x1

x2

x3

x4

=

−3348

33.6667−15.2857

Eliminate row 4 with row 2 using alpha= -0.396825

−7 −4 −10 30 9 2 60 0 2.77778 6.333330 0 −14.3651 2.19048

x1

x2

x3

x4

=

−3348

33.6667−34.3333

Column 3Pivot row 3 and row 4

−7 −4 −10 30 9 2 60 0 −14.3651 2.190480 0 2.77778 6.33333

x1

x2

x3

x4

=

−3348

−34.333333.6667

Eliminate row 4 with row 3 using alpha= 0.19337

−7 −4 −10 30 9 2 60 0 −14.3651 2.190480 0 0 6.75691

x1

x2

x3

x4

=

−3348

−34.333327.0276

14/15

Back solve

Solve for x4: x4 = 27.0276−(0)6.75691

= 4

Solve for x3: x3 = −34.3333−4(2.19048)−14.3651

= 3

Solve for x2: x2 = 48−(2∗3+4∗6)9

= 2

Solve for x1: x1 = −33−(−4∗2−10∗3+3∗4)−7

= 1

Check solution

R = Ax− b =

0000

15/15