2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Матрицы над полем Z_2
Сообщение14.10.2024, 10:16 


08/05/08
600
Есть некий прямоугольник, размером $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$ - оба нечетны, то матрица вырождена (в этом случае ,возможно, причина в том, что, если изначальный прямоугольник покрасить в шахматную раскраску, то все углы будут одного цвета)

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

 Профиль  
                  
 
 Re: Матрицы над полем Z_2
Сообщение14.10.2024, 17:53 
Заслуженный участник


07/08/23
1055
Давайте рассмотрим систему
$$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\}$ -- это необходимые и достаточные условия.

 Профиль  
                  
 
 Re: Матрицы над полем Z_2
Сообщение14.10.2024, 18:40 


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

 Профиль  
                  
 
 Re: Матрицы над полем Z_2
Сообщение14.10.2024, 22:20 
Заслуженный участник


07/08/23
1055
Никто не запрещает добавить эти уравнения при $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$.

 Профиль  
                  
 
 Re: Матрицы над полем Z_2
Сообщение15.10.2024, 01:22 


08/05/08
600
dgwuqtj в сообщении #1658573 писал(а):
Никто не запрещает добавить эти уравнения при $i = 0$

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

 Профиль  
                  
 
 Re: Матрицы над полем Z_2
Сообщение15.10.2024, 10:14 
Заслуженный участник


07/08/23
1055
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)$). Вроде её невырожденность уже можно исследовать руками.

 Профиль  
                  
 
 Re: Матрицы над полем Z_2
Сообщение15.10.2024, 11:59 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Матрицы над полем Z_2
Сообщение15.10.2024, 12:21 


08/05/08
600
dgwuqtjOk, спасибо

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group