Mathwords logoReference LibraryMathwords

Gaussian Elimination

Gaussian Elimination

A method of solving a linear system of equations. This is done by transforming the system's augmented matrix into row-echelon form by means of row operations. Then the system is solved by back-substitution.

 

Example of Gaussian Elimination: solving x+y+z=3, 2x+3y+7z=0, x+3y−2z=17 via row operations to get x=1, y=4, z=−2.

 

 

See also

Gauss-Jordan elimination

Key Formula

[a11a12a13b1a21a22a23b2a31a32a33b3]→row ops[a11′a12′a13′b1′0a22′a23′b2′00a33′b3′]\left[\begin{array}{ccc|c} a_{11} & a_{12} & a_{13} & b_1 \\ a_{21} & a_{22} & a_{23} & b_2 \\ a_{31} & a_{32} & a_{33} & b_3 \end{array}\right] \xrightarrow{\text{row ops}} \left[\begin{array}{ccc|c} a_{11}' & a_{12}' & a_{13}' & b_1' \\ 0 & a_{22}' & a_{23}' & b_2' \\ 0 & 0 & a_{33}' & b_3' \end{array}\right]
Where:
  • aija_{ij} = Coefficients of the variables in the original system
  • bib_i = Constants on the right-hand side of each equation
  • aij′a_{ij}' = Transformed coefficients after row operations
  • bi′b_i' = Transformed constants after row operations

Worked Example

Problem: Solve the system of equations: x+2y+z=9x + 2y + z = 9 2x+5y+2z=212x + 5y + 2z = 21 3x+7y+4z=303x + 7y + 4z = 30
Step 1: Write the augmented matrix for the system.
[12192522137430]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 2 & 5 & 2 & 21 \\ 3 & 7 & 4 & 30 \end{array}\right]
Step 2: Eliminate the first column below the pivot. Replace R2R_2 with R2−2R1R_2 - 2R_1, and replace R3R_3 with R3−3R1R_3 - 3R_1.
[121901030113]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 0 & 1 & 0 & 3 \\ 0 & 1 & 1 & 3 \end{array}\right]
Step 3: Eliminate the second column below the second pivot. Replace R3R_3 with R3−R2R_3 - R_2.
[121901030010]\left[\begin{array}{ccc|c} 1 & 2 & 1 & 9 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 0 \end{array}\right]
Step 4: The matrix is now in row-echelon form. Back-substitute starting from the last row. Row 3 gives z=0z = 0. Row 2 gives y=3y = 3. Row 1 gives x+2(3)+0=9x + 2(3) + 0 = 9, so x=3x = 3.
z=0,y=3,x=9−6−0=3z = 0,\quad y = 3,\quad x = 9 - 6 - 0 = 3
Answer: x=3x = 3, y=3y = 3, z=0z = 0.

Another Example

This example shows what happens when the system has dependent equations (a row of zeros), leading to infinitely many solutions rather than a unique solution.

Problem: Solve the system of equations: 2x+4y=102x + 4y = 10 3x+6y=153x + 6y = 15
Step 1: Write the augmented matrix.
[24103615]\left[\begin{array}{cc|c} 2 & 4 & 10 \\ 3 & 6 & 15 \end{array}\right]
Step 2: Divide R1R_1 by 2 to make the leading coefficient 1.
[1253615]\left[\begin{array}{cc|c} 1 & 2 & 5 \\ 3 & 6 & 15 \end{array}\right]
Step 3: Replace R2R_2 with R2−3R1R_2 - 3R_1 to eliminate the first entry in row 2.
[125000]\left[\begin{array}{cc|c} 1 & 2 & 5 \\ 0 & 0 & 0 \end{array}\right]
Step 4: Row 2 is all zeros, meaning the two equations are dependent. The system has infinitely many solutions. From row 1: x+2y=5x + 2y = 5, so x=5−2tx = 5 - 2t where y=ty = t is a free variable.
x=5−2t,y=t,t∈Rx = 5 - 2t,\quad y = t,\quad t \in \mathbb{R}
Answer: Infinitely many solutions: x=5−2tx = 5 - 2t, y=ty = t for any real number tt.

Frequently Asked Questions

What is the difference between Gaussian Elimination and Gauss-Jordan Elimination?
Gaussian Elimination reduces the augmented matrix to row-echelon form (upper triangular with zeros below each pivot), then uses back-substitution to find the solution. Gauss-Jordan Elimination goes further, reducing the matrix to reduced row-echelon form (with zeros both above and below each pivot and leading 1s), so you can read the solution directly without back-substitution. Gauss-Jordan requires more row operations but eliminates the need for the back-substitution step.
When does Gaussian Elimination fail or give no solution?
Gaussian Elimination reveals an inconsistent system when a row reduces to the form [0 0 ⋯ 0 ∣ c][0\ 0\ \cdots\ 0\ |\ c] where c≠0c \neq 0. This represents the equation 0=c0 = c, which is impossible, meaning the system has no solution. The method itself does not fail — it reliably detects whether a system has one solution, infinitely many solutions, or no solution at all.
What are the three allowed row operations in Gaussian Elimination?
The three elementary row operations are: (1) swap two rows, (2) multiply a row by a nonzero constant, and (3) add a multiple of one row to another row. These operations change the appearance of the augmented matrix but do not change the solution set of the system.

Gaussian Elimination vs. Gauss-Jordan Elimination

Gaussian EliminationGauss-Jordan Elimination
GoalReduce to row-echelon form (zeros below pivots)Reduce to reduced row-echelon form (zeros above and below pivots, leading 1s)
Final stepRequires back-substitution to find the solutionSolution is read directly from the final matrix
Number of operationsFewer row operations neededMore row operations needed
When to useSolving a system by hand; efficient for large systemsFinding the inverse of a matrix; when you want a clean final form

Why It Matters

Gaussian Elimination is one of the most fundamental algorithms in linear algebra and appears in nearly every introductory course. You will use it to solve systems of equations, determine whether a system is consistent, find the rank of a matrix, and compute determinants. It also forms the backbone of how computers solve large linear systems in engineering, physics, and data science applications.

Common Mistakes

Mistake: Performing a row operation incorrectly by subtracting the multiplier from only some entries in the row instead of all entries, including the constant on the right side of the augmented matrix.
Correction: When you perform Ri←Ri−kRjR_i \leftarrow R_i - kR_j, you must apply the operation to every entry in the row, including the entry in the augmented column. Skipping the constant column will produce a wrong answer.
Mistake: Forgetting to do back-substitution and misreading the row-echelon form as the final answer.
Correction: Row-echelon form is not the solution — it is an intermediate step. After reaching row-echelon form, you must substitute the known values from the bottom row upward to solve for each variable in turn.

Related Terms