在有限域 F2 上求解 X 的系统 AX=B

Question

Let A, B, and X be binary matrices (in F2 ) {0,1} positive values, where A and B are of size n×m with n>m (more equations than variables). X is an m×m matrix. Compute X such that 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)；此命令是通信系统工具箱的一部分。如果你有工具箱，那么你需要做的就是通过堆叠 B 的列将矩阵方程 AX=B 转化为 Mx=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

现在，如果您没有 Communications System Toolbox，则需要自己通过 GF(2) 实现解决方案。方法是标准的：Gaussian elimination, and you can find lots of its implementation online. Specifically for binary matrices this algorithm is described in How can I find a solution of binary matrix equation AX = B?

在有限域 F2 上求解 X 的系统 AX=B

Solve the system AX=B for X over the finite field F2

binary

matlab

linear-algebra

xor