Схема ассоциации

Теория ассоциативных схем возникла в статистике , в теории постановки эксперимента по дисперсионному анализу . В математике ассоциативные схемы относятся как к алгебре , так и к комбинаторике . В алгебраической комбинаторике схемы ассоциации обеспечивают единый подход ко многим темам, например, к комбинаторным проектам и теории кодов, исправляющих ошибки . В алгебре ассоциативные схемы обобщают группы , а теория ассоциативных схем обобщает теорию характеров линейных представлений групп .

Определение

Схема ассоциации n -класса состоит из × X на n + 1 множества X вместе с разбиением S X бинарные отношения , R 0 , R 1 _, ... , _R n , _{которые} удовлетворяют:

• $R_{0}=\{(x,x):x\in X\}$; это называется тождественным отношением .
• Определение $R^{*}:=\{(x,y):(y,x)\in R\}$, если R в S , то * в S. R
• Если $(x,y)\in R_{k}$, количество $z\in X$ такой, что $(x,z)\in R_{i}$ и $(z,y)\in R_{j}$ является константой $p_{ij}^{k}$ в зависимости от $i$, $j$, $k$ но не от конкретного выбора $x$ и $y$.

Схема ассоциации коммутативна, если $p_{ij}^{k}=p_{ji}^{k}$ для всех $i$, $j$ и $k$. Большинство авторов предполагают это свойство.Однако обратите внимание, что хотя понятие схемы ассоциации обобщает понятие группы, понятие коммутативной схемы ассоциации лишь обобщает понятие коммутативной группы .

Симметричная каждый схема ассоциации – это схема, в которой $R_{i}$ является симметричным отношением . То есть:

• если ( Икс , y ) ∈ р _я , то ( y , Икс ) ∈ р _я . (Или, что то же самое, R * = R .)

Любая симметричная схема ассоциации коммутативна.

Две точки x и y называются i- ми ассоциатами, если $(x,y)\in R_{i}$. В определении говорится, что если x и y являются i- ми ассоциатами, то такими же являются y и x . Каждая пара точек является i- м ассоциатом ровно для одного $i$. Каждая точка является своим собственным нулевым ассоциированным, тогда как отдельные точки никогда не являются нулевыми ассоциированными. Если x и y являются k- ми ассоциатами, то количество точек $z$ которые оба являются i- ми партнерами $x$ и j- е партнеры $y$ является константой $p_{ij}^{k}$.

Интерпретация графов и матрицы смежности

Симметричную схему ассоциации можно представить как полный граф с помеченными ребрами. На графике есть $v$ вершины, по одной на каждую точку $X$, и ребро, соединяющее вершины $x$ и $y$ помечен $i$ если $x$ и $y$ являются $i$ й соратники. Каждое ребро имеет уникальную метку, а количество треугольников с фиксированным основанием отмечено меткой $k$ имея другие края, помеченные $i$ и $j$ является константой $p_{ij}^{k}$, в зависимости от $i,j,k$ а не о выборе базы. В частности, каждая вершина инцидентна ровно $p_{ii}^{0}=v_{i}$ края помечены $i$; $v_{i}$ валентность ​ отношения ​ $R_{i}$. Есть также петли с надписью $0$ в каждой вершине $x$, соответствующий $R_{0}$.

Отношения . описываются матрицами смежности $A_{i}$ является матрицей смежности $R_{i}$ для $i=0,\ldots ,n$ и представляет собой v × v, матрицу размера строки и столбцы которой помечены точками $X$.

$\left(A_{i}\right)_{x,y}={\begin{cases}1,&{\mbox{if }}(x,y)\in R_{i},\\0,&{\mbox{otherwise.}}\end{cases}}\qquad (1)$

Определение симметричной схемы ассоциации эквивалентно утверждению, что $A_{i}$ являются v × v (0,1)-матрицами , удовлетворяющими

Я. $A_{i}$ симметричен,

II. $\sum _{i=0}^{n}A_{i}=J$ (матрица «все единицы»),

III. $A_{0}=I$,

IV. $A_{i}A_{j}=\sum _{k=0}^{n}p_{ij}^{k}A_{k}=A_{j}A_{i},i,j=0,\ldots ,n$.

( x , y )-я запись в левой части (IV) — это количество путей длины два между x и y с метками i и j в графе. Обратите внимание, что строки и столбцы $A_{i}$ содержать $v_{i}$ $1$х:

