如何在Python中求解GF(2)上的宽矩形线性矩阵方程AX=B

问题背景 #

给定GF(2)（模2）下的两个二进制矩阵：

• A：11×12矩阵，秩为11（宽矩阵，变量数多于方程数）
• B：同尺寸11×12矩阵，秩为11

需求：找到系数矩阵X（11×11），使得X与A的左乘等于B（即B的每一行是A的行的线性组合，允许行交换操作）。

现有尝试的局限 #

• 常规np.linalg.solve无法直接使用，因为A不是方阵
• 转换为galois库的GF(2)矩阵后，填充冗余行会导致矩阵奇异，无法用标准方阵求解函数
• 已得到A的行最简形，但无法直接推导出行变换序列或X矩阵

Python解决方案（基于galois库） #

galois库原生支持GF(2)域下的非方阵线性方程组求解，利用其矩阵的solve_left方法可直接得到X：

完整代码 #

import numpy as np
import galois

# 定义GF(2)域
GF = galois.GF(2)

# 输入矩阵A和B
A = np.array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
              [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
              [0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0],
              [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
              [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
              [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
              [0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]])

B = np.array([[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]])

# 转换为GF(2)矩阵
A_gf = GF(A)
B_gf = GF(B)

# 求解X：X @ A_gf = B_gf（行线性组合）
X = B_gf.solve_left(A_gf)

# 验证解的正确性
assert np.array_equal(X @ A_gf, B_gf), "解验证失败"

print("系数矩阵X：")
print(X)

关键说明 #

• solve_left方法专门用于求解左乘线性方程组X·A = B，适用于非方阵场景，此处因A和B的秩匹配且行空间一致，解唯一
• 验证步骤确保X满足原方程，避免计算错误

获取行变换操作序列 #

若需要得到将A转换为B的显式行变换序列，可通过行约简时返回的变换矩阵Q实现：

# 获取行变换矩阵Q，Q·A_gf = RREF(A_gf)
R, Q = A_gf.row_reduce(return_q=True)

# Q是所有行初等变换的乘积矩阵，其逆矩阵可将RREF(A)转换回A
Q_inv = Q.inv()

# 推导变换矩阵：X = B_gf @ Q_inv @ R.inv()

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