How To Tell If a Matrix is Invertible

Have you been asked a question in coding interviews to find out how to tell if a matrix is invertible? It is very easy to find out if you are familiar with linear algebra.

But if you do not know linear algebra or have forgotten about it, today in this post I will discuss how you can find or check if the matrix is invertible.

Linear Algebra Fundamental

So, any square matrix of size n-by-n is called Invertible when a square matrix A is multiplied with square matrix B or vice versa the result is the same.

AB = BA = In

Where In represents the n-by-n identity matrix. Then in this case Matrix B is called the inverse matrix of A. Hence a square matrix is invertible only when its determinant is non-zero.

So, basically, we look into this above problem we can clearly conclude that B = A-1. Hence to derive completely and remove the confusion. To check if any given matrix is invertible we need to find 1/A and then multiply it with A.

A.A-1 = In

For Example,

Then we need to check that AB = BA = I_n. Where I_n needs to be like the below image. which will prove that A is invertible and B is its inverse.

How to Tell if a Matrix is Invertible in C++

Let us see the below-working code to check if the matrix is invertible using C++ and Python.

// C++ program to determine if matrix is invertible or not.
#include <stdio.h>
using namespace std;
 
//Keeping dimensions of the Matrix as 4 for now.
#define N 2
 
void findCoFactor(int matrix[N][N], int temp[N][N], int p, int q, int n)
{
    int i = 0, j = 0;
 
    // Looping for each element of the matrix
    for (int row = 0; row < n; row++) {
        for (int col = 0; col < n; col++) {
            // Copying into temporary matrix only those element
            // which are not in given row and column
            if (row != p && col != q) {
                temp[i][j++] = mat[row][col];
 
                // If Row is filled, then increase row index and
                // reset column index to start i.e. 0.
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
}
 
/* Recursive function for finding determinant of matrix.
n is current dimension of matrix[][]. */
int getDetOfMatrix(int matrix[N][N], int n)
{
    int D = 0; // Initialize result
 
    // If matrix has only one element then simply return the matrix.
    if (n == 1)
        return matrix[0][0];
 
    int temp[N][N]; // To store cofactors
 
    int sign = 1; // To store sign multiplier
 
    // Loop through each element of first row
    for (int f = 0; f < n; f++) {
        // Getting Cofactor of matrix[0][f]
        findCoFactor(matrix, temp, 0, f, n);
        D += sign * matrix[0][f] * getDetOfMatrix(temp, n - 1);
 
        // elements are to be added with alternate sign
        sign = -sign;
    }
 
    return D;
}
 
bool isMatrixInvertible(int matrix[N][N], int n)
{
    if (getDetOfMatrix(matrix, N) != 0)
        return true;
    else
        return false;
}
 
// Main function code to test above functions.
int main()
{
    int matrix[N][N] = { { 1, 2 },
                      { 3, 4}}
    if (isMatrixInvertible(matrix, N))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

How to Tell if a Matrix is Invertible in Python

# Function to get cofactor of
# matrix[p][q] in temp[][]. n is
# current dimension of matrix[][]
def findCoFactor(matrix, temp, p, q, n):
	i = 0
	j = 0

	# Looping for each element
	# of the matrix
	for row in range(n):
		
		for col in range(n):
			
			# Copying into temporary matrix
			# only those element which are
			# not in given row and column
			if (row != p and col != q) :
				
				temp[i][j] = matrix[row][col]
				j += 1

				# Row is filled, so increase
				# row index and reset col index
				if (j == n - 1):
					j = 0
					i += 1

# Recursive function for
# finding determinant of matrix.
# n is current dimension of mat[][].
def getDetOfMatrix(matrix, n):
	D = 0 # Initialize result

	# Base case : if matrix
	# contains single element
	if (n == 1):
		return matrix[0][0]
		
	# To store cofactors
	temp = [[0 for x in range(N)]
			for y in range(N)]

	sign = 1 # To store sign multiplier

	# Iterate for each
	# element of first row
	for f in range(n):
		
		# Getting Cofactor of matrix[0][f]
		findCoFactor(matrix, temp, 0, f, n)
		D += (sign * matrix[0][f] *
			getDetOfMatrix(temp, n - 1))

		# inverted elements are needs to be added with negative sign.
		sign = -sign
	return D

def isMatrixInvertible(matrix, n):
	if (getDetOfMatrix(matrix, N) != 0):
		return True
	else:
		return False
	
# Main Function Code
matrix = [[ 1, 2],
	[ 3, 4 ]]
	
N = 2
if (isMatrixInvertible(matrix, N)):
	print("Yes")
else:
	print("No")

If you liked the answer then please follow us on Facebook and Twitter. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview-related questions? Check Top Interview Questions category.