$A_{i}J=JA_{i}=v_{i}J.\qquad (2)$

Терминология

• Числа $p_{ij}^{k}$ называются параметрами схемы. Их еще называют структурными константами .

История

Термин «схема ассоциации» возник благодаря ( Bose & Shimamoto 1952 ), но эта концепция уже присуща ( Bose & Nair 1939 ). Эти авторы изучали то, что статистики назвали частично сбалансированными неполными блоками (PBIBD). Этот предмет стал объектом алгебраического интереса после публикации ( Bose & Mesner 1959 ) и введения алгебры Бозе-Меснера . Важнейшим вкладом в теорию стала диссертация П. Дельсарта ( Delsarte 1973 ), который признал и в полной мере использовал связи с теорией кодирования и теорией дизайна. Обобщения изучались Д. Г. Хигманом (когерентные конфигурации) и Б. Вейсфейлером ( дистанционно регулярные графы ).

Основные факты

• $p_{00}^{0}=1$, то есть, если $(x,y)\in R_{0}$ затем $x=y$ и единственный $z$ такой, что $(x,z)\in R_{0}$ является $z=x$.
• $\sum _{i=0}^{k}p_{ii}^{0}=|X|$; это потому, что $R_{i}$ раздел $X$.

Алгебра Бозе–Меснера

Матрицы смежности $A_{i}$ графиков ​ $\left(X,R_{i}\right)$ создать коммутативную и ассоциативную алгебру ${\mathcal {A}}$ (по действительным или комплексным числам ) как для матричного произведения , так и для поточечного произведения . Эта ассоциативная коммутативная алгебра называется алгеброй Бозе – Меснера схемы ассоциации.

Поскольку матрицы в ${\mathcal {A}}$ симметричны друг с другом, то и коммутируют их можно диагонализовать одновременно. Поэтому, ${\mathcal {A}}$ полупрост примитивных и имеет единственный базис идемпотентов $J_{0},\ldots ,J_{n}$.

Есть еще одна алгебра $(n+1)\times (n+1)$ матрицы изоморфные , ${\mathcal {A}}$, и с ним часто легче работать.

Примеры

• Схема Джонсона , обозначаемая J ( v , k ), определяется следующим образом. Пусть S — множество из v элементов. Точки схемы J ( v , k ) — это ${v \choose k}$ подмножества S с k элементами. Два k -элементных подмножества A , B из S являются i -ми ассоциатами, если их пересечение имеет размер k − i .
• Схема Хэмминга , обозначаемая H ( n , q ), определяется следующим образом. Точки H ( n , q ) — это q ^н упорядоченные n - кортежи на множестве размера q . Два n- кортежа x , y называются i -ми ассоциированными, если они расходятся ровно по i координатам. Например, если x = (1,0,1,1), y = (1,1,1,1), z = (0,0,1,1), то x и y — первые ассоциаты, x и z являются первыми ассоциатами, а y и z — 2-ми ассоциатами в H (4,2).
• Дистанционно -регулярный граф G формирует схему ассоциации, определяя две вершины как i -ые ассоциаты, если их расстояние равно i .
• Конечная группа G дает схему ассоциации на $X=G$, с классом R _g для каждого элемента группы следующим образом: для каждого $g\in G$ позволять $R_{g}=\{(x,y)\mid x=g*y\}$ где $*$ это групповая операция . Класс групповой идентичности равен R ₀ . Эта схема ассоциации коммутативна тогда и только тогда, G абелева когда .
• Конкретная схема ассоциации 3-х классов:

Пусть A (3) — следующая схема ассоциации с тремя ассоциативными классами на множестве X = {1,2,3,4,5,6}. Запись ( i , j ) равна s , если элементы i и j находятся в отношении R _s .

	1	2	3	4	5	6
1	0	1	1	2	3	3
2	1	0	1	3	2	3
3	1	1	0	3	3	2
4	2	3	3	0	1	1
5	3	2	3	1	0	1
6	3	3	2	1	1	0

Теория кодирования

Схема Хэмминга и схема Джонсона имеют важное значение в классической теории кодирования .

