Gauss-Jordan Elimination — Introduction

Given a system of $$$n$$$ linear algebraic equations (SLAE) with $$$m$$$ variables, we are asked to solve it (i.e., determine whether it has no solution, a unique solution, or infinitely many solutions). In the case of at least one solution, return any one of them.

In short, we are given the following system of equations:

where $$$a_{ij}$$$ ($$$1 \le i \le n,\ 1 \le j \le m$$$) and $$$b_i$$$ ($$$1 \le i \le n$$$) are known constants, and $$$x_i$$$ ($$$1 \le i \le m$$$) are the unknowns.

Alternatively, the system can be represented in matrix form as:

$$$Ax = b$$$

where $$$A$$$ is an $$$n \times m$$$ matrix of coefficients $$$a_{ij}$$$, and $$$b$$$ is an $$$n$$$-dimensional vector of constants.

This method can also be applied when the system has modular constraints:

The Algorithm

The Gauss-Jordan elimination method sequentially eliminates variables to reduce the system to a simpler form and then solves it. Specifically, we use the first equation to eliminate $$$x_1$$$ from the remaining $$$n-1$$$ equations, transforming them into a new system. This continues by eliminating $$$x_2$$$, and so on.

Two elementary row operations are used:

• Multiply an equation by a non-zero constant $$$r$$$.
• Add one equation to another (after possibly scaling it).

These operations preserve the solution set.

To perform Gauss elimination, for each variable $$$x_i$$$ ($$$1 \le i \le \min(n, m)$$$):

1. Find an unused equation with $$$a_{ei} \neq 0$$$:

• If found: divide all coefficients of that equation by $$$a_{ei}$$$, mark the equation as used, and eliminate $$$x_i$$$ from other equations.
• If not found: $$$x_i$$$ is a free variable.

1. For each remaining equation $$$r$$$, subtract $$$a_{ri}$$$ times the pivot row (equation $$$e$$$). This sets all other $$$a_{ri} = 0$$$ while maintaining $$$a_{ei} = 1$$$.

After elimination, solve from bottom to top:

• If $$$n \lt m$$$, then $$$x_i$$$ with $$$i \gt n$$$ are free variables.
• Assume all free variables are 0 (or arbitrary if finding general solution).
• For each dependent variable, solve using the row where it was eliminated.

Finally, check for consistency:

• If any row simplifies to $$$0 = c$$$ with $$$c \neq 0$$$, the system has no solution.
• Otherwise, if at least one free variable exists, there are infinitely many solutions; else, there is a unique solution.

Example

We use an $$$n \times (m+1)$$$ augmented matrix to represent the system. Each row is an equation; the first $$$m$$$ numbers are coefficients, the last is the constant term.

Given:

Matrix:

Step 1: Eliminate $$$x$$$

• Row2 -= 3 * Row1
• Row3 += 2 * Row1

Step 2: Eliminate $$$y$$$

• Row1 -= 5 * Row2
• Row3 += 2 * Row2

Step 3: Eliminate $$$z$$$

• Row1 -= 13 * Row3
• Row2 += 2 * Row3

Let $$$t = 0$$$:

Since $$$t$$$ is a free variable, there are infinitely many solutions. Another valid one is:

Conclusion

In this part, we’ve introduced the Gauss-Jordan elimination method and applied it to a sample problem.

In the next section, we’ll explore competitive programming problems that use this technique, share implementation tips, and provide clean code samples.