Problem

Given a square matrix, determine if the matrix is invertible. A matrix is invertible if and only if its determinant is non-zero. Write a function that takes a square matrix as input and returns true if it is invertible and false otherwise.

Definition

An invertible matrix (also known as a non-singular or non-degenerate matrix) is a square matrix that has an inverse. Specifically, a square matrix ( A ) is said to be invertible if there exists another square matrix ( B ) of the same size such that:

$$ A \cdot B = B \cdot A = I $$

where I is the identity matrix of the same dimension as A.

More: Invertible Matrices

Examples

Example 1:

1
2
3

Input: matrix = [[1, 2], [3, 4]]
Output: false
Explanation: The determinant of the matrix is calculated as (1*4 - 2*3) = 4 - 6 = -2. Since the determinant is not zero, the matrix is not invertible.

Example 2:

1
2
3
4

Input: matrix = [[2, 3], [1, 4]]
Output: true
 Explanation: The determinant of the matrix is calculated as (2*4 - 3*1) = 8 - 3 = 5.
              Since the determinant is non-zero, the matrix is invertible.

Example 3:

1
2
3

Input: matrix = [[0, 1], [1, 2]]
Output: true
Explanation: The determinant of the matrix is calculated as (0*2 - 1*1) = 0 - 1 = -1. Since the determinant is non-zero, the matrix is invertible.

Solution

Method 1 - Calculating determinant

To determine if a matrix is invertible, we need to check if its determinant is non-zero. The steps are as follows:

  1. Square Matrix Check: First, ensure that the input matrix is square (i.e., it has the same number of rows and columns). If not, the matrix cannot be invertible.

  2. Determinant Calculation: Calculate the determinant of the matrix. For a 2x2 matrix [a, b], [c, d], the determinant is ad - bc. For larger matrices, we recursively calculate the determinant using the cofactor expansion.

  3. Invertibility Check: If the determinant is non-zero, the matrix is invertible. If the determinant is zero, the matrix is not invertible.

Code

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

public class Solution {
    // Check if the matrix is invertible by checking if the determinant is non-zero
    public boolean isMatrixInvertible(int[][] matrix) {
        int n = matrix.length;
        if (n != matrix[0].length) {
            throw new IllegalArgumentException("Matrix must be square");
        }
        // Calculate the determinant
        int determinant = calculateDeterminant(matrix, n);
        return determinant != 0;
    }

    // Helper method to calculate the determinant
    private int calculateDeterminant(int[][] matrix, int n) {
        if (n == 1) {
            return matrix[0][0];
        }
        if (n == 2) {
            return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        }

        int determinant = 0;
        int sign = 1;
        for (int i = 0; i < n; i++) {
            determinant += sign * matrix[0][i] * calculateDeterminant(getMinor(matrix, 0, i), n - 1);
            sign = -sign;
        }
        return determinant;
    }

    // Helper method to get the minor of a matrix
    private int[][] getMinor(int[][] matrix, int row, int col) {
        int n = matrix.length;
        int[][] minor = new int[n - 1][n - 1];
        int minorRow = 0, minorCol;
        for (int i = 0; i < n; i++) {
            if (i == row) continue;
            minorCol = 0;
            for (int j = 0; j < n; j++) {
                if (j == col) continue;
                minor[minorRow][minorCol++] = matrix[i][j];
            }
            minorRow++;
        }
        return minor;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        int[][] matrix1 = {
            {1, 2},
            {3, 4}
        };
        System.out.println(solution.isMatrixInvertible(matrix1)); // Output: false
        
        int[][] matrix2 = {
            {2, 3},
            {1, 4}
        };
        System.out.println(solution.isMatrixInvertible(matrix2)); // Output: true
        
        int[][] matrix3 = {
            {0, 1},
            {1, 2}
        };
        System.out.println(solution.isMatrixInvertible(matrix3)); // Output: true
    }
}
 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution:

    def is_matrix_invertible(self, matrix):
        n = len(matrix)
        if n != len(matrix[0]):
            raise ValueError("Matrix must be square")
        # Calculate the determinant
        determinant = self.calculate_determinant(matrix, n)
        return determinant != 0

    # Helper method to calculate the determinant
    def calculate_determinant(self, matrix, n):
        if n == 1:
            return matrix[0][0]
        if n == 2:
            return matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0]
        
        determinant = 0
        sign = 1
        for i in range(n):
            determinant += sign * matrix[0][i] * self.calculate_determinant(self.get_minor(matrix, 0, i), n - 1)
            sign = -sign
        return determinant

    # Helper method to get the minor of a matrix
    def get_minor(self, matrix, row, col):
        minor = []
        for i in range(len(matrix)):
            if i != row:
                minor.append([matrix[i][j] for j in range(len(matrix[i])) if j != col])
        return minor

# Example usage
solution = Solution()

matrix1 = [
    [1, 2],
    [3, 4]
]
print(solution.is_matrix_invertible(matrix1)) # Output: False

matrix2 = [
    [2, 3],
    [1, 4]
]
print(solution.is_matrix_invertible(matrix2)) # Output: True

matrix3 = [
    [0, 1],
    [1, 2]
]
print(solution.is_matrix_invertible(matrix3)) # Output: True

Complexity

  • ⏰ Time complexity: O(n!). The time complexity of calculating the determinant of an n x n matrix can be high (O(n!) using cofactor expansion), which may be impractical for large matrices.
  • 🧺 Space complexity: O(1)