Determining whether the determinant of an NxN integer matrix is even or odd
For a given NxN (0,1) matrix whose values are integers, I want to determine if the determinant of the matrix is even (mod2 = 0) or odd (mod2 = 1).
Is there an efficient algorithm? N is equal to 100, so the O (N!) Brute force solution is too slow.
If I do Gaussian elimination and calculate the determinant naively, the determinant will be at most 200 digits, so I have to do 200 digit multiplications and divisions.
source to share
Operating mode 2 is extremely simple. The following is a recursive approach based on the following:
-
If the first column is all 0s, then the determinant is 0.
-
If the first column has 1 in the first row and is 0, then the determinant is the same as the determinant of the matrix obtained by removing the first row and the first column.
-
Swapping two strings does not affect the mod-2 qualifier. If you weren't working with mod 2, you would multiply by -1, but -1 (mod 2) = 1.
-
Replacing a string with the sum of that string and another string does not affect the determinant.
-
When you add two lines whose first entries are 1, then mod-2, you end up with a line whose first entry is 0.
Python 3 implementation:
def det2(mat):
matrix = [[a%2 for a in row] for row in mat]
n = len(matrix)
if n == 1: return matrix[0][0]
#first find a nonzero element in first column
i = 0
while i < n and matrix[i][0] == 0: i += 1
if i == n:
return 0 #since a column of zeros
else:
if 0 < i: matrix[0],matrix[i] = matrix[i],matrix[0]
#clear rest of column:
for i in range(1,n):
if matrix[i][0] == 1:
matrix[i] = [a+b for a,b in zip(matrix[i],matrix[0])]
rest = [row[1:] for row in matrix[1:]]
return det2(rest)
Tested as follows:
import random
def randMatrix(n,k):
return [[random.randint(0,k+1) for i in range(n)] for j in range(n)]
A = randMatrix(100,100) #a 100x100 random matrix with entries in 0,1,...,100
det2(A) #takes less than a second
The above code is basically a proof of concept. It's reasonably fast, although Python is an interpreted language. If you use @ mcdowella's idea and box the records into 64-bit integer variables and use bitwise operations, the above code could be modified to run very fast in something like C. Also, of course, it's easy enough to write this in iterative. rather than recursively:
def det2(mat):
matrix = [[a%2 for a in row] for row in mat]
n = len(matrix)
for i in range(n):
#first find a nonzero element in column i in row i or below:
j = i
while j < n and matrix[j][i] == 0: j += 1
if j == n:
return 0 #since a zero will be on final diagonal
else:
if i < j: matrix[i],matrix[j] = matrix[j],matrix[i]
#clear rest of column:
for j in range(i+1,n):
if matrix[j][i] == 1:
matrix[j] = [(a+b) % 2 for a,b in zip(matrix[i],matrix[j])]
#if you get to this stage without returning 0:
return 1
source to share