algorithm - 确定 NxN 整数矩阵的行列式是偶数还是奇数

对于给定的 NxN (0,1)-矩阵，其值都是整数，我想确定矩阵的行列式是偶数 (mod2 = 0) 还是奇数 (mod2 = 1)。

有什么有效的算法吗？ N 和 100 一样大，所以一个蛮力 O(N!) 解决方案太慢了。

如果我进行高斯消元并天真计算行列式，行列式最多为200位，因此我必须进行200位乘法和除法。

最佳答案

工作模式 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

关于algorithm - 确定 NxN 整数矩阵的行列式是偶数还是奇数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43702846/