对于给定的nxn(0,1(-matrix，其值都是整数，我想确定矩阵的决定因素是否均匀(mod2 = 0(或奇数(mod2 = mod2 =(1(。
是否有有效的算法？N高达100，因此蛮力O(N！(解决方案太慢。
如果我进行高斯淘汰并天真地计算决定因素，则决定因素最多为200位数字，因此我必须进行200位数字乘法和划分。
工作mod 2非常容易。以下是基于以下情况的递归方法：
-
如果第一列为全部0，则决定符为0。
-
如果第一列在第一行中具有1个，则在下面为0，则确定因素与通过删除第一行和第一行获得的矩阵的决定因素相同。
-
交换两个行对MOD-2决定因素没有影响。如果您不工作mod 2，则会乘以-1，但是-1(mod 2(=1。
-
用该行的总和替换一行，而另一行对决定因素没有影响。
-
当您添加两个行条目为1然后mod-2时，您将获得第一个条目为0的行。
python 3实现：
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)
测试如下：
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
上述代码主要是概念证明。即使Python是一种解释的语言，这也是相当快的。如果您使用@mcdowella的想法并将条目包装在64位整数变量中并使用刻度操作，则可以修改上述代码以在C中迅速工作。它以迭代而不是递归形式：
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
将奇数替换为1，将偶数替换为0。如果新的决定符值是奇数的，那么母亲的值是奇数的，否则否则