Gauss-Jordan Method

In the Gauss-Jordan method, we reduce the coefficient matrix into an identity matrix. We eliminate variables from all rows except the pivot row and also normalize the pivot row. Once the method is complete, we will be left with an identity matrix and the solution vector.

This page presents an online interactive calculator for the Gauss-Jordan method with a step-by-step explanation, algorithm, flowchart, pseudo-code and programs in C and Python.

Interactive Calculator

The following is an interactive calculator for the Gauss-Jordan method with partial pivoting:

System size--System size---12345678

$x_{1}+$

$x_{2}+$

$x_{3}=$

$x_{1}+$

$x_{2}+$

$x_{3}=$

$x_{1}+$

$x_{2}+$

$x_{3}=$

Solution,

The above system can be represented in matrix notation as:

$$\begin{bmatrix}7 & 5 & 3 \\ 2 & 1 & 6 \\ 1 & 2 & 3\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}1 \\ 2 \\ 3\end{bmatrix}$$

Step 1

Take $R_{1}$ as pivot row, $a_{11}=7$ as pivot element, and eliminate $x_{1}$ from $R_{2}, R_{3}$ by applying

$$R_{2}\leftarrow R_{2}-\frac{2}{7}R_{1}, R_{3}\leftarrow R_{3}-\frac{1}{7}R_{1}$$

$$\begin{bmatrix}7 & 5 & 3 \\ 0 & -0.4 & 5.14 \\ 0 & 1.3 & 2.57\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}1 \\ 1.7143 \\ 2.8571\end{bmatrix}$$

Step 2

Take $R_{2}$ as pivot row, $a_{22}=-0.4286$ as pivot element, and eliminate $x_{2}$ from $R_{1}, R_{3}$ by applying

$$R_{1}\leftarrow R_{1}+\frac{5}{0.4286}R_{2}, R_{3}\leftarrow R_{3}+\frac{1.2857}{0.4286}R_{2}$$

$$\begin{bmatrix}7 & 0 & 63 \\ 0 & -0.4 & 5.14 \\ 0 & 0 & 18\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}21 \\ 1.7143 \\ 8\end{bmatrix}$$

Step 3

Take $R_{3}$ as pivot row, $a_{33}=18$ as pivot element, and eliminate $x_{3}$ from $R_{1}, R_{2}$ by applying

$$R_{1}\leftarrow R_{1}-\frac{63}{18}R_{3}, R_{2}\leftarrow R_{2}-\frac{5.1429}{18}R_{3}$$

$$\begin{bmatrix}7 & 0 & 0 \\ 0 & -0.4 & 0 \\ 0 & 0 & 18\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}-7 \\ -0.5714 \\ 8\end{bmatrix}$$

Step 4

Normalize $R_{1}, R_{2}, R_{3}$ by applying

$$R_{1}\leftarrow \frac{R_{1}}{7}, R_{2}\leftarrow \frac{R_{2}}{-0.4286}, R_{3}\leftarrow \frac{R_{3}}{18}$$

$$\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}\begin{bmatrix}x_{1} \\ x_{2} \\ x_{3}\end{bmatrix}=\begin{bmatrix}-1 \\ 1.3333 \\ 0.4444\end{bmatrix}$$

Hence the solution for the system is:

$x_{1}=-1, x_{2}=1.3333, x_{3}=0.4444$

Algorithm

The following represents the algorithm for the Gauss-Jordan method without pivoting:

1. Start
2. Declare and read the size of the system $N$
3. Declare variable $S$ for system in augmented matrix notation, as a 2D array of size $N\times (N+1)$. Such that $S_{i,j}$ represents the element at $i^{th}$ row and $j^{th}$ column. The last column represents the constant vector.
4. For each elements of $S$ input a value from user
5. Start from $k=1$
6. Take $R_{k}$ as pivot row and then then eliminate $x_{k}$ from the rows $R_{i}$ for $i=1,...,N$ and $i\neq k$ by applying $R_{i}\leftarrow R_{i}- \frac{S_{i,k}}{S_{k,k}}R_{k}$ modifying $S$.
7. Increase $k$ by $1$. Goto step 6 if $k \text{<} N$
8. Normalize $R_{k}$ by applying $R_{k}\leftarrow \frac{R_{k}}{a_{k,k}}$ for $k=1...N$
9. Print solution $x_{k}=S_{k,N+1}$
10. Stop

Pseudo Code

Read N
Declare S = Array(N, N+1)

-- Read the input
for i=1:N
  for j=1:N+1
    Read S[i][j]
  endfor
endfor

 and normalization
-- Perform elimination
for k=1:N
  for i=1:N
    factor = S[i][k]/S[k][k]
    if i!=k:
      for j=1:N+1
          S[i][j] = S[i][j] - factor * S[k][j]
      end
    end
  end
end

-- Perform normalization and print solution
for k=1:N-1
  print "xk=", S[k][N+1]/S[k][k]
end

Program

C

/*
 * Gauss Jordan Method in C
*/

#include <stdio.h>
#define MAX_SYSTEM_SIZE 20

int main()
{
  // The size of linear system
  int N = 3;

  // Preallocate enough memory for the system
  double S[MAX_SYSTEM_SIZE][MAX_SYSTEM_SIZE+1];

  // Get the size of the system
  printf("Enter the size of linear system: ");
  scanf("%d", &N);

  // Limit the max system size
  if (N >= MAX_SYSTEM_SIZE)
  {
    printf("Please enter size below %d", MAX_SYSTEM_SIZE);
    return -1;
  }
  
  // Ask for the system
  printf("\nEnter the matrix in augmented matrix form:\n");
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N + 1; j++)
    {
      printf("Enter S[%d][%d] = ", i + 1, j + 1);
      scanf("%lf", &S[i][j]);
    }
  }

  // Perform Elimination
  for (int k = 0; k < N; k++)
  {
    for (int i = 0; i < N; i++)
    {
      if(i!=k){
        // Precalculate factor as S[i][k] will 
        // change in the following loop
        double factor = S[i][k] / S[k][k];
        for (int j = 0; j < N + 1; j++)
        {
          S[i][j] = S[i][j] - factor * S[k][j];
        }
      }
    }
  }

  // Print solution by performing normalization
  printf("\nSolution for the system is: \n");
  for (int i = 0; i < N; i++)
  {
    printf("x%d = %lf\n", i + 1, S[i][N]/S[i][i]);
  }

  return 0;
}

Python

#
# Gauss Jordan Method in Python
#

N = int(input("Enter the size of the system "))
S = [[0]*(N+1) for _ in range(N)]

# Ask for input
print("Enter the system in augmented matrix form:")
for i in range(N):
  for j in range(N+1):
    S[i][j] = float(input(f"Enter S[{i+1}][{j+1}] = "))

# Perform elimination
for k in range(N):
  for i in range(N):
    if i!=k:
      # Precalculate factor as S[i][k] will change in the following loop
      factor = S[i][k]/S[k][k]
      for j in range(N+1):
        S[i][j] = S[i][j] - factor*S[k][j]


# Print the solution by performing normalization
print("Solution for the system is:");
for i in range(N):
  print(f"x{i+1} = {S[i][N]/S[i][i]}")

Complexity

The complexity of the Gauss-Jordan method is $O(N^3)$. This comes from the three nested loops in the forward elimination step. The space complexity is $O(N^2)$ which comes from the size of the system.

Advantages

1. Simpler implementation.
2. It can be used for calculating the inverse of a square matrix.

Disadvantages

1. Requires 50% more operations than the Gauss Elimination method.