求模为2的线性矩阵方程

问题描述

我有一个这样的矩阵：

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])

我找到了Solving systems of equations modulo a certain number, with or without numpy，但由于某种原因，解决方案对我不起作用。我收到错误：

ValueError：指定第三个参数时，POW()第二个参数不能为负

为什么它不工作？有其他解决方案吗？

---

解决方案

由于模数的原因，您无法使用经典的线性代数方法来解决此组合问题。希望模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矩阵上，该问题似乎很难解，并且非常接近于求解被证明为NP-complete的boolean satisfiability problem。

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

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