Схема ассоциации - Association scheme

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

Определение

Схема ассоциации n-классов состоит из набор Икс вместе с раздел S из Икс × Икс в n + 1 бинарные отношения, Р₀, Р₁, ..., Р_п которые удовлетворяют:

• ${\displaystyle R_{0}=\{(x,x):x\in X\}}$ и называется отношение идентичности.
• Определение ${\displaystyle R^{*}:=\{(x,y):(y,x)\in R\}}$, если р в S, тогда Р* в S
• Если ${\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}}$ это симметричное отношение. То есть:

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

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

Обратите внимание, однако, что, хотя понятие схемы ассоциации обобщает понятие группы, понятие схемы коммутативной ассоциации только обобщает понятие коммутативной группы.

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

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

Симметричную схему ассоциации можно представить в виде полный график с маркированными краями. На графике ${\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}}$.

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

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

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

Я. ${\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}$.

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

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

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

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

История

Период, термин схема ассоциации связано с (Бозе и Симамото 1952 ) но концепция уже заложена в (Бозе и Наир 1939 ).^[9] Эти авторы изучали то, что статистики называют частично сбалансированные неполные блочные конструкции (PBIBD). Предмет стал объектом алгебраического интереса с публикацией (Бозе и Меснер 1959 ) и введение Алгебра Бозе – Меснера. Важнейшим вкладом в теорию явилась диссертация П. Дельсарта (Дельсарт 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 \left(n+1\right)\times \left(n+1\right)}$ матрицы который изоморфный к ${\displaystyle {\mathcal {A}}}$, и с ним часто легче работать.

Примеры

• В Схема Джонсона, обозначенный J(v, k), определяется следующим образом. Позволять S быть набором с v элементы. Пункты схемы J(v,k) являются ${\displaystyle {v \choose k}}$ подмножества S с k элементы. Два k-элементные подмножества А, B из S находятся я ые соратники, когда их пересечение имеет размер k − я.
• В Схема Хэмминга, обозначенный ЧАС(п,q), определяется следующим образом. Пункты ЧАС(п,q) являются q^п упорядоченный п-кортежи над набором размера q. Два п- пары Икс, у как говорят я -е сотрудники, если они не согласны в точности я координаты. Например, если Икс = (1,0,1,1), у = (1,1,1,1), z = (0,0,1,1), то Икс и у первые партнеры, Икс и z первые партнеры и у и z вторые партнеры в H (4,2).
• А дистанционно регулярный граф, грамм, формирует схему ассоциации, определяя две вершины как я th соратники, если их расстояние я.
• А конечная группа грамм дает схему ассоциации на ${\displaystyle X=G}$, с классом р_грамм для каждого элемента группы, а именно: для каждого ${\displaystyle g\in G}$ позволять ${\displaystyle R_{g}=\{(x,y)|x=g*y\}}$ куда ${\displaystyle *}$ это группа операция. Класс групповой идентичности р₀. Эта схема ассоциации коммутативна тогда и только тогда, когда грамм является абелевский.
• Конкретная схема ассоциации 3 классов:^[11]

Позволять А(3) следующая схема ассоциации с тремя ассоциированными классами на множестве Икс = {1,2,3,4,5,6}. (я,j) запись s если элементы я и 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

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

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

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

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

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

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

Примечания

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

Рекомендации

• Бейли, Розмари А. (2004), Схемы ассоциации: разработанные эксперименты, алгебра и комбинаторика, Издательство Кембриджского университета, ISBN  978-0-521-82446-0, МИСТЕР  2047311. (Главы предварительного проекта доступно онлайн.)
• Баннаи, Эйити; Ито, Тацуро (1984), Алгебраическая комбинаторика I: схемы ассоциаций, Менло-Парк, Калифорния: The Benjamin / Cummings Publishing Co., Inc., стр. Xxiv + 425, ISBN  0-8053-0490-8, МИСТЕР  0882540
• Бозе, Р.; Меснер, Д. М. (1959), «О линейных ассоциативных алгебрах, соответствующих схемам ассоциации частично сбалансированных планов», Анналы математической статистики, 30 (1): 21–38, Дои:10.1214 / aoms / 1177706356, JSTOR  2237117, МИСТЕР  0102157
• Бозе, Р.; Наир, К. Р. (1939), "Частично сбалансированные неполные блочные конструкции", Санкхья, 4: 337–372
• Бозе, Р.; Симамото Т. (1952), "Классификация и анализ частично сбалансированных неполных блочных конструкций с двумя ассоциированными классами", Журнал Американской статистической ассоциации, 47 (258): 151–184, Дои:10.1080/01621459.1952.10501161
• П. Камион (1998), Коды и схемы ассоциации: основные свойства схем ассоциации, относящиеся к кодированию, в Справочник по теории кодирования, V. S. Pless и W. C. Huffman, Eds., Elsevier, Нидерланды.
• Дельсарт, П. (1973), "Алгебраический подход к схемам ассоциации теории кодирования", Отчеты об исследованиях Philips, Приложение № 10
• Delsarte, P .; Левенштейн, В. И. (1998). «Ассоциативные схемы и теория кодирования». IEEE Transactions по теории информации. 44 (6): 2477–2504. Дои:10.1109/18.720545.
• Дембовский, П. (1968), Конечная геометрия, Берлин: Springer-Verlag
• Годсил, К. Д. (1993), Алгебраическая комбинаторика, Нью-Йорк: Чепмен и Холл, ISBN  0-412-04131-6, МИСТЕР  1220704
• Ф. Дж. Мак-Вильямс и Н. Дж. А. Слоан, Теория кодов, исправляющих ошибки, Эльзевир, Нью-Йорк, 1978.
• Улица, Энн Пенфолд & Улица, Дебора Дж. (1987). Комбинаторика экспериментального дизайна. Оксфорд У. П. [Кларендон]. ISBN  0-19-853256-3.

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