如何检查 m 个 n 大小的向量是否线性无关？
免责声明
严格来说，这不是一个编程问题，但大多数程序员迟早都必须处理数学（尤其是代数），所以我认为答案将来可能对其他人有用。
现在的问题
我试图检查 m 个维度为 n 的向量是否线性无关。 如果 m == n 您可以使用向量构建一个矩阵并检查行列式是否为 != 0。但是如果 m < n？
有什么提示吗？
另请参阅此视频讲座。
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
构造一个向量矩阵（每个向量一行），并对该矩阵执行高斯消除 。 如果任何矩阵行相互抵消，则它们不是线性无关的。
最简单的情况是当 m > 1 时。 n，在这种情况下，它们不能线性无关。
Construct a matrix of the vectors (one row per vector), and perform a Gaussian elimination on this matrix. If any of the matrix rows cancels out, they are not linearly independent.
The trivial case is when m > n, in this case, they cannot be linearly independent.
构造一个矩阵
M，其行是向量并确定M的秩。 如果M的秩小于m（向量的数量），则存在线性相关性。 在确定M的排名的算法中，一旦获得一行零，您就可以停止该过程，但是运行该算法直至完成还可以提供生成集的维数向量。 哦，确定 M 的秩的算法只是高斯消去法。注意数值不稳定。 请参阅《数值食谱》第二章开头的警告。
Construct a matrix
Mwhose rows are the vectors and determine the rank ofM. If the rank ofMis less thanm(the number of vectors) then there is a linear dependence. In the algorithm to determine the rank ofMyou can stop the procedure as soon as you obtain one row of zeros, but running the algorithm to completion has the added bonanza of providing the dimension of the spanning set of the vectors. Oh, and the algorithm to determine the rank ofMis merely Gaussian elimination.Take care for numerical instability. See the warning at the beginning of chapter two in Numerical Recipes.
如果
m，你将不得不对它们进行一些操作（有多种可能性：高斯消除，正交化等，几乎任何可用于求解方程的变换都可以）并检查结果（例如，高斯消去=>零行或零列，正交化=>零向量，SVD =>零奇异数） 但是，请注意，对于程序员来说，这个问题是一个不好的问题，并且这个问题是程序要解决的坏问题。 这是因为每个线性相关的 n
If
m<n, you will have to do some operation on them (there are multiple possibilities: Gaussian elimination, orthogonalization, etc., almost any transformation which can be used for solving equations will do) and check the result (eg. Gaussian elimination => zero row or column, orthogonalization => zero vector, SVD => zero singular number)However, note that this question is a bad question for a programmer to ask, and this problem is a bad problem for a program to solve. That's because every linearly dependent set of
n<mvectors has a different set of linearly independent vectors nearby (eg. the problem is numerically unstable)这些天我一直在研究这个问题。
之前，我发现了一些关于高斯或高斯-乔丹消除的算法，但大多数算法只适用于方阵，而不适用于一般矩阵。
要申请通用矩阵，最好的答案之一可能是这样的：
http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB
您可以找到伪代码和各种语言的源代码。
对于我来说，我将Python源代码转换为C++，导致上面链接中提供的C++代码有些复杂并且不适合在我的模拟中实现。
希望这对你有帮助，祝你好运^^
I have been working on this problem these days.
Previously, I have found some algorithms regarding Gaussian or Gaussian-Jordan elimination, but most of those algorithms only apply to square matrix, not general matrix.
To apply for general matrix, one of the best answers might be this:
http://rosettacode.org/wiki/Reduced_row_echelon_form#MATLAB
You can find both pseudo-code and source code in various languages.
As for me, I transformed the Python source code to C++, causes the C++ code provided in the above link is somehow complex and inappropriate to implement in my simulation.
Hope this will help you, and good luck ^^
如果计算能力不是问题，最好的方法可能是找到矩阵的奇异值。 基本上，您需要找到
M'*M的特征值并查看最大与最小的比率。 如果比率不是很大，则向量是独立的。If computing power is not a problem, probably the best way is to find singular values of the matrix. Basically you need to find eigenvalues of
M'*Mand look at the ratio of the largest to the smallest. If the ratio is not very big, the vectors are independent.当放入大小为 mxn 的矩阵 M 时，检查 m 个行向量是否线性无关的另一种方法是计算
mxm 方阵的行列式。 当且仅当 M 有一些相关行时它才为零。 然而，高斯消除通常应该更快。
Another way to check that m row vectors are linearly independent, when put in a matrix M of size mxn, is to compute
i.e. the determinant of a mxm square matrix. It will be zero if and only if M has some dependent rows. However Gaussian elimination should be in general faster.
抱歉，我的错误...
上面链接中提供的源代码结果是不正确的，至少我测试过的python代码和我转换的C++代码并不总是生成正确的答案。 （虽然对于上面链接中的示例，结果是正确的:) -- )
要测试 python 代码，只需将
mtx替换为，返回的结果将如下所示：
尽管如此，我得到了摆脱这种情况的出路。 只是这次我将
rref函数的matalb源代码转换为C++。 您可以运行matlab并使用type rref命令来获取rref的源代码。请注意，如果您正在处理一些非常大的值或非常小的值，请确保使用 C++ 中的
long double数据类型。 否则，结果会被截断，与matlab结果不一致。我一直在 ns2 中进行大型模拟，所有观察到的结果都是合理的。
希望这对您和任何其他遇到此问题的人有所帮助......
Sorry man, my mistake...
The source code provided in the above link turns out to be incorrect, at least the python code I have tested and the C++ code I have transformed does not generates the right answer all the time. (while for the exmample in the above link, the result is correct :) -- )
To test the python code, simply replace the
mtxwithand the returned result would be like:
Nevertheless, I have got a way out of this. It's just this time I transformed the matalb source code of
rreffunction to C++. You can run matlab and use thetype rrefcommand to get the source code ofrref.Just notice that if you are working with some really large value or really small value, make sure use the
long doubledatatype in c++. Otherwise, the result will be truncated and inconsistent with the matlab result.I have been conducting large simulations in ns2, and all the observed results are sound.
hope this will help you and any other who have encontered the problem...
一种非常简单的方法（计算效率不是最高）是简单地删除随机行，直到
m=n，然后应用行列式技巧。m < n：删除行（使向量更短），直到矩阵为方阵，然后m = n：检查行列式是否为 0（如您所说）mn（向量的数量大于其长度）：它们是线性相关的（始终）。简而言之，原因是
mx n方程组的任何解也是nx n方程组的解（您正在尝试求解 <代码>Av=0）。 如需更好的解释，请参阅维基百科，其中比我解释得更好。A very simple way, that is not the most computationally efficient, is to simply remove random rows until
m=nand then apply the determinant trick.m < n: remove rows (make the vectors shorter) until the matrix is square, and thenm = n: check if the determinant is 0 (as you said)m < n(the number of vectors is greater than their length): they are linearly dependent (always).The reason, in short, is that any solution to the system of
m x nequations is also a solution to then x nsystem of equations (you're trying to solveAv=0). For a better explanation, see Wikipedia, which explains it better than I can.