Как решить линейное прямоугольное матричное уравнение по модулю 2? ⇐ Python

[Anonymous]

Я пытаюсь решить линейное матричное уравнение AX = B с помощью Python, где A,B,X — двоичные матрицы, т.е. над GF(2):

Код: Выделить всё

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

Я знаю, что A имеет ранг 11 и форму (11,12). т. е. A — широкая прямоугольная матрица с большим количеством переменных, чем уравнений. Таким образом, скорее всего, существует свободная переменная и параметризованное решение.
RHS, B в уравнении имеет вид:

Код: Выделить всё

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

Который, как я также могу вычислить, имеет ранг 11.
Я хочу найти линейные комбинации строк в A, которые дают B. В идеале включены замены строк .

• Обычные методы Python (

  Код: Выделить всё

  np.linalg.solve(A,B)

  ) нельзя использовать напрямую, поскольку A и B не являются квадратными матрицами.
• Следующим я попробовал решатель numpy в Галуа . Поскольку это конечные матрицы полей, я использую первый вариант Галуа, чтобы обернуть их в объекты mod 2,

  Код: Выделить всё

  import galois     GF = galois.GF(2)    A1 = GF(A)

• Но проблема с неквадратной матрицей остается: заполнение избыточными строками делает матрицу сингулярной, а линейную систему неразрешимой с помощью np.linalg.solve или scipy.linalg.solve.
• Далее я получил эшелон с сокращенным количеством строк форма, рассчитанная с помощью A1.row_reduce() для объекта Галуа

Код: Выделить всё

A1.row_reduce() = GF([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1]], order=2)

(Из вышеизложенного легко увидеть сумму последовательных строк, чтобы получить RHS, т.е. строка 1 + строка 2 с сокращением строк дает B), но функция galois rref не помогает мне прийти в X или последовательности явных операций для преобразования A в B. Я знаю, что решение существует из-за равенства рангов и сокращенной формы строк, я просто не знаю, как найти X.
tldr; как решить широкую прямоугольную (т.е. неквадратную) систему уравнений с матрицами по модулю 2, используя Python?

Подробнее здесь: https://stackoverflow.com/questions/787 ... over-mod-2