Существование решения для линейной системы mod 2

Dec 09 2020

Позволять $A$ - (кососимметричная) матрица над $\mathbb{Z}/2$. (На самом деле я бы взял$A$ как матрица связи ориентированной обрамленной связи в $S^3$или матрица, представляющая форму пересечения на замкнутом гладком 4-многообразии. Следующее утверждение, однако, кажется в целом справедливым.) Меня интересует следующая линейная система над$\mathbb{Z}/2$, $$a_{i1}x_1+a_{i2}x_2\cdots+a_{in}x_n=a_{ii},\quad i=1,\cdots,n.$$

Известно, что в этой системе всегда есть решение. (см. «Лекции Савельева по топологии трехмерных многообразий» .) Но я не могу понять, почему это верно, если только$A$ неособен по $\mathbb{Z}/2$. Есть ли общий метод работы с такими линейными системами?

Ответы

1 JyrkiLahtonen Dec 10 2020 at 04:21

Это правда, но это немного сложно. Идея состоит в том, чтобы просто написать матрицу в виде$$ A=BB^T $$ таким образом, чтобы пространство столбцов $B$ равен $A$. Все столбцы$A$ линейные комбинации столбцов $B$, но мне не ясно, как добиться обратного включения (это явно не верно для всех вариантов выбора $B$).

Итак, в настоящее время я не могу написать полностью автономное доказательство, мне нужно сослаться на две статьи:

  • А. Лемпель, Факторизация матрицы над$GF(2)$ и трассово-ортогональные базисы $GF(2^m)$, SIAM J. Comput., Т. 4, стр. 175-186, июнь 1975 г.
  • Г. Серусси, А. Лемпель, Максимальное правдоподобное декодирование некоторых кодов Рида-Мюллера , IEEE Transactions по теории информации, Vol. IT-29, NO. 3 мая 1983 г.

IIRC нужен только первый. Я включаю второе, потому что первое я нашел, прочитав его.

Проблема, которую Лемпель (известный как Лемпель-Зив) решает в первой статье, заключается в следующем. Он хочет написать данную симметричную$n\times n$ матрица $A$ над $\Bbb{Z}_2$ в виде $A=BB^T$максимально эффективно. То есть он хочет минимизировать количество столбцов$m$ из $B$. Его ответ таков

Как обычно $m$ равно званию $r(A)$ из $A$. Исключение составляют случаи, когда диагональ$A$ все нули, когда $m=1+r(A)$ лучшее, что мы можем сделать.

Мы можем применить результат Лемпеля для решения этого вопроса следующим образом.

  1. Если диагональ $A$все нули, утверждение тривиально. Мы можем использовать$x_i=0$ для всех $i$.
  2. Если это не так, количество столбцов $B$ равен рангу $A$. Так как$A=BB^T$ пространство столбцов $A$ тогда равно $B$.
  3. Итак, достаточно показать, что диагональ $A$ содержится в пространстве столбцов $B$.
  4. Уравнение $A=BB^T$ Значит это $a_{ii}$ равно внутреннему продукту $(B_i,B_i)$ из $i$й ряд $B_i$ из $B$ с собой.
  5. Но $B_i$ двоичный, поэтому $(B_i,B_i)$ это просто сумма записей этого $i$-я строка как $x^2=x$ для всех $x\in\Bbb{Z}_2$.
  6. Следовательно, диагональ $A$ это сумма столбцов $B$.
  7. Следовательно, диагональ $A$ также находится в пространстве столбцов $A$ и мы закончили.

Это кажется излишне беспорядочным. Идея использования$A=BB^T$пришло ко мне интуитивно. Я подсчитал несколько примеров и заметил, что столбцы$B$суммируйте по диагонали. Время лампочки!

QiaochuYuan Dec 09 2020 at 14:15

В $\mathbb{Z}_2$ форма пересечения на замкнутой гладкой $4$-многообразие всегда невырождено двойственностью Пуанкаре.