Эффективный подход для выделения линейно-независимых столбцо

[GreenEkatherine]

Добрый день! Столкнулась с проблемой при написании функции, которая отбрасывает линейно зависимые столбцы матриц (матрица двоичная и разреженная, но это уже совсем другая история). Из того, что я вспомнила из студенческого курса и нашла в гугле – вариант в принципе один: применить метод Гаусса. Дальше видимо нужно смотреть, какие столбцы занулятся и выкинуть их из исходной матрицы. Подскажите, хорош ли такой подход из соотношения простота/быстродействие? И какие есть альтернативы?

[mihailm]

Приводите матрицу к ступенчатому виду элементарными преобразованиями строк, там где уголки, те столбцы можно взять за линейно независимые

[arseniiv]

GreenEkatherine в сообщении #884181 писал(а):

Подскажите, хорош ли такой подход из соотношения простота/быстродействие? И какие есть альтернативы?

Не знаю, хорош или нет, но его надо будет обязательно специализировать под данные, заметив, что умножать и вычитать не нужно, а нужен только xor. (Это на всякий случай — такая идея должна и сама приходить. )

[GreenEkatherine]

mihailm в сообщении #884192 писал(а):

Приводите матрицу к ступенчатому виду элементарными преобразованиями строк, там где уголки, те столбцы можно взять за линейно независимые

Мне кажется, навскидку здесь не сработает (у второго столбца нет "уголка", но он линейно независим):

10010
10001
1010
100

[Otta]

Это нулевой-то столбец?

[GreenEkatherine]

Otta в сообщении #884856 писал(а):

Это нулевой-то столбец?

Ой, исправляюсь. По привычке смотрела на строки.

Вот здесь:

10010
1000
1001
100

То есть "привести к ступенчатому виду" = использовать метод Гаусса, и по углам определять? Я не поняла изначально отличия от предложенного мной подхода.

[patzer2097]

GreenEkatherine в сообщении #884181 писал(а):

Столкнулась с проблемой при написании функции, которая отбрасывает линейно зависимые столбцы матриц

Вы хотя бы понимаете, что линейно зависимыми бывают не столбцы, а наборы столбцов? Если да, то сформулируйте задачу нормально

[GreenEkatherine]

patzer2097
нормально формулирую задачу: оставить в матрице множество линейно независимых столбцов. Называя столбец линейно независимым, я подразумевала, что он относится к линейно независимому подмножеству.

[Joker_vD]

GreenEkatherine
Непустое? А из одного столбца сгодится? Или вы все-таки хотите максимальную линейно независимую подсистему?

[patzer2097]

GreenEkatherine в сообщении #884901 писал(а):

нормально формулирую задачу: оставить в матрице множество линейно независимых столбцов. Называя столбец линейно независимым, я подразумевала, что он относится к линейно независимому подмножеству.

понятно. но в такой формулировке Вам достаточно удалить нулевые столбцы, а все остальные оставить. после того, как столбцы будут удалены, советую начать читать учебник

[GreenEkatherine]

Действительно, проще привязываться к формулировке и отсылать читать учебники.

[arseniiv]

А почему вы думаете, что правильная формулировка получается из вашей единственным образом? Может, из неё исправлением можно несколько разных получить? Задача правильно сформулировать — ваша, тем более что осталось всего ничего: просто скажите,

Joker_vD в сообщении #884920 писал(а):

вы все-таки хотите максимальную линейно независимую подсистему

или любую. (Если любую, берите первый встреченный ненулевой столбец, вот и независимая система.)

[mihailm]

GreenEkatherine в сообщении #884853 писал(а):

...Мне кажется, навскидку здесь не сработает (у второго столбца нет "уголка", но он линейно независим):
10010
10001
1010
100

Точнее у такой
10010
10001
01010
00100
Но ведь она не приведена к ступенчатому виду. Избавьтесь от первой единички во второй строке

[GreenEkatherine]

arseniiv
Да, максимальную.

-- 07.07.2014, 17:46 --

mihailm
Поняла, спасибо.

[patzer2097]

GreenEkatherine в сообщении #884949 писал(а):

Действительно, проще привязываться к формулировке и отсылать читать учебники.

ок, не хотите - не читайте, больше не отсылаю, извините