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

[bot]

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

Вот берем допустимое слово $abcdacbd$. Редуцируем его до $ab'dab'd$

А если все двухбуквенные подслова различны по составу, то оно может быть редуцировано?
Вот, скажем, $abcdeacebd$ редуцируется или нет?

[waxtep]

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

Первоначально всегда $a$. Но в результате преобразований, например слова $aabcbc$ у вас получится слово $bcbc$. Тогда можно переименовать буквы $bcbc$ в $abab$. То есть, как обозначаются буквы не важно. Важен только их порядок расположения в строке.

Тогда в алфавите из трех символов допустимых слов получается слишком мало - пять штук - $\varnothing,abab$ и ещё три шестибуквенных

[alcoholist]

waxtep в сообщении #1379761 писал(а):

слишком мало

это нормально, так как подразумевается, что матрицы определены с точностью до "элементарных преобразований"

[situs]

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

какие слова называются допустимыми (хорошими). Уже дайте внятное определение.

Допустимые - это в смысле первоначального построения или рассмотрения, а не их "хорошести". То есть мы рассматриваем только допустимые слова на произвольном алфавите конечной длины.

Хорошим или разрешенным словом будем называть допустимое слово, которое редуцируется до одного из $(), (abab), (abcabc)$. В противном случае слово будем называть плохим или запрещенным.

[alcoholist]

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

Хорошим или разрешенным словом будем называть допустимое слово, которое редуцируется до одного из $(), (abab), (abcabc)$. В противном случае слово будем называть плохим или запрещенным.

 в любом алфавите???

-- Пн мар 04, 2019 13:56:30 --

пока не определите все объекты корректно...

[situs]

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

в любом алфавите???

Не понял?

Я же написал:

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

мы рассматриваем только допустимые слова на произвольном алфавите конечной длины.

[alcoholist]

situs
напишите в отдельном посте определение всех понятий и свое утверждение

-- Пн мар 04, 2019 14:21:54 --

с нуля... это и вам пригодится

[Someone]

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

Я же написал:

Очевидно, имелось в виду "в любом конечном".

Вообще, у меня сложилось впечатление, что Вы придумываете новые правила "на ходу", не важно какие, лишь бы продолжать обсуждение.
Давайте уж окончательную версию.

[situs]

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

напишите в отдельном посте определение всех понятий и свое утверждение

Someone в сообщении #1379780 писал(а):

Давайте уж окончательную версию.

Определение 1. Cлово длины $2n$ на любом конечном алфавите $\{a_1,a_2,\cdots,a_n\}$ называется допустимым, если
а) Каждая буква входит в слово ровно два раза.
б) Буква $a_{i+1}$ первый раз (слева направо) входит в слово после буквы $a_i$.

Определение 2. Редукцией допустимого слова называется композиция некоторого числа следующих преобразований
1) Удаление двух стоящих рядом одинаковых букв.
2) Замена двух букв на одну, если буквы в слове расположены таким образом - $\dots xy \dots yx \dots$ (в этом случае слово преобразуется к виду $\dots x \dots x \dots$).

Определение 3. Пусть $w$ - допустимое слово длины $2n$. Редуцированное слово - слово длины $2m < 2n$, полученное в результате редукции $w$ и переименования букв на алфавите $\{a_1,a_2,\cdots,a_m\}$ по правилу (б) определения 1.

Определение 4. Допустимое или редуцированное слово следующего вида $(), (xyxy), (xyzxyz)$ называется хорошим словом. Слово $()$ - пустое слово, т.е. слово без букв.

Определение 5. Буквы $x$ и $y$ в допустимом или редуцированном слове будем называть дружественными, если они расположены в таком порядке - $\dots x \dots y \dots x \dots y$.

Определение 6. Матрицей слова длины $2n$ называется $n \times n$ матрица $\mathbf{M} = (m_{ij})$ над полем $\mathbb{Z}_2$ элементы которой определяются по следующему правилу. Если в слове две буквы с номерами $i, j$ дружественные, тогда $m_{ij} = m_{ji} = 1$. В противном случае $m_{ij} = m_{ji} = 0$.

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

[alcoholist]

Определение 4+. Допустимое слово, редуцирующееся к виду $(), (xyxy), (xyzxyz)$ называется хорошим.

-- Пн мар 04, 2019 20:03:27 --

Определение 5+. Буквы $x$ и $y$ в допустимом слове будем называть дружественными, если они расположены в таком порядке - $\dots x \dots y \dots x \dots y$.

-- Пн мар 04, 2019 20:06:47 --

утверждение становится тривиальным

[situs]

alcoholist

Спасибо за замечания! Определения учту. Хотя я думал, что достаточно будет по одному определению. Почему Ваш вариант более аккуратный?

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

утверждение становится тривиальным

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

Не понимаю, нужно ли, чтобы быть честным, отдельно показывать биекцию между множеством хороших слов и матриц? Вот например, обратное соответствие - как по матрице построить слово?

[alcoholist]

+ это не еще, а вместо))
Доказывать все строго обязательно

[situs]

Еще остался открытым такой вопрос! Как по матрице построить слово? У меня не получается. Предположение, что однозначно этого сделать не получиться. Помогите пожалуйста!

[alcoholist]

кажется, надо начать с того, что ранг матрицы равен 2

[situs]

А если ранг не 2. Я говорю про любую матрицу, не только хороших слов.

Пусть матрица будет

$\begin{pmatrix} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 0 \end{pmatrix}$

Как вот по ней можно построить допустимое слово?