Python 如何从矩阵中找到线性无关的行
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/28816627/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find linearly independent rows from a matrix
提问by SparkAndShine
How to identify the linearly independent rows from a matrix? For instance,
如何从矩阵中识别线性无关的行？例如，
The 4th rows is independent.
第 4 行是独立的。
采纳答案by hakanc
First, your 3rd row is linearly dependent with 1t and 2nd row. However, your 1st and 4th column are linearly dependent.
首先，您的第 3 行与 1t 和第 2 行线性相关。但是，您的第 1 列和第 4 列是线性相关的。
Two methods you could use:
您可以使用两种方法：
Eigenvalue
特征值
If one eigenvalue of the matrix is zero, its corresponding eigenvector is linearly dependent. The documentation eigstates the returned eigenvalues are repeated according to their multiplicity and not necessarily ordered. However, assuming the eigenvalues correspond to your row vectors, one method would be:
如果矩阵的一个特征值为零，则其对应的特征向量线性相关。文档eig说明返回的特征值根据它们的多重性重复并且不一定是有序的。但是，假设特征值对应于您的行向量，一种方法是：
import numpy as np
matrix = np.array(
[
[0, 1 ,0 ,0],
[0, 0, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 1]
])
lambdas, V = np.linalg.eig(matrix.T)
# The linearly dependent row vectors
print matrix[lambdas == 0,:]
Cauchy-Schwarz inequality
柯西-施瓦茨不等式
To test linear dependence of vectors and figure out which ones, you could use the Cauchy-Schwarz inequality. Basically, if the inner product of the vectors is equal to the product of the norm of the vectors, the vectors are linearly dependent. Here is an example for the columns:
要测试向量的线性相关性并找出哪些，您可以使用Cauchy-Schwarz 不等式。基本上，如果向量的内积等于向量范数的乘积，则向量线性相关。以下是列的示例：
import numpy as np
matrix = np.array(
[
[0, 1 ,0 ,0],
[0, 0, 1, 0],
[0, 1, 1, 0],
[1, 0, 0, 1]
])
print np.linalg.det(matrix)
for i in range(matrix.shape[0]):
for j in range(matrix.shape[0]):
if i != j:
inner_product = np.inner(
matrix[:,i],
matrix[:,j]
)
norm_i = np.linalg.norm(matrix[:,i])
norm_j = np.linalg.norm(matrix[:,j])
print 'I: ', matrix[:,i]
print 'J: ', matrix[:,j]
print 'Prod: ', inner_product
print 'Norm i: ', norm_i
print 'Norm j: ', norm_j
if np.abs(inner_product - norm_j * norm_i) < 1E-5:
print 'Dependent'
else:
print 'Independent'
To test the rows is a similar approach.
测试行是一种类似的方法。
Then you could extend this to test all combinations of vectors, but I imagine this solution scale badly with size.
然后你可以扩展它来测试向量的所有组合，但我认为这个解决方案会随着大小而严重扩展。
回答by Simone Bolognini
I edited the code for Cauchy-Schwartz inequality which scales better with dimension: the inputs are the matrix and its dimension, while the output is a new rectangular matrix which contains along its rows the linearly independent columns of the starting matrix. This works in the assumption that the first column in never null, but can be readily generalized in order to implement this case too. Another thing that I observed is that 1e-5 seems to be a "sloppy" threshold, since some particular pathologic vectors were found to be linearly dependent in that case: 1e-4 doesn't give me the same problems. I hope this could be of some help: it was pretty difficult for me to find a really working routine to extract li vectors, and so I'm willing to share mine. If you find some bug, please report them!!
我编辑了 Cauchy-Schwartz 不等式的代码，它随着维度的扩展更好：输入是矩阵及其维度，而输出是一个新的矩形矩阵，它的行包含起始矩阵的线性独立列。这在假设第一列永远不会为空的情况下起作用，但也可以很容易地推广以实现这种情况。我观察到的另一件事是 1e-5 似乎是一个“草率”阈值，因为在这种情况下发现某些特定的病理向量是线性相关的：1e-4 不会给我同样的问题。我希望这会有所帮助：我很难找到一个真正有效的例程来提取 li 向量，所以我愿意分享我的。如果您发现一些错误，请报告他们！！
from numpy import dot, zeros
from numpy.linalg import matrix_rank, norm
def find_li_vectors(dim, R):
r = matrix_rank(R)
index = zeros( r ) #this will save the positions of the li columns in the matrix
counter = 0
index[0] = 0 #without loss of generality we pick the first column as linearly independent
j = 0 #therefore the second index is simply 0
for i in range(R.shape[0]): #loop over the columns
if i != j: #if the two columns are not the same
inner_product = dot( R[:,i], R[:,j] ) #compute the scalar product
norm_i = norm(R[:,i]) #compute norms
norm_j = norm(R[:,j])
#inner product and the product of the norms are equal only if the two vectors are parallel
#therefore we are looking for the ones which exhibit a difference which is bigger than a threshold
if absolute(inner_product - norm_j * norm_i) > 1e-4:
counter += 1 #counter is incremented
index[counter] = i #index is saved
j = i #j is refreshed
#do not forget to refresh j: otherwise you would compute only the vectors li with the first column!!
R_independent = zeros((r, dim))
i = 0
#now save everything in a new matrix
while( i < r ):
R_independent[i,:] = R[index[i],:]
i += 1
return R_independent
回答by Couchy311
I know this was asked a while ago, but here is a very simple (although probably inefficient) solution. Given an array, the following finds a set of linearly independent vectors by progressively adding a vector and testing if the rank has increased:
我知道这是不久前被问到的，但这是一个非常简单（虽然可能效率低下）的解决方案。给定一个数组，下面通过逐步添加一个向量并测试秩是否增加来找到一组线性无关的向量：
from numpy.linalg import matrix_rank
def LI_vecs(dim,M):
LI=[M[0]]
for i in range(dim):
tmp=[]
for r in LI:
tmp.append(r)
tmp.append(M[i]) #set tmp=LI+[M[i]]
if matrix_rank(tmp)>len(LI): #test if M[i] is linearly independent from all (row) vectors in LI
LI.append(M[i]) #note that matrix_rank does not need to take in a square matrix
return LI #return set of linearly independent (row) vectors
#Example
mat=[[1,2,3,4],[4,5,6,7],[5,7,9,11],[2,4,6,8]]
LI_vecs(4,mat)
回答by MSeifert
With sympyyou can find the linear independant rows using: sympy.Matrix.rref:
使用sympy，您可以使用以下方法找到线性独立行sympy.Matrix.rref：
>>> import sympy
>>> import numpy as np
>>> mat = np.array([[0,1,0,0],[0,0,1,0],[0,1,1,0],[1,0,0,1]]) # your matrix
>>> _, inds = sympy.Matrix(mat).T.rref() # to check the rows you need to transpose!
>>> inds
[0, 1, 3]
Which basically tells you the rows 0, 1 and 3 are linear independant while row 2 isn't (it's a linear combination of row 0 and 1).
这基本上告诉您第 0、1 和 3 行是线性独立的，而第 2 行不是（它是第 0 行和第 1 行的线性组合）。
Then you could remove these rows with slicing:
然后你可以通过切片删除这些行：
>>> mat[inds]
array([[0, 1, 0, 0],
[0, 0, 1, 0],
[1, 0, 0, 1]])
This also works well for rectangular (not only for quadratic) matrices.
这也适用于矩形（不仅适用于二次）矩阵。
回答by R zu
I interpret the problem as finding rows that are linearly independent from other rows. That is equivalent to finding rows that are linearly dependent on other rows.
我将问题解释为查找与其他行线性无关的行。这等效于查找线性依赖于其他行的行。
Gaussian elimination and treat numbers smaller than a threshold as zeros can do that. It is faster than finding eigenvalues of a matrix, testing all combinations of rows with Cauchy-Schwarz inequality, or singular value decomposition.
高斯消除并将小于阈值的数字视为零可以做到这一点。它比查找矩阵的特征值、使用 Cauchy-Schwarz 不等式测试所有行组合或奇异值分解更快。
请参阅：https: //math.stackexchange.com/questions/1297437/using-gauss-elimination-to-check-for-linear-dependence
Problem with floating point numbers:
浮点数问题：
http://numpy-discussion.10968.n7.nabble.com/Reduced-row-echelon-form-td16486.html
http://numpy-discussion.10968.n7.nabble.com/Reduced-row-echelon-form-td16486.html
