0

Нужно найти линейно зависимые векторы в матрице произвольного размера. В примере такими векторами есть второй и четвертый.

import numpy as np

matrix = np.array([
    [1, 0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0],
    [1, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 0, 0]
    ])

Пробовал банальным перебором, но получилось очень громоздко и криво, поэтому даже не стал дописывать. Надеюсь, есть способ проще. Еще пытался использовать np.linalg.eig, но не могу разобраться как ее правильно использовать.

1

2 ответа 2

2

По идее, надо смотреть матрицу корреляции, которую даёт np.corrcoef, но как её правильно интерпретировать я сходу не соображу. Хотя и вижу единички не на диагонали:

print(np.corrcoef(matrix))

Вывод:

[[ 1.          0.31622777 -0.25        0.31622777]
 [ 0.31622777  1.         -0.31622777  1.        ]
 [-0.25       -0.31622777  1.         -0.31622777]
 [ 0.31622777  1.         -0.31622777  1.        ]]

Подумал ещё, сочинил вот такого монстра:

print(np.nonzero(np.isclose(np.abs(np.corrcoef(matrix) - np.eye(matrix.shape[0])), 1.)))

Пошагово:

  • corrcoef - берём матрицу корреляции
  • вычитаем eye - убираем единицы с диагонали (корреляция векторов с самими собой нас не интересует)
  • abs - берём абсолютное значение коэффициентов корреляции (отрицательная корреляция - тоже корреляция)
  • isclose - проверяем на близость получившихся коэффициентов к 1 (точное равенство может не всегда соблюдаться для чисел с плавающей точкой)
  • nonzero - получаем индексы найденных линейно коррелирующих векторов

На выходе:

(array([1, 3]), array([3, 1]))

Интерпретировать можно так (учитывая, что индексация в Питоне идёт с 0, т.е. в вашем случае имеем векторы под индексом 0, 1, 2, 3): вектор 1 линейно коррелирует с вектором 3; и наоборот: вектор 3 линейно коррелирует с вектором 1.

7
  • спасибо большое! это работает, пускай и не для всех случаев (иногда пропускает линейные векторы и ищет просто одинаковые)
    – Ted Mosby
    25 окт 2020 в 6:56
  • @TedMosby Обновил подсчёт. Теперь правильно ищет и для отрицательной корреляции, и не требует корреляции ровно 1.0, что для чисел с плавающей точкой может не всегда срабатывать
    – CrazyElf
    25 окт 2020 в 7:49
  • @TedMosby А можете привести примеры, когда не срабатывает? Что там в матрице корреляции, интересно.
    – CrazyElf
    25 окт 2020 в 7:51
  • Возможно причина в том, что оно работает только на два вектора? А в матрице могут больше двух векторов быть зависимыми. Сейчас наведу пример в отдельном посте
    – Ted Mosby
    25 окт 2020 в 8:55
  • У меня программа генерирует эту матрицу в цикле, с каждой итерацией матрица увеличивается по определенным формулам. Суть в том, что когда получается вот такая матрица: matrix = np.array([ [1, 1, 0, 0, 1, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 1, 0, 0], [1, 1, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 1, 0, 0, 0, 0], [1, 0, 1, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 1], [1, 1, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 0, 0, 0], [1, 0, 0, 0, 0, 1, 0, 0, 0] ])
    – Ted Mosby
    25 окт 2020 в 9:03
0

Если кому-то пригодится, решил проблему таким образом:

from itertools import combinations
from numpy import sum as npsum

def combs(matr):
    arr = []
    for k in range(2, len(matr) + 1):
        rows = combinations(matr,k)
        indices = list(combinations(range(len(matr)), k))
        for i, j in enumerate(rows):
            if sum(npsum(j, axis=0) % 2) == 0: 
                arr.append(indices[i])
    return arr

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.