我如何才能找到二元矩阵方程AX = B的解决方案？ [英] How can I find a solution of binary matrix equation AX = B?

问题描述

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

Given an m*n binary matrix A, m*p binary matrix B, where n > m what is an efficient algorithm to compute X such that 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

Note, when I say binary matrix I mean matrix defined over the field Z_2, that is, where all arithmetic is mod 2.

如果有任何兴趣，这是我面临的生成适合矩阵的随机纠错code的一个问题。

If it is of any interest, this is a problem I am facing in generating suitable matrices for a random error correction code.

推荐答案

您可以用排减做到这一点：将B到A的右侧，然后换行（在整个事情）在0行获得1山口0;然后异或该行到具有任何其他行一个'1'0列，所以你只有在第0列单1然后移动到下一列;如果[1,1]是接零交换第1行与具有1有一排后，再行XOR，使其只有1列。假设'A'是一个方阵，并有一个解决方案，那么你最终必须转化为一个统一的，和B被替换为解决Ax = b的。
如果N> M，你必须比方程多未知数的系统，这样可以解决一些未知的，并设置其他为零。在该行复位，如果有一列中没有值其中有一个1使用（已降低了行下面），你可以跳过该列，并做出相应的未知为零（你可以做到这一点，最多纳米倍）。

You can do it with row reduction: Place B to the right of A, and then swap rows (in the whole thing) to get a 1 in row 0, col 0; then xor that row to any other row that has a '1' in column 0, so you have only a single 1 in column 0. Then move to the next column; if [1,1] is zero then swap row 1 with a later row that has a 1 there, then xor rows to make it the only 1 in the column. Assuming 'A' is a square matrix and a solution exists, then you eventually have converted A to unity, and B is replaced with the solution to Ax=B. If n > m, you have a system with more unknowns than equations, so you can solve for some of the unknowns, and set the others to zero. During the row reduction, if there are no values in a column which have a '1' to use (below the rows already reduced) you can skip that column and make the corresponding unknown zero (you can do this at most n-m times).

这篇关于我如何才能找到二元矩阵方程AX = B的解决方案？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！