Матрицы над полем Z_2

[ET]

Есть некий прямоугольник, размером $n$ на $m$ (разделенный на единичные квадратики)

Для каждого его квадратика существует неизвестная $x_{i,j}$ из поля $Z_2$ (имею в виду кольцо вычетов по модулю 2, которое является полем, иногда его по-другому видел обозначения) и уравнение вида
$x_{i-1,j}+x_{i+1,j}+x_{i,j-1}+x_{i,j+1}=$ чему-нибудь
(вектор-столбец меня мало интересует, меня интересует матрица)

, если все переменные существуют (то есть, если $i-1=0$, то без слагаемого $x_{i-1,j}$, если $j+1>m$ , то без слагаемого $x_{i,j+1}$, итд)

То есть для каждого $n$ и $m$ имеем квадратную матрицу над полем $Z_2$ размера $mn$

Для таких матриц меня интересует
1. Вырожденность-невырожденность (как частный случай вопроса номер 2)
2. Дефект. То есть размер матрицы минус размерность ядра. То есть размерность пространства решений
3. Вот, не знаю, как выразиться. Однозначно вычисляемые неизвестные. Возможно, это базисные векторы, ортогональные ядру? Короче, если подставить такой ветор-столбец, чтобы система была совместна, то, в случае вырожденной матрицы, некоторые неизвестные могут принимать разные значения, но некоторые иногда определяются однозначно. Вот такие неизвестные (и по хорошему быстрый метод их вычисления) меня и интересуют.

Что я знаю:
Если $m=n$ то, даже могу доказать, что матрица будет вырождена. Возможно, еще в некоторых случаях докажу, возможно , еще и в случаях $m=n+k(n+1)$

Если $m \neq n$ То могу указать такую предвычисляемую неизвестную, как $x_{n,n+1}$ и симметричные ей

Все остальное знаю только потому, что есть решалка таких систем и без доказательств, то есть проверено на некоторых числах. Например, что дефект матрицы ,соотвествующей квадрату, равен стороне этого квадрата и у таких матриц однозначно вычисляемых неизвестных нет. Или что дефекты матриц, соотвествующих прямоугольникам $n \times m$ и $n \times (m+k(n+1))$ равны или что если и $n$ и $m$ - оба нечетны, то матрица вырождена (в этом случае ,возможно, причина в том, что, если изначальный прямоугольник покрасить в шахматную раскраску, то все углы будут одного цвета)

Меня интересует: что еще можно сказать на эту тему?

[dgwuqtj]

Давайте рассмотрим систему

$$x_{i - 1, j} + x_{i + 1, j} + x_{i, j - 1} + x_{i, j + 1} = y_{i, j},$$

где $i, j$ пробегают все целые числа, $x_{i, j} = 0$ при $i \notin \{1, \ldots, n\}$ или $j \notin \{1, \ldots, m\}$. Тогда $y_{i, j} = 0$, кроме случаев $0 \leq i \leq n + 1$, $1 \leq j \leq m$ и $1 \leq i \leq n$, $0 \leq j \leq m + 1$. Из этой системы все $x_{i, j}$ находятся однозначно, зная $x_{i', j'}$ с $i' < i$ (при помощи уравнения для $y_{i - 1, j}$, а также пользуясь $x_{i, j} = 0$ при $i \ll 0$). А именно,

$$x_{i, j} = y_{i - 1, j} + y_{i - 2, j - 1} + y_{i - 2, j + 1} + y_{i - 3, j - 2} + y_{i - 3, j} + y_{i - 3, j + 2} + \ldots$$

Вот и получается, что $x_{i, j} = 0$ (как уравнения на $y_{i', j'}$) при $i > n$ или $i \geq 1$, $j \notin \{1, \ldots, m\}$ -- это необходимые и достаточные условия.

[ET]

dgwuqtj
Это не эквивалентная переформулировка. потому что таких уравнений для $i=0$ у меня нет
Но, да, если известны все $x_{i,1}$ , то остальное вычисляется однозначно. Из чего, например, следует, что дефект матрицы не больше меньшей стороны того прямоугольника

[dgwuqtj]

Никто не запрещает добавить эти уравнения при $i = 0$, просто $y_{0, j}$ выбрать какие надо. Но это просто идея, как можно попробовать упростить задачу.

Можно ещё написать явные выражения $x_{i, j}$ через $x_{k, 1}$, зная $y_{u, v} = x_{u - 1, v} + x_{u + 1, v} + x_{u, v - 1} + x_{u, v + 1}$ при $u < i$. Удобно считать, что $n \leq m$ и что $y_{0, j} = x_{1, j}$. Получается так:

$$ x_{i, j} = \sum_{u = 1}^i \sum_{v = \max(0, u - j)}^{\min(u - 1, m - j)} y_{i - u, j - u + 1 + 2 v}. $$

И ваши первые два вопроса сводятся к тому, как $y_{n, j}$ выражаются через $y_{i, j}$ с $i < n$. Это равносильно тому, что выражение выше обнуляется, если в него формально подставить $i = n + 1$, для всех $1 \leq j \leq m$. Причём эти $m$ уравнений линейно независимы, так как в них входят $y_{n, j}$, но не входят $y_{n, k}$ при $k \neq j$.

[ET]

dgwuqtj в сообщении #1658573 писал(а):

Никто не запрещает добавить эти уравнения при $i = 0$

Не, ну что значит никто не запрещает? Эти уравнения сводятся к утверждениям $x_{i,1}=a_i$
, а $x_{i,1}$ - это то, что надо найти. И, если неправильно прописать эти $a_i$, система может стать несовместной, даже, если до этого она была совместной. А вопрос-то в решении этой системы
То есть вот есть система линейных уравнений - сколько уравнений, столько неизвестных. Никто не запрещает добавить новые? Ну, можно, но откуда их взять?

[dgwuqtj]

ET в сообщении #1658587 писал(а):

Ну, можно, но откуда их взять?

Так я написал, откуда. Получится другая система, просто тесно связанная с исходной.

Если вернуться к явным формулам для $x_{i, j}$, то получатся уравнения

$$ \sum_{v = \max(0, n + 1 - j)}^{\min(n, m - j)} x_{1, j - n + 2 v} = \sum_{u = 1}^n \sum_{v = \max(0, n + 1 - u - j)}^{\min(n - u, m - j)} y_{u, u + j - n + 2 v}. $$

Всего $m$ уравнений и $m$ неизвестных $x_{1, j}$. При $1 \leq n \leq 4$, $m = 4$ матрицы коэффициентов — это

$$ \Bigl(\begin{smallmatrix}0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0\end{smallmatrix}\Bigr),\quad \Bigl(\begin{smallmatrix}0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0\end{smallmatrix}\Bigr),\quad \Bigl(\begin{smallmatrix}0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0\end{smallmatrix}\Bigr),\quad \Bigl(\begin{smallmatrix}0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0\end{smallmatrix}\Bigr). $$

В общем случае при $n = m$ матрица нулевая, а при $n < m$ единички в этой матрице заполняют позиции одной чётности в прямоугольнике под углом $45^\circ$, вписанном в матрицу (начиная с вершин $(1, n + 1)$, $(n + 1, 1)$, $(m - n, m)$, $(m, m - n)$). Вроде её невырожденность уже можно исследовать руками.

[dgwuqtj]

У меня получилось, что система невырожденная тогда и только тогда, когда $n + 1$ и $m + 1$ взаимно просты.

[ET]

dgwuqtjOk, спасибо