如何从矩阵中找到线性无关的行

Question

如何从矩阵中识别出线性无关的行？例如，

第4行是独立的

Answer 1

首先，您的第 3 行与第 1t 行和第 2 行线性相关。但是，您的第一列和第四列是线性相关的。

您可以使用的两种方法：

特征值

如果矩阵的一个特征值为零，则其对应的特征向量是线性相关的。文档 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。基本上，如果向量的内积等于向量范数的乘积，则向量是线性相关的。以下是列的示例：

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'

测试行的方法类似。

然后你可以扩展它来测试向量的所有组合，但我想这个解决方案随着大小的扩展很糟糕。

Answer 2

我编辑了 Cauchy-Schwartz 不等式的代码，它随维度更好地缩放：输入是矩阵及其维度，而输出是一个新的矩形矩阵，它的行包含起始矩阵的线性独立列.这在假设第一列从不为空的情况下起作用，但也可以很容易地推广以实现这种情况。我观察到的另一件事是 1e-5 似乎是一个 "sloppy" 阈值，因为在这种情况下发现某些特定的病理向量是线性相关的：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

Answer 3

我知道不久前有人问过这个问题，但这是一个非常简单（尽管可能效率低下）的解决方案。给定一个数组，下面通过逐步添加一个向量并测试秩是否增加来找到一组线性无关的向量：

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)

Answer 4

与sympy you can find the linear independant rows using: 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]

这基本上告诉您第 0、1 和 3 行是线性独立的，而第 2 行不是（它是第 0 行和第 1 行的线性组合）。

然后您可以通过切片删除这些行：

>>> mat[inds]
array([[0, 1, 0, 0],
       [0, 0, 1, 0],
       [1, 0, 0, 1]])

这也适用于矩形（不仅适用于二次）矩阵。

Answer 5

我将问题解释为查找与其他行线性独立的行。这相当于找到与其他行线性相关的行。

高斯消元并将小于阈值的数字视为零可以做到这一点。它比查找矩阵的特征值、使用 Cauchy-Schwarz 不等式测试所有行的组合或奇异值分解更快。

参见： https://math.stackexchange.com/questions/1297437/using-gauss-elimination-to-check-for-linear-dependence

浮点数问题：

http://numpy-discussion.10968.n7.nabble.com/Reduced-row-echelon-form-td16486.html

Answer 6

关于以下讨论：

Find dependent rows/columns of a matrix using Matlab?

from sympy import *
A = Matrix([[1,1,1],[2,2,2],[1,7,5]])
print(A.nullspace())

很明显第一行和第二行是相乘的。如果我们执行上面的代码，我们会得到 [-1/3, -2/3, 1]。 null space 中零元素的索引显示独立性。但是为什么这里的第三个元素不为零呢？如果我们将 A 矩阵与空值 space 相乘，我们将得到一个零列向量。那怎么了？

我们要找的答案是A的转置的空值space

B = A.T
print(B.nullspace())

现在得到[-2, 1, 0]，说明第三行是独立的

这里有两个重要说明：

考虑我们是要检查行依赖还是列依赖依赖项。
注意矩阵的空值space不等于空值 space 该矩阵的转置，除非它是对称的。

如何从矩阵中找到线性无关的行

How to find linearly independent rows from a matrix

python

numpy

matrix

linear-algebra