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

[alcoholist]

приведите пример слова длины 8

[situs]

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

приведите пример слова длины 8

$w_1 = (a_{1}a_{2}a_{3}a_{4}a_{1}a_{2}a_{3}a_{4})$ - с отношением дружественности - каждый элемент дружит с каждым.

$w_2 = (a_{1}a_{1}a_{2}a_{2}a_{3}a_{3}a_{4}a_{4})$ - с отношением дружественности - никто не дружит.

Им будут соответствовать матрицы:

$\mathbf{M}(w_1) = \begin{pmatrix} 0 & 1 & 1 & 1\\ 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1\\ 1 & 1 & 1 & 0 \end{pmatrix}$

$\mathbf{M}(w_2) = \begin{pmatrix} 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 \end{pmatrix}$

[alcoholist]

ну так перечислите матрицы, которые таким путем можно получить

[situs]

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

ну так перечислите матрицы, которые таким путем можно получить

Не понял Вас!
Я уже показал как по "слову" можно построить матрицу. Теперь, чтобы показать взаимно-однозначное соответствие между "словами" и матрицами, мне нужно показать обратное, что по любой квадратной матрице над полем $\mathbb{Z}_2 $ с нулевой главной диагональю можно построить "слово".

[alcoholist]

не всякой 0-1матрице соответствует слово... а каким?

[waxtep]

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

Ему будет соответствовать матрица:

$M_{13}$ и $M_{24}$ тоже, видимо, нолики? $a_1$ с $a_3$ нигде не соседствуют и т.п.

[situs]

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

не всякой 0-1матрице соответствует слово... а каким?

Квадратная симметричная матрица над полем $\mathbb{Z}_2 $ с нулевой главной диагональю.

[waxtep]

Что-то будет тяжело с биекцией: в алфавите длины $3$, все слова, где нет двух одинаковых букв подряд, отобразятся в одну и ту же матрицу

[situs]

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

Что-то будет тяжело с биекцией: в алфавите длины $3$, все слова, где нет двух одинаковых букв подряд, отобразятся в одну и ту же матрицу

Не так. На алфавите длины 3 будет 8 разных "слов" и соответственно 8 разных матриц.

[waxtep]

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

Не так. На алфавите длины 3 будет 8 разных "слов" и соответственно 8 разных матриц.

Возможно, чего-то не понимаю, скажите, какими будут матрицы для слов $xyzxyz$ и $xyxzyz$? Я из Вашего описания понял, что для обоих слов будет матрица с нулями на главной диагонали и единицами вне.

[alcoholist]

поточнее описание «слов»

[situs]

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

матрицы для слов $xyzxyz$ и $xyxzyz$

$\mathbf{M}(xyzxyz) = \bordermatrix{ & x & y & z\cr x & 0 & 1 & 1\cr y & 1 & 0 & 1 \cr z & 1 & 1 & 0 \cr}$

$\mathbf{M}(xyxzyz) = \bordermatrix{ & x & y & z\cr x & 0 & 1 & 0\cr y & 1 & 0 & 1 \cr z & 0 & 1 & 0 \cr}$

-- 03.03.2019, 16:17 --

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

поточнее описание «слов»

Куда еще точнее я пока не понимаю. Лучше скажите, что Вам непонятно?

[waxtep]

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

waxtep в сообщении #1379588

писал(а):
матрицы для слов $xyzxyz$ и $xyxzyz$

$\mathbf{M}(xyzxyz) = \bordermatrix{ & x & y & z\cr x & 0 & 1 & 1\cr y & 1 & 0 & 1 \cr z & 1 & 1 & 0 \cr}$ $\mathbf{M}(xyxzyz) = \bordermatrix{ & x & y & z\cr x & 0 & 1 & 0\cr y & 1 & 0 & 1 \cr z & 0 & 1 & 0 \cr}$

Но ведь в $xyxzyz$ буква $z$ "дружит" (соседствует) и с буквой $x$, и с буквой $y$, почему в матрице отражена "дружба" $z$ только с $y$, но не с $x$?

[alcoholist]

situs
для того, чтобы буквы $x,y$ дружили, они должны расположиться обязательно как $\ldots xy\ldots xy\ldots$, или можно $\ldots xy\ldots yx\ldots$, или достаточно $\ldots xy\ldots$, как вы показали в примере для

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

$$\mathbf{M}(xyxzyz) = \bordermatrix{ & x & y & z\cr x & 0 & 1 & 0\cr y & 1 & 0 & 1 \cr z & 0 & 1 & 0 \cr}$$

[Someone]

Ну, это обычные определения. Алфавит — произвольное множество; его элементы называются символами или буквами. Конечная последовательность символов — слово. Алфавит может быть и бесконечным (любой мощности), но Вас интересует только конечный алфавит.

Правила образования слов у Вас прописаны недостаточно подробно. Однозначно понятно, что если алфавит содержит $n$ символов, то слово должно содержать $2n$ символов, каждый по два раза.
Непонятно, могут ли соседние буквы быть одинаковыми. Например, в алфавите $A_1=\{a\}$ из одной буквы возможно только слово $aa$. Оно допустимо по вашим правилам или нет?
В алфавите $A=\{a,b\}$ из двух букв можно составить $6$ слов: $aabb$, $abab$, $abba$, $baab$, $baba$, $bbaa$. Какие из них допустимы?
В алфавите из $n$ букв по указанному правилу можно составить $\frac{(2n)!}{2^n}$ слов. Например, для $n=3$ получаем $\frac{6!}{2^3}=\frac{720}8=90$ слов.
С отношением дружественности неясностей больше.
Если буквы дружественные, они могут стоять в слове рядом или обязаны стоять в слове рядом? Во втором случае обе пары или достаточно одной пары? Если обе пары, то в одном и том же порядке или могут в разных? То есть, обязательно $xy\ldots xy$ или можно и $xy\ldots yx$?

В наиболее естественной для меня интерпретации отношение дружественности указывает, какие буквы могут, но не обязаны стоять рядом, при этом буква сама для себя является дружественной, то есть, две одинаковые буквы могут стоять рядом. Количество таких отношений дружественности для алфавита из $n$ букв равно $2^{\frac{n(n-1)}2}$, что при $n\geqslant 2$ не равно количеству слов. Легко проверить, что

$$\frac{(2n)!}{2^n}>2^{\frac{n(n-1)}2}\text{ при }2\leqslant n\leqslant 12,$$

$$\frac{(2n)!}{2^n}<2^{\frac{n(n-1)}2}\text{ при }n>12.$$

Уточняйте, пожалуйста.