Биекция между словами и матрицами

[alcoholist]

situs в сообщении #1380057 писал(а):

А если ранг не 2.

для доказательства утверждения это не нужно

-- Ср мар 06, 2019 01:46:59 --

но $abacdcbd$

[situs]

alcoholist в сообщении #1380064 писал(а):

для доказательства утверждения это не нужно

Че то я ничего не понимаю. Для какого доказательства, какого утверждения?

alcoholist в сообщении #1380064 писал(а):

$abacdcbd$

Верно.

[alcoholist]

situs в сообщении #1380103 писал(а):

Для какого доказательства, какого утверждения?

единственного утверждения, которое вы привели

-- Ср мар 06, 2019 12:21:45 --

situs в сообщении #1379813 писал(а):

Утверждение. Слово является хорошим тогда и только тогда, когда ранг его матрицы $\leqslant 2$.

[situs]

Так я ж пишу сейчас не о доказательстве этого утверждения, а о том, как построить слово по любой квадратной матрице над $ \mathbb{Z}_2$ c нулевой диагональю. То есть об описании способа построения.

[alcoholist]

так докажите сначала утверждение, зачем перескакивать с одного на другое

-- Ср мар 06, 2019 12:38:23 --

научитесь записывать слова для матриц ранга 2 для начала

[situs]

alcoholist в сообщении #1380112 писал(а):

так докажите сначала утверждение, зачем перескакивать с одного на другое

Это нетрудно.

Доказательство. Рассмотрим произвольное допустимое слово $w$. Пусть $w$ хорошее. Тогда $w$ редуцируется до одного из слов $(), (xyxy), (xyzxyz)$. Матрицы этих слов имеют ранг не более 2.
Теперь обратно. Пусть $w$ - допустимое слово на алфавите любой длины $n$ и предположим, что ранг его матрицы не более 2. Случай $n < 2$ тривиален. Пусть $n \geqslant 2$. Тогда матрица слова имеет вид либо $\left( \begin{smallmatrix} 0 & 1\\ 1 & 0 \end{smallmatrix} \right)$ в случае $n = 2$ , либо является матрицей любого порядка $n > 2$, которая элементарными преобразованиями - сложением строк (столбцов) по модулю 2, удалением нулевых строк (столбцов) может быть преобразована к $\left( \begin{smallmatrix} 0 & 1\\ 1 & 0 \end{smallmatrix} \right)$, что соответствует хорошему слову. Ранг при этом сохраняется. Следовательно слово $w$ является хорошим.

-- 06.03.2019, 13:16 --

alcoholist в сообщении #1380112 писал(а):

научитесь записывать слова для матриц ранга 2 для начала

?

[alcoholist]

situs в сообщении #1380119 писал(а):

Тогда $w$ редуцируется до одного из слов $(), (xyxy), (xyzxyz)$. Матрицы этих слов имеют ранг не более 2.

почему при редуции слова ранг соотв. матриц не меняется?

-- Ср мар 06, 2019 13:26:04 --



-- Ср мар 06, 2019 13:26:09 --

situs в сообщении #1380000 писал(а):

Как по матрице построить слово?

-- Ср мар 06, 2019 13:27:06 --

alcoholist в сообщении #1380112 писал(а):

научитесь записывать слова для матриц ранга 2 для начала

[situs]

alcoholist в сообщении #1380125 писал(а):

почему при редуции слова ранг соотв. матриц не меняется?

Сохранение ранга матрицы следует из того, что при преобразовании редукции в матрице удаляется нулевая строка и нулевой столбец, т.е. линейно зависимая строка и линейно зависимый столбец.

-- 06.03.2019, 13:34 --

alcoholist в сообщении #1380125 писал(а):

научитесь записывать слова для матриц ранга 2 для начала

Вот не понимаю и всё

[alcoholist]

situs в сообщении #1380126 писал(а):

при преобразовании редукции в матрице удаляется нулевая строка и нулевой столбец, т.е. линейно зависимая строка и линейно зависимый столбец.

не всегдa

situs в сообщении #1380126 писал(а):

Вот не понимаю и всё

тогдa нет д-вa

[situs]

alcoholist в сообщении #1380131 писал(а):

тогдa нет д-вa

То есть я не понимаю, что от меня требуется сделать. Не могли бы сказать как-то по другому или пример?

[alcoholist]

Вы сформулировали утверждение. Для его доказательства в части «только тогда» надо уметь строить слово по матрице.

-- Ср мар 06, 2019 14:58:04 --

рaнгa <=2

[situs]

alcoholist в сообщении #1380137 писал(а):

Для его доказательства в части «только тогда» надо уметь строить слово по матрице.

Пусть у нас есть $n \times n$ матрица $\mathbf{M}=(m_{ij})$. Возьмем любой алфавит $A = \{a_1, a_2, \dots, a_n\}$. Будем рассматривать элементы матрицы стоящие на местах $(i, j = i + 1)$, где $i = 1, \dots, n - 1$ и элемент на $(i = 1, j = n)$-м месте. Если соответсвующий элемент $m_{ij} = 1$, то cформируем строку-слово из букв $a_i \in A$ так, чтобы буквы были расположены в таком виде - $\dots a_i \dots a_{i+1} \dots a_i \dots a_{i+1} \dots$. Иначе, если $m_{ij} = 0$, буквы в строке расположим таким образом - $\dots a_i \dots a_i \dots a_{i+1} \dots a_{i+1} \dots$. Для элемента матрицы на $(i = 1, j = n)$-м месте, если $m_{1n} = 1$, то строка примет вид - $a_1 \dots a_n \dots a_1 \dots a_n \dots $. В противном случае - $a_1 \dots a_1 \dots a_n \dots a_n \dots$.

Посмотрите, пожалуйста. Такое построение корректно?

[alcoholist]

situs в сообщении #1380691 писал(а):

Пусть у нас есть $n \times n$ матрица $\mathbf{M}=(m_{ij})$.

Произвольная матрица? Над каким алгебраическим объектом?

situs в сообщении #1380691 писал(а):

Возьмем любой алфавит $A = \{a_1, a_2, \dots, a_n\}$.

Слово "любой" кажется лишним. Просто алфавит из $n$ букв.

situs в сообщении #1380691 писал(а):

Посмотрите, пожалуйста. Такое построение корректно?

Зачем нужна $n\times n$-матрица, если используются всего лишь $n$ ее элементов?

[Null]

А можно вопрос к чему редуцируется слово (123231)? Допустимо ли оно? Какой у него ранг матрицы?
А то по моему это контрпример.

[alcoholist]

Null в сообщении #1382829 писал(а):

Допустимо ли оно?

да

Null в сообщении #1382829 писал(а):

А можно вопрос к чему редуцируется слово (123231)?

не редуцируемо

Null в сообщении #1382829 писал(а):

Какой у него ранг матрицы?

2, сама матрица

$$ \left(\begin{array}{ccc} 0 & 0 & 0\\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{array}\right)$$

-- Вт мар 19, 2019 12:06:04 --

Null в сообщении #1382829 писал(а):

А то по моему это контрпример.

к чему?