Linear Algebra – Gaussian Elimination

Book: Introduction to Linear Algebra, Johnson et al. Third Edition

Gaussian Elimination is a method in linear algebra used to solve systems of linear equations.
It systematically transforms a system of equations into a simpler form so the solutions become easy to find.

It works by manipulating the augmented matrix of the system using basic row operations.

Linear Equations:

General Linear Systems:
A general linear system is simply a collection of one or more linear equations involving the same variables.

• There are m equations
• There are n unknown variables $x_1, x_2, …, x_n$
• The numbers $a_{ij}$​ are called coefficients
• The numbers $b_i$ are called constants

This form represents ANY possible system of linear equations.

Matrix Representation: Instead of writing many equations, linear algebra rewrites a general linear system compactly using matrices:

Ax = b

Where b is the constant vector, A is the coefficient matrix and x is the vector of variables.

Elementary Operations: In linear algebra, Elementary Row Operations are simple moves you can perform on the rows of a matrix. They are the foundation of Gaussian Elimination, which is used to solve systems of linear equations, find matrix inverses, and calculate determinants.

The key rule is: These operations change the numbers in the matrix, but they do not change the solution to the system of equations.

There are exactly three types of elementary operations:

• Row Swapping $R_i ​\leftrightarrow R_j​$
• Scaling a Row $R_i​→kR_i​(k \neq 0)$
• Row Replacement $R_i + k R_j \rightarrow R_i$

There are exactly three types of elementary operations:

1. Row Interchange (Swapping)

You can swap the positions of any two rows.

• Why use it? To move a non-zero number into a “pivot” position (usually the top-left) to make division easier later.
• Notation: $R_i ​\leftrightarrow R_j​$

Example: Swap Row 1 and Row 2.

​2. Scalar Multiplication (Scaling)

You can multiply (or divide) any row by a non-zero constant number (scalar).

• Why use it? To turn a leading number into a 1 (making it a “leading one”).
• Notation: $R_i​→kR_i​(k \neq 0)$

Example: Multiply Row 1 by 3.​

3. Row Addition (Pivoting)

You can add a multiple of one row to another row. (This is the most commonly used operation).

• Why use it? To create zeros below a pivot (canceling out variables) to reach Row Echelon Form.
• Notation: $R_i + k R_j \rightarrow R_i$​ (Replace Row i with [Row i + (k times Row j)])

Example: We want to turn the 4 in the second row into a 0. We can use the −1 in the first row to do it. We add 4 times Row 1 to Row 2.

GAUSSIAN ELIMINATION (Variable Elimination Technique):

Gaussian Elimination is a systematic algorithm used to solve systems of linear equations. It works by applying the elementary row operations (swap, scale, add) to simplify a matrix until the solution becomes obvious.

The goal is to turn a messy system of equations into a clean triangular shape known as Row Echelon Form.

The Two Main Phases of Guassian Elimination:

1. Forward Elimination:
   • Goal: Create zeros below the main diagonal (bottom-left corner).
   • Result: You get a “staircase” pattern of numbers. The last row usually tells you the value of the last variable immediately (e.g., z=3).
2. Back Substitution:
   • Goal: Work upwards from the bottom.
   • Result: Since you know z, you plug it into the row above to find y, then plug both into the top row to find x.

Example: Solving a System

Let’s solve this system for $x,y,z$:

Step 1: Write the Augmented Matrix

Step 2: Elimination (Targeting Column 1) We want zeros below the first 1.

• Kill the 2: R2​−2R1​→R2​
• Kill the -1: R3​+R1​→R3​

Step 3: Elimination (Targeting Column 2) We need a zero below the 2 (in the middle).

• Kill the 6: R3​−3R2​→R3​

New Matrix (Row Echelon Form):

Step 4: Back Substitution Now we convert the rows back into equations and solve from bottom to top.