determinant.md

Determinant of a matrix

input	output
n: size of matrix arr[][]: n x n matrix	d: determinant of matrix

example :

input:
4
1 2 3 4
1 3 4 5
4 5 6 7
3 4 5 3

output:
9

using recursion :

• number of nodes at root = 1 ( ⁴C₄ )

• number of nodes at level 1 = 4 ( ⁴C₄ x ⁴C₃ )

• number of nodes at level 2 = 12 ( ⁴C₄ x ⁴C₃ x ⁴C₂ )

• total number of operation require to calculate the determinant is ⁴C₄ + ⁴C₄ x ⁴C₃ + ⁴C₄ x ⁴C₃ x ⁴C₂ = 1 + 1 * 4 + 1 * 4 * 3 = 1 + 4 + 12 = 17

• in general this can be written as ⁿC_n + ⁿC_n x ⁿC_n-1 + ⁿC_n x ⁿC_n-1 x ⁿC_n-2 + . . . . < n!

approach 1 :

1. base conditions :

   • if size of matrix is 1 :
     • return matrix[0][0]

2. initialize determinat to 0

3. iterate through first row and find cofactor for each column

   • for column in range (0 to size) :
     • find cofactor for current column element by calling the function recusively and passing the submatrix of size - 1
     • (the submatix excludes the current column)
     • multiply the current column element with it's cofactor
     • add the result to determinant with appropriate sign
     • [ sign = (-1) ^column ]

4. return determinant

implementation :

def cofactor(matrix, column, size):
    trim = []

    for i in range(1, size):
        temp = []
        
        for j in range(size):
            if j == column: continue
            
            temp.append(matrix[i][j])
        
        trim.append(temp)    
    
    return trim

def determinant(matrix, size):
    if size == 1:
        return matrix[0][0]
    
    det = 0

    for i in range(size):
        temp = matrix[0][i] * determinant(cofactor(matrix, i, size), size - 1) 
        det += ((-1) ** i) * temp
    
    return det

n = int(input())

matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

print(determinant(matrix, n))

time and space complexity :

T(n) = O(n!)
S(n) = O(n)

---

example :

using dynamic programming (bottom up method) :

• the main computational cost is to calculate the combination of column indices ( ⁿC_r )

• for above example the cost is ⁴C₄ + ⁴C₃ + ⁴C₂ = 1 + 4 + 6 = 11

• in general this can be written as ⁿC_n + ⁿC_n-1 + ⁿC_n-2 + . . . . + ⁿC₂ < 2ⁿ

approach 2 :

1. initialize indices to string containing index from 0 to size

   • (if size of matrix is 4x4 then, indices = '0123')

2. find all combination of columns with the help of indices

   • for r in range (2 to size) :
     • find ⁿC_r of column indices
     • find determinant for each sub-matrix and store it into cofactor hash
     • for determinant of matrix of size > 2 the cofactors can be directly obtained from hash

3. return the determinant of matrix

implementation :

from itertools import combinations

def nCr(string, n):
    result = []
    
    for comb in list(combinations(string, n)):
        result.append(list(map(int, comb)))
    
    return result

def determinant(matrix, size):
    indices = ''.join([str(i) for i in range(size)])
    
    cofactor = {}
    
    for r in range(2, size + 1):
        combination = nCr(indices, r)
        i = n - r
        
        if r == 2:
            for column in combination:
                det = 0
                [j, k] = column
                det += matrix[i][j] * matrix[i+1][k] - matrix[i+1][j] * matrix[i][k]
                cofactor[''.join(map(str, column))] = det
        else:
            for column in combination:
                det = 0
                for j in column:
                    co = ''.join(map(str, column)).replace(str(j), '')
                    det += ((-1) ** column.index(j)) * matrix[i][j] * cofactor[co]
                    
                cofactor[''.join(map(str, column))] = det 
    
    return cofactor[indices]
        

n = int(input())

matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

print(determinant(matrix, n))

time and space complexity :

T(n) = O(2ⁿ)
S(n) = O(2ⁿ)

---

example :

gauss elimination method :

approach 3 :

• for row in range (0 to size) :

  • if matrix[row][row] is 0 swap with non-zero row

  • for col in range (row + 1, size) :

    • if matrix[row][col] is not 0 :

      • perform row operation (to form upper triangular matrix)

• determinant is product of diagonal elements of an upper triangular matrix

implementation :

from math import ceil

def rowOperation(matrix, i, j, size):
    a = matrix[j][i]
    b = matrix[i][i]
    
    for k in range(i, size):
        matrix[j][k] = matrix[j][k] - (a / b) * matrix[i][k]

def swap(matrix, i, j):
    matrix[i], matrix[j] = matrix[j], matrix[i]

def determinant(matrix, size):
    for i in range(size):
        k = i
        
        while matrix[k][i] == 0: k += 1
        
        if k == size: continue
        elif k != i: swap(matrix, i, k)
        
        for j in range(i + 1, size):
            if matrix[j][i] != 0:
                rowOperation(matrix, i, j, size)
    
    det = 1
    for i in range(size):
        det *= matrix[i][i]
    
    return ceil(det)

n = int(input())

matrix = []
for _ in range(n):
    row = list(map(int, input().split()))
    matrix.append(row)

print(determinant(matrix, n))

time and space complexity :

T(n) = O(n³)
S(n) = O(1)