matrix - 如何找到二进制矩阵方程 AX = B 的解？

Question

给定一个 m*n 二进制矩阵 A，m*p 二进制矩阵 B，其中 n > m 计算 X 使得 AX=B 的有效算法是什么？

例如：

A = 
1  1  0  0  1  1  0  1  0  0  
1  1  0  0  1  0  1  0  0  1  
0  1  1  0  1  0  1  0  1  0  
1  1  1  1  1  0  0  1  1  0  
0  1  1  0  1  0  1  1  1  0 

B = 
0  1  0  1  1  0  1  1  0  1  0  0  1  0  
0  0  1  0  1  1  0  0  0  1  0  1  0  0  
0  1  1  0  0  0  1  1  0  0  1  1  0  0  
0  0  1  1  1  1  0  0  0  1  1  0  0  0  
1  0  0  1  0  0  1  0  1  0  0  1  1  0  

请注意，当我说二进制矩阵时，我指的是在字段 Z_2 上定义的矩阵，也就是说，所有算术都是模 2。

如果有任何兴趣，这是我在为随机纠错码生成合适的矩阵时面临的问题。

Answer 1

您可以通过减少行来做到这一点：将 B 放在 A 的右侧，然后交换行（在整个事物中）以在第 0 行、第 0 列中获得 1；然后将该行与第 0 列中具有“1”的任何其他行进行异或，因此第 0 列中只有一个 1。然后移至下一列；如果 [1,1] 为零，则将第 1 行与后面有 1 的行交换，然后对行进行异或以使其成为该列中唯一的 1。假设 'A' 是一个方阵并且存在一个解，那么您最终将 A 转换为单位，并将 B 替换为 Ax=B 的解。如果 n > m，则系统的未知数多于方程，因此您可以求解一些未知数，并将其他未知数设置为零。在行缩减期间，如果列中没有值为“1”的值