Как мне найти решение бинарного матричного уравнения 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, а затем поменяйте местами (в целом), чтобы получить 1 в строке 0, col 0; затем зафиксируйте эту строку в любой другой строке, которая имеет "1" в столбце 0, так что у вас есть только один 1 в столбце 0. Затем перейдите к следующему столбцу; если [1,1] равно нулю, то поменяйте местами строку 1 с более поздней строкой, в которой есть 1, затем добавьте в строку xor строки, чтобы сделать ее единственной 1 в столбце. Предполагая, что "A" является квадратной матрицей, и решение существует, тогда вы в конечном итоге конвертировали A в единицу, и B заменяется решением Ax=B. Если n > m, у вас есть система с большим количеством неизвестных, чем уравнений, так что вы можете решить для некоторых из неизвестных, и установить другие на ноль. Во время сокращения строки, если в столбце нет значений, которые должны использовать "1" (ниже уже уменьшенных строк), вы можете пропустить этот столбец и сделать соответствующий неизвестный ноль (вы можете сделать это самое большее в нм).