c++ - 有效检查三个二进制 vector 是否在有限域上线性独立

Question

我在我的程序中给出了三个由 unsigned int 表示的二进制 vector v1、v2、v3 和一个有限域 F，它也是一组二进制 vector 。我需要检查 vector 是否线性无关，即 F 中没有 f1、f2 使得 f1*v1 +f2*v2 = v3。

直接的蛮力解决方案是遍历字段并检查所有可能的线性组合。

是否存在更高效的算法？

我想强调两点:

1. 场元素是 vector ，而不是标量。因此，e 域元素 f1 和给定 vector vi 的乘积是点积。所以高斯消元法不起作用(如果我没有漏掉什么的话)
2. 字段是有限的，所以如果我发现 f1*v1 +f2*v2 = v3 对于某些 f1,f2 这并不意味着 f1 ,f2 属于F。

Answer 1

如果 vector 在 r^2 中，那么它们是自动相关的，因为当我们将它们制成矩阵并将其简化为阶梯形式时，将至少有一个自由变量(在本例中只有一个)。

如果 vector 在 R^3 中，那么你可以从它们 i 中创建一个矩阵。一个二维数组，然后你可以取该矩阵的行列式。如果行列式等于 0，则 vector 是线性相关的，否则不是。

如果 vector 在 R^4、R^5 等中，则适当的方法是将矩阵简化为阶梯形式。