Введение
Теория ассоциационных схем возникла в статистике, в теории экспериментального проектирования для анализа дисперсии. В математике схемы ассоциаций относятся как к алгебре, так и к комбинаторике. В алгебраической комбинаторике схемы ассоциаций обеспечивают единый подход к многим темам, например, комбинаторным конструкциям и теории кодов коррекции ошибок. В алгебре схемы ассоциаций обобщают группы, а теория ассоциационных схем обобщает теорию символов линейных представлений групп.
Определение
Схема ассоциации n классов состоит из множества X вместе с разделом S X × X на n + 1 бинарных отношений, R0, R1, , Rn, которые удовлетворяют:; это называется отношением идентичности. Определяя , если R в S, то R* в S. Если , число таких, что и является константой в зависимости от , , но не от конкретного выбора и схема ассоциации является коммутативной, если для всех , и большинство авторов предполагают это свойство. Однако следует отметить, что, в то время как понятие схемы ассоциации обобщает понятие группы, понятие коммутативной схемы ассоциации обобщает только понятие коммутативной группы. Схема симметричной ассоциации - это схема, в которой каждый из них является симметричным отношением. То есть: если (x, y) ∈ Ri, то (y, x) ∈ Ri. (или эквивалентно, R* = R.) Каждая схема симметричных ассоциаций является коммутативной. Две точки x и y называются i-выми соотношениями, если в определении говорится, что если x и y являются i-выми соотношениями, то и y и x также являются соотношениями. Каждая пара точек является i-ой ассоциированной точкой для ровно одного, каждый пункт является своей собственной нулевой ассоциированной точкой, в то время как отдельные точки никогда не являются нулевой ассоциированной точкой. Если x и y - k-ие соотношения , то число точек , которые являются и i-ими соотношениями , и j-ими соотношениями , является постоянной .
; it is called the identity relation. Defining , if R in S, then R* in S.
If , the number of such that and is a constant depending on , , but not on the particular choice of and
An association scheme is commutative if for all , and Most authors assume this property. Note, however, that while the notion of an association scheme generalizes the notion of a group, the notion of a commutative association scheme only generalizes the notion of a commutative group. A symmetric association scheme is one in which each is a symmetric relation. That is:
if (x, y) ∈ Ri, then (y, x) ∈ Ri. (Or equivalently, R* = R.)
Every symmetric association scheme is commutative. Two points x and y are called i th associates if The definition states that if x and y are i th associates then so are y and x. Every pair of points are i th associates for exactly one Each point is its own zeroth associate while distinct points are never zeroth associates. If x and y are k th associates then the number of points which are both i th associates of and j th associates of is a constant .
Терминология
Числа называются параметрами схемы. Они также называются структурными константами.
История
Эти авторы изучали то, что статистики называют частично сбалансированными неполными блок-проектами (PBIBD). Предмет стал объектом интереса алгебры с публикацией и введением алгебры Бозе-Меснера. Наиболее важным вкладом в теорию был тезис П. Делсарте, который признал и полностью использовал связи с теорией кодирования и теорией дизайна. Обобщения изучались Д. Г. Хигманом (когерентные конфигурации) и Б. Вайсфейлером (регулярные графики расстояний).
Основные факты
, т.е. если тогда и единственное такое, что есть; это потому, что разделение.
Алгебра Бозе-Меснера
Матрицы смежности графов генерируют коммутативную и ассоциативную алгебру (над действительными или комплексными числами) как для произведения матрицы, так и для произведения по точке. Эта ассоциативная, коммутативная алгебра называется алгеброй ассоциации Бозе-Меснера. Поскольку матрицы в symmetric симметричны и коммутируют друг с другом, они могут быть одновременно диагонализированы. Следовательно, полупростая и имеет уникальную основу примитивных идемпотентов. Существует другая алгебра матриц, которая изоморфна к , и с ней часто легче работать.
There is another algebra of matrices which is isomorphic to , and is often easier to work with.
Теория кодирования
Схема Хамминга и схема Джонсона имеют большое значение в классической теории кодирования. В теории кодирования теория схемы ассоциаций в основном связана с расстоянием кода. Метод линейного программирования дает верхние границы для размера кода с заданным минимальным расстоянием и нижние границы для размера конструкции с заданной прочностью. Наиболее конкретные результаты получаются в том случае, когда основополагающая схема ассоциации удовлетворяет определенным свойствам полиномов; это приводит к области ортогональных полиномов. В частности, некоторые универсальные границы производятся для кодов и конструкций в схемах ассоциации многочленного типа. В классической теории кодирования, имеющей дело с кодами в схеме Хамминга, преобразование Маквильямса включает в себя семейство ортогональных многочленов, известных как многочленов Краутчука. Эти многочлены дают собственные значения матриц отношений расстояний схемы Хамминга.