C++ Program to check if a matrix is invertible

The first necessary condition for a matrix to have an inverse is, the matrix has to be a square matrix (m*n matrix is not allowed). The matrix has to be of order n*n.

Suppose we have a matrix X. If we are able to find a matrix Y such that XY = YX = I (Identity matrix), then the matrix X is called invertible.

A square matrix is invertible iff it is a non-singular matrix (i.e. determinant of the matrix is not zero). As a reason, we can say divisibility. To calculate the inverse of a matrix we divide the transpose of that matrix by the determinant of that matrix. That’s why if determinant becomes zero, we can’t divide by the determinant. So, the determinant has to be non-zero to get an inverse.

You can check hereĀ how to calculate the transpose of a matrix.

Let’s see an example for invertibility:

C++ Program to check if a matrix is invertible

Check if a matrix is invertible

 

Approach:

We will calculate the determinant value of the matrix. If the value of the determinant is 0, it is not invertible. Otherwise, it is invertible.

To calculate the determinant we will use the formal method, add elements multiplied by cofactors with alternating signs. To calculate the cofactor we have a temporary array, in which we store the elements that are not in that row and column. Now, the cofactor array is further going for recursion to calculate determinant.

Code:

#include <iostream>
using namespace std;

// dimension of the matrix.
// change it according to requirement.
#define dim 5

// function to calculate cofactor.
void calculate_cofactor(int matrix[dim][dim], int cofactor[dim][dim], int x, int y, int n) {
  
  int p = 0, q = 0;

  for(int i=0; i<n; i++) {
    
    for(int j=0; j<n; j++) {
      
      // elements of row x and column y is ignored.
      if(i != x && j != y) {

        cofactor[p][q++] = matrix[i][j];

        // column reached upper limit
        // so, setting column to 0 and increment row.
        if(q == n-1){
          q = 0;
          p++;
        }
      }
    }
  }
}

// function to calculate determinant,
// this function works recursively.
int get_determinant(int matrix[dim][dim], int n) {
  
  int rel = 0, sign = 1;

  // terminating condition of recursion.
  if(n == 1)
    return matrix[0][0];

  // another 2D-Array to store cofactor.
  int cofactor[dim][dim];

  for(int i = 0; i<n; i++) {

    // calculating the cofactor.
    calculate_cofactor(matrix, cofactor, 0, i, n);
    
    // adding values multiplied by cofactor.
    rel += sign * matrix[0][i] * get_determinant(cofactor, n-1);

    // alternating the sign.	
    sign = 0-sign;
  }

  // value of rel is the desired determinant.
  return rel;
}

bool has_inverse(int matrix[dim][dim], int n) {

  if(get_determinant(matrix, n) == 0)
    return false;

  return true;
}

int main() {

  int matrix[dim][dim] = {{1, 2, 3, 4, 5},
              {6, 7, 8, 9, 10},
              {11, 12, 13, 14, 15},
              {16, 17, 18, 19, 20},
              {21, 22, 23, 24, 25}};

  if(has_inverse(matrix, dim))
    cout << "Invertible\n";
  else
    cout << "Non-invertible\n";

  return 0;
}

Output:

Non-invertible

Leave a Reply