Python实现模2算术下向量线性相关性校验的方案咨询

核心原理 #

模2算术下的向量线性相关性判断，等价于将向量按行/列组成矩阵后，计算矩阵在GF(2)有限域上的秩：若秩小于向量总个数，说明向量组线性相关。你之前用scipy的null_space得到的是实数域的计算结果，不适用有限域场景。

方案1：纯NumPy实现GF(2)高斯消元（无额外依赖，性能最优） #

直接基于NumPy的布尔运算实现GF(2)域的高斯消元求秩，逻辑简单，没有额外依赖，性能远高于sympy的符号运算，适配大规模矩阵场景。

示例代码 #

import numpy as np

def gf2_rank(matrix):
    """
    计算GF(2)域下矩阵的秩
    matrix: 输入的0-1二维数组，每行代表一个向量
    """
    M = matrix.copy().astype(bool)
    rank = 0
    n_rows, n_cols = M.shape
    
    for col in range(n_cols):
        # 找当前列第一个为1的行作为主元
        pivot = None
        for r in range(rank, n_rows):
            if M[r, col]:
                pivot = r
                break
        if pivot is None:
            continue
        
        # 交换主元行和当前秩对应行
        M[[rank, pivot]] = M[[pivot, rank]]
        
        # 消去其他行当前列的1
        for r in range(n_rows):
            if r != rank and M[r, col]:
                M[r] ^= M[rank]
        
        rank += 1
    return rank

# 测试你给出的示例
v1 = [1,1,0]
v2 = [0,1,1]
v3 = [1,0,1]
M = np.array([v1, v2, v3])
rank = gf2_rank(M)
print(f"GF(2)下矩阵秩为{rank}，向量个数为3，是否线性相关：{rank < 3}")
# 输出结果：GF(2)下矩阵秩为2，向量个数为3，是否线性相关：True

性能优化提示 #

如果你的矩阵列数不超过64/128，可以将每一行的0-1值压缩为一个uint64/uint128整数，消元过程用位运算代替逐元素运算，速度可以再提升10~100倍，适合处理十万级以上行的超大矩阵。

方案2：基于galois库实现（封装完善，开发成本低） #

galois是专门用于有限域运算的Python库，底层基于NumPy矢量化实现，性能比sympy高2~3个量级，API封装完善，不需要自己实现消元逻辑。

示例代码 #

首先安装依赖：pip install galois

import galois
import numpy as np

# 初始化GF(2)域
GF = galois.GF(2)
# 把numpy数组转为GF(2)域的矩阵
v1 = [1,1,0]
v2 = [0,1,1]
v3 = [1,0,1]
M = GF(np.array([v1, v2, v3]))
# 计算秩
rank = np.linalg.matrix_rank(M)
# 也可以直接求零空间
null_space = M.null_space()
print(f"GF(2)下矩阵秩为{rank}，是否线性相关：{rank < M.shape[0]}")
print(f"零空间维度：{null_space.shape[1]}")

内容的提问来源于stack exchange，提问作者fcrp