Gauss-Jordan Elimination

Definition

Gauss-Jordan elimination is an algorithm used in linear algebra to solve systems of linear equations, find the inverse of an invertible matrix, or find the rank of a matrix. It is an extension of Gaussian elimination where the matrix is transformed into Reduced Row Echelon Form (RREF) using a sequence of elementary row operations.

Main Content

1. Augmented Matrix Representation

• A system of linear equations is represented as an augmented matrix $[A|B]$, where $A$ is the coefficient matrix and $B$ is the column vector of constants.
• The goal is to reach a state where the matrix $A$ becomes an identity matrix $I$, effectively isolating the variables on one side.

2. Elementary Row Operations

• Row Swapping: Interchanging two rows ($R_i \leftrightarrow R_j$).
• Scalar Multiplication: Multiplying all entries of a row by a non-zero constant ($k R_i \rightarrow R_i$).
• Row Addition/Subtraction: Adding or subtracting a multiple of one row to another row ($R_i + kR_j \rightarrow R_i$).

3. Reduced Row Echelon Form (RREF)

• Every leading entry (the first non-zero number from the left) in a row is 1.
• The leading 1 of any row is to the right of the leading 1 of the row above it.
• All entries in a column containing a leading 1 are zero, except for the leading 1 itself.

[ 1  0  0 | a ]
[ 0  1  0 | b ]
[ 0  0  1 | c ]

(Above: A 3x3 system in RREF, where a, b, and c represent the solution for x, y, and z.)

Working / Process

1. Forward Elimination

• Identify the first pivot element (top-left). If it is zero, swap the row with one below it.
• Use row operations to create zeros in all entries below the pivot.
• Move to the next diagonal element and repeat the process until the matrix is in Row Echelon Form (upper triangular).

2. Backward Elimination

• Start from the bottom-right pivot and work upwards.
• Use row operations to create zeros in all entries above the pivot.
• This creates an upper triangular matrix where only the diagonal elements and the augmented column remain non-zero.

3. Normalization

• Once the matrix is in the form of a diagonal matrix, divide each row by its leading entry to transform the diagonal elements into 1s.
• The augmented column now contains the final values of the variables.

Advantages / Applications

• Direct Method: Unlike iterative methods, it provides an exact solution in a finite number of steps.
• Inverse Calculation: It is the standard numerical method for calculating the inverse of a square matrix ($[A|I] \rightarrow [I|A^{-1}]$).
• Computational Efficiency: It is highly systematic and easily programmable for computer implementation in software like MATLAB or Python (NumPy).

Summary

Gauss-Jordan elimination is a foundational numerical method that systematically transforms an augmented matrix into Reduced Row Echelon Form to solve linear systems or invert matrices. By applying elementary row operations—swapping, scaling, and addition—it isolates variables to provide direct solutions. Important terms include the augmented matrix, pivot element, identity matrix, and row operations.