2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7
 
 Re: Биекция между словами и матрицами
Сообщение19.03.2019, 12:47 
Заслуженный участник


12/08/10
1608
alcoholist в сообщении #1379823 писал(а):
Допустимое слово, редуцирующееся к виду $(), (xyxy), (xyzxyz)$ называется хорошим.

situs в сообщении #1380057 писал(а):
Слово является хорошим тогда и только тогда, когда ранг его матрицы $\leqslant 2$.

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение19.03.2019, 13:26 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
Null
ну, это к ТС вопрос))
Вероятно, надо к редукции слов добавить и редукцию $aWa\mapsto W$, так как слова $aWa$ и $aaW$ определяют одну и ту же матрицу.
И список редукций еще пошерстить надо наверняка. Еще какие-то добавить.

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение19.03.2019, 14:55 
Аватара пользователя


03/02/19
138
Null в сообщении #1382861 писал(а):
alcoholist в сообщении #1379823 писал(а):
Допустимое слово, редуцирующееся к виду $(), (xyxy), (xyzxyz)$ называется хорошим.

situs в сообщении #1380057 писал(а):
Слово является хорошим тогда и только тогда, когда ранг его матрицы $\leqslant 2$.
Так. А в чем упрёк вопрос? Cформулируйте, пожалуйста.

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение19.03.2019, 16:55 
Аватара пользователя


03/02/19
138
alcoholist

Спасибо за замечания. Кажется я понял. Посмотрите.

Покажем, что каждой матрице $\mathbf{M}(w)$ может быть поставлено в соответствие слово $w$.

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

$\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$.


Таким образом получим слово-строку или слово $w$ длины $2n$

 Профиль  
                  
 
 Re: Биекция между словами и матрицами
Сообщение22.03.2019, 08:41 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
situs в сообщении #1382910 писал(а):
Покажем, что каждой матрице $\mathbf{M}(w)$ может быть поставлено в соответствие слово $w$.
Не пишите "покажем, что". Здесь ведь по смыслу: Опишем правило $M\mapsto w_M$.

-- Пт мар 22, 2019 08:46:54 --

situs
Вопрос все равно остается. Для построения слова вы используется всего $n$ элементов матрицы из $\frac{1}{2}\left(n^2-n\right)$.

-- Пт мар 22, 2019 08:49:15 --

alcoholist в сообщении #1382767 писал(а):
Зачем нужна $n\times n$-матрица, если используются всего лишь $n$ ее элементов?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 95 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7

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



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

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


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

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