Линейная матрица независимости

Question

Предположим, что у нас есть матрица A размером m на n с рангом m и набор K⊆ {1..n} такой, что столбцы A, индексированные K, линейно независимы. Теперь мы хотим расширить K и найти множество L так, чтобы k⊆L и столбцы, индексированные L, тоже были линейно независимы.

Один из способов сделать это - начать добавлять индексы столбцов в K и проверить, являются ли новые наборы линейно независимыми или нет, например, используя метод исключения Гаусса. Но есть ли лучший способ, чтобы мне не нужно было проверять каждый добавленный индекс.

Спасибо

Answer 1

Только потому, что никто еще официально не ответил ... ты не можешь просто использовать QR?

Q, R = qr(A)

QR-факторизация находит ортонормированную матрицу Q и верхнюю треугольную матрицу R такую, что A = QR. Он реализует алгоритм Грамма-Шмидта для нахождения ортонормированного базиса для A.

Столбцы Q ортонормированы, следовательно, линейно независимы. И первые n столбцов Q охватывают пространство столбцов A. Поэтому Q должен дать вам то, что вы хотите.