В теории кодирования в основном занимается расстоянием кода теория ассоциативных схем . Метод линейного программирования дает верхние границы размера кода с заданным минимальным расстоянием и нижние границы размера проекта с заданной надежностью. Наиболее конкретные результаты получаются в том случае, когда лежащая в основе схема ассоциации удовлетворяет определенным полиномиальным свойствам; это приводит нас в область ортогональных многочленов . В частности, получены некоторые универсальные границы для кодов и планов в схемах ассоциации полиномиального типа.

В классической теории кодирования , имеющей дело с кодами в схеме Хэмминга , преобразование Мак-Вильямса включает в себя семейство ортогональных полиномов, известных как полиномы Кравчука . Эти полиномы дают собственные значения матриц дистанционных отношений схемы Хэмминга .

См. также

• Блочный дизайн
• Алгебра Бозе – Меснера
• Комбинаторный дизайн

Ссылки

• Бейли, Розмари А. (2004), Схемы ассоциации: спланированные эксперименты, алгебра и комбинаторика , Cambridge University Press, ISBN  978-0-521-82446-0 , МР   2047311 . (Главы из предварительного проекта доступны в Интернете .)
• Баннаи, Эйичи; Ито, Тацуро (1984), Алгебраическая комбинаторика I: схемы ассоциаций , Менло-Парк, Калифорния: Бенджамин/Каммингс, ISBN  0-8053-0490-8 , МР   0882540
• Бозе, Колорадо ; Меснер, Д. М. (1959), «О линейных ассоциативных алгебрах, соответствующих схемам ассоциации частично сбалансированных планов» , Annals of Mathematical Статистика , 30 (1): 21–38, doi : 10.1214/aoms/1177706356 , JSTOR   2237117 , MR   0102157
• Бозе, Р.К .; Наир, К.Р. (1939), «Частично сбалансированные неполные блочные конструкции», Sankhyā , 4 (3): 337–372, JSTOR   40383923
• Бозе, Р.К .; Симамото, Т. (1952), «Классификация и анализ частично сбалансированных неполных блочных конструкций с двумя ассоциированными классами», Журнал Американской статистической ассоциации , 47 (258): 151–184, doi : 10.1080/01621459.1952.10501161
• Камион, П. (1998), «18. Коды и ассоциативные схемы: основные свойства ассоциативных схем, имеющих отношение к кодированию», в Плесс, В.С.; Хаффман, WC; Бруальди, Р.А. (ред.), Справочник по теории кодирования , вып. 1, Elsevier, стр. 1441–, ISBN.  978-0-444-50088-5
• Дельсарт, П. (1973), «Алгебраический подход к ассоциативным схемам теории кодирования», Philips Research Reports (Дополнение № 10), OCLC   641852316
• Дельсарт, П.; Левенштейн, В.И. (1998). «Схемы ассоциации и теория кодирования». Транзакции IEEE по теории информации . 44 (6): 2477–2504. дои : 10.1109/18.720545 .
• Дембовский, П. (1968), Конечная геометрия , Springer, ISBN  978-3-540-61786-0
• Годсил, компакт-диск (1993), Алгебраическая комбинаторика , Нью-Йорк: Чепмен и Холл, ISBN  0-412-04131-6 , МР   1220704
• МакВильямс, Ф.Дж.; Слоан, NJA (1977), Теория кодов, исправляющих ошибки , Математическая библиотека Северной Голландии, том. 16, Эльзевир, ISBN  978-0-444-85010-2
• Стрит, Энн Пенфолд ; Стрит, Дебора Дж. (1987), Комбинаторика экспериментального планирования , Oxford UP [Кларендон], ISBN  0-19-853256-3

• ван Линт, Дж. Х.; Уилсон, Р.М. (1992), Курс комбинаторики , издательство Кембриджского университета, ISBN  0-521-00601-5
• Цишанг, Пол-Херманн (2005a), « Схемы ассоциации: спланированные эксперименты, алгебра и комбинаторика Розмари А. Бэйли, обзор» (PDF) , Бюллетень Американского математического общества , 43 (2): 249–253, doi : 10.1090 /S0273-0979-05-01077-3
• Цишанг, Пол-Германн (2005b), Теория ассоциативных схем , Springer, ISBN  3-540-26136-2
• Цишанг, Пауль-Херманн (2006), «Условие обмена для ассоциативных схем», Израильский журнал математики , 151 (3): 357–380, doi : 10.1007/BF02777367 , MR   2214129 , S2CID   120009352