Решите систему AX=B для X над конечным полем F2

Question

Пусть A, B и X - двоичные матрицы (в F2) {0,1} положительных значений, где A и B имеют размер n×m при n>m (больше уравнений, чем переменных). X - матрица m×m. Вычислить X так, чтобы AX=B.

Здесь A не является квадратичной матрицей.

У меня есть A и B, и я ищу X. Какой алгоритм я должен использовать, чтобы найти X?

я пытался

X=pinv(A)*B; 
X=mod(X,2); 

но результаты являются действительными значениями, а не двоичными (элементы конечного поля F2)

Answer 1

Ни A\B ни pinv(A)*B помочь вам в любом, потому что эти команды обрабатывают записи матрицы как действительные числа, а не элементы конечного поля GF(2).

Команда gflineq решает линейные системы над полем GP(p) с x = gflineq(A,b,p); эта команда является частью панели инструментов системы связи. Если у вас есть набор инструментов, то все, что вам нужно сделать, это поместить матричное уравнение AX=B в форму Mx=B, сложив столбцы B, а затем преобразовать решение обратно в матричную форму. Как это:

[n, m] = size(A);
b = B(:);                 % stacked B
M = kron(eye(m), A);      % duplicated A to match
sol = gflineq(M, b, 2);   % solved Mx=b over GF(2)
X = reshape(sol, m, m);   % reshaped into matrix form X 

Теперь, если у вас нет панели инструментов системы связи, вам нужно будет самостоятельно реализовать решение поверх GF(2). Метод является стандартным: исключение Гаусса, и вы можете найти много его реализации в Интернете. В частности, для двоичных матриц этот алгоритм описан в разделе Как найти решение бинарного матричного уравнения AX = B?