Как найти линейно независимые строки из матрицы

Ответ 1

Во-первых, ваша 3-я строка линейно зависит от 1t и 2-й строки. Однако ваш 1-й и 4-й столбцы линейно зависимы.

Два метода, которые вы могли бы использовать:

собственные значения

Если одно собственное значение матрицы равно нулю, то соответствующий ему собственный вектор является линейно зависимым. Документация 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,:]

Неравенство Коши-Шварца

Чтобы проверить линейную зависимость векторов и выяснить, какие из них можно использовать неравенство Коши-Шварца. В принципе, если скалярное произведение векторов равно произведению нормы векторов, то векторы линейно зависимы. Вот пример для столбцов:

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'

Для проверки строк используется аналогичный подход.

Затем вы можете расширить это, чтобы проверить все комбинации векторов, но я думаю, что это решение сильно ухудшает размер.

Ответ 2

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

Что в основном говорит вам, что строки 0, 1 и 3 являются линейными независимо, тогда как строка 2 не является (это линейная комбинация строк 0 и 1).

Затем вы можете удалить эти строки с помощью нарезки:

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

Это также хорошо работает для прямоугольных (не только квадратичных) матриц.

Ответ 3

Я отредактировал код неравенства Коши-Шварца, который лучше масштабируется с измерением: входные данные - это матрица и ее размерность, а выходные данные - это новая прямоугольная матрица, которая содержит вдоль своих строк линейно независимые столбцы исходной матрицы. Это работает в предположении, что первый столбец никогда не равен нулю, но может быть легко обобщен для реализации этого случая. Еще одна вещь, которую я заметил, заключается в том, что 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

Ответ 4

Я знаю, что это было задано некоторое время назад, но вот очень простое решение. Для данного массива следующее находит набор линейно независимых векторов путем постепенного добавления вектора и проверки увеличения ранга:

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)

Ответ 5

Я интерпретирую проблему как нахождение строк, которые линейно независимы от других строк. Это эквивалентно нахождению строк, которые линейно зависят от других строк.

Исключение по Гауссу и обработка чисел, меньших порога, поскольку нули могут сделать это. Это быстрее, чем поиск собственных значений матрицы, проверка всех комбинаций строк с неравенством Коши-Шварца или разложение по сингулярным числам.

См.: https://math.stackexchange.com/info/1297437/using-gauss-elidity-to-check-for-linear-dependence

Проблема с числами с плавающей запятой:

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