Эффективная проверка, если три бинарных вектора линейно независимы над конечным полем
Мне даны три двоичных вектора v1, v2, v3, представленных в моей программе как unsigned int, и конечное поле F, которое также является набором двоичных векторов. Мне нужно проверить, являются ли векторы линейно независимыми, то есть в f нет f1, f2, так что f1 * v1 + f2 * v2 = v3.
Непосредственное решение для перебора — перебрать поле и проверить все возможные линейные комбинации.
Существует ли более эффективный алгоритм?
Спасибо.
UPD: Я бы хотел подчеркнуть два момента: 1) элементы поля являются векторами, а не скалярами. Следовательно, произведение элемента поля f1 и заданного вектора vi является точечным произведением. Таким образом, устранение по Гауссу не работает (если я что-то не упускаю); 2) поле конечно, поэтому если я обнаружу, что f1 * v1 + f2 * v2 = v3 для некоторого f1, f2, это не означает, что f1, f2 принадлежат F.
Решение
Если векторы находятся в г ^ 2, то они автоматически зависят, потому что когда мы создадим их матрицу и приведем ее к эшелонированной форме, будет по крайней мере одна свободная переменная (в данном случае только одна).
Если векторы находятся в R ^ 3, то из них можно составить матрицу i. 2d массив, а затем вы можете взять определитель этой матрицы. Если определитель равен 0, то векторы линейно зависимы, иначе нет.
Если векторы находятся в R ^ 4, R ^ 5 и т. Д., То подходящим способом является приведение матрицы в форму эшелона.
Другие решения
Для любого конечного набора M векторов, определенных в пространстве размерности N, они линейно независимы, если ранг матрицы MxN, построенной путем суммирования этих векторов строка за строкой, имеет ранг, равный M.
Что касается численно устойчивых вычислений с использованием линейной алгебры, то разложение по сингулярным числам обычно это путь, и существует множество реализаций, доступных там. Ключевым моментом в этом контексте является понимание того, что ранг матрицы равен числу ее ненулевых единичных значений. Однако следует отметить, что из-за приближений с плавающей запятой, конечная точность должна быть выбрана, чтобы решить, является ли значение фактически нулевым.
Ваш вопрос упоминает, что ваши векторы определены в наборе целых чисел, и это, безусловно, может быть использовано для преодоления конечной точности вычислений с плавающей запятой, но я не знаю, как. Может быть, кто-то может помочь нам?
Гауссово исключение работает, если вы делаете это внутри конечного поля.
Для двоичного файла это должно быть довольно просто, потому что обратный элемент тривиален.
Для больших конечных полей вам нужно как-то найти обратные элементы, что может превратиться в отдельную проблему.