用模 2 求解线性矩阵方程

Question

我有一个这样的矩阵：

import numpy as np

A = np.array([
    [1,1,1,0],
    [1,1,0,1],
    [1,0,1,1],
    [0,1,1,1]
])

和一个向量：

b = np.array([0,1,1,1])

我想解方程：A * x = b。但我想以模 2 的形式解决它。这意味着 1 + 1 = 0。所以在这种情况下的解决方案是：

x = np.array([0,0,0,1])

我找到了，但由于某种原因，该解决方案对我不起作用。我收到错误：

ValueError: pow() 2nd argument cannot be negative when 3rd argument specified

为什么不起作用？还有其他解决方案吗？

Answer 1

由于模数，您不能使用经典的线性代数方法来解决这个组合问题。希望使用模数 2 可以使问题简单得多。实际上，加法模 2 的行为类似于 XOR 二元函数，乘法类似于 AND 二元函数。因此，问题可以改写如下：

x1 ^ x2 ^ x3 ^  0 = 0
x1 ^ x2 ^  0 ^ x4 = 1
x1 ^  0 ^ x3 ^ x4 = 1
 0 ^ x2 ^ x3 ^ x4 = 1

因此：

x1 ^ x2 ^ x3 = 0
x1 ^ x2 ^ x4 = 1
x1 ^ x3 ^ x4 = 1
x2 ^ x3 ^ x4 = 1

这个例子可以很简单地解决，因为x1 ^ x2 ^ x3 = 0意味着要么x1，x2和x3为零，要么树变量中的两个设置为1，这与以下3条规则冲突。

然而，在任意 A 矩阵上，问题似乎很难解决并且非常接近解决 boolean satisfiability problem, which is proven to be NP-complete.

此外，请注意，关于 A 和 b 的解决方案可能不存在或可能不是唯一的。

使用 CSP 求解器 肯定有助于轻松解决此问题，但如果问题不是 NP 完全问题（这尚未得到证明），它可能不是最佳方法).有许多 Python 库可以解决这个问题（例如 OR 工具应该能够做到这一点）。

Solve a linear matrix equation with modulo 2