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

Теория ассоциативных схем возникла в статистике , в теории экспериментального планирования для дисперсионного анализа . ^{[1] [2] [3]} В математике ассоциативные схемы относятся как к алгебре, так и к комбинаторике . В алгебраической комбинаторике ассоциативные схемы обеспечивают единый подход ко многим темам, например, комбинаторным конструкциям и теории кодов, исправляющих ошибки . ^{[4] [5]} В алгебре ассоциативные схемы обобщают группы , а теория ассоциативных схем обобщает теорию характеров линейных представлений групп . ^{[6] [7] [8]}

Определение

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

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

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

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

• если ( x , y ) ∈ R _i , то ( y , x ) ∈ R _i . (Или, что эквивалентно, R * = R .)

Каждая симметричная схема ассоциации коммутативна.

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

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

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

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

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

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

I. симметричен, ${\displaystyle A_{i}}$

II. (матрица, состоящая из одних единиц), ${\displaystyle \sum _{i=0}^{n}A_{i}=J}$

III. , ${\displaystyle A_{0}=I}$

IV. . ${\displaystyle 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 в графе. Обратите внимание, что строки и столбцы содержат 's: ${\displaystyle A_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle 1}$

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

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

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

История

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

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

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

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

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

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

Существует еще одна алгебра матриц, которая изоморфна , и с ней часто проще работать. ${\displaystyle (n+1)\times (n+1)}$ ${\displaystyle {\mathcal {A}}}$

Примеры

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

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

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

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

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

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

Смотрите также

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

Примечания

1. Бейли 2004, стр. 387
2. Бозе и Меснер 1959
3. Бозе и Наир 1939
4. Баннаи и Ито 1984
5. Годсил 1993
6. Бейли 2004, стр. 387
7. Цишанг 2005b
8. Цишанг 2005a
9. Дембовски 1968, стр. 281, сноска 1
10. Баннаи и Ито 1984, стр. vii
11. Улица и улица 1987, стр. 238

Ссылки

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

• ван Линт, Дж. Х.; Уилсон, Р. М. (1992), Курс комбинаторики , Cambridge University Press, 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