如何找到二进制矩阵方程 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上定义的矩阵，也就是说，所有算术都是mod 2。

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

Answer 1

你可以用减少行来做到这一点：将 B 放在 A 的右侧，然后交换行（在整个事情中）以获得第 0 行中的 1，col 0; 然后将该行与第 0 列中具有"1"的任何其他行进行 xor 运算，因此第 0 列中只有一个 1。然后移动到下一列;如果 [1,1] 为零，则将第 1 行与后面有 1 的行交换，然后对行进行 XOR 行以使其成为列中唯一的 1。假设"A"是一个方阵并且存在一个解，那么你最终将 A 转换为单位，B 被替换为 Ax=B 的解。如果 n> m，则系统具有比方程更多的未知数，因此您可以求解某些未知数，并将其他未知数设置为零。在行缩减期间，如果列中没有可以使用"1"的值（在已减少的行下方），则可以跳过该列并生成相应的未知零（您最多可以在 n-m 次执行此操作）。