Матрица конференций

В математике матрица конференции (также называемая C - матрицей ) представляет собой квадратную матрицу C с 0 на диагонали и +1 и -1 на диагонали, такую, что C ^Т C кратен матрице I. единичной Таким образом, если матрица имеет порядок n , C ^Т C знак равно ( п -1) я . Некоторые авторы используют более общее определение, которое требует, чтобы в каждой строке и столбце был один 0, но не обязательно по диагонали.

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

Для n > 1 существует два типа матрицы конференций. Давайте нормализуем C , сначала (если используется более общее определение), переставив строки так, чтобы все нули находились на диагонали, а затем отрицая любую строку или столбец, первая запись в которых отрицательна. (Эти операции не меняют того, является ли матрица матрицей конференции.) Таким образом, нормализованная матрица конференций имеет все 1 в первой строке и столбце, за исключением 0 в верхнем левом углу, и равна 0 по диагонали. Пусть S — матрица, которая останется после первой строки и столбца C. удаления Тогда либо n четно , если его (кратно 4), а S кососимметрично ( как и нормализованный C первая строка инвертирована), либо n нечетно четно ( соответствует 2 по модулю 4) и симметрично ( S как – нормированный C ).

конференций

Если C — симметричная матрица конференции порядка n > 1, то не только n должно быть конгруэнтно 2 по модулю 4, но также n - 1 должно быть суммой двух квадратов ; есть умное доказательство с помощью теории элементарных матриц у Ван Линта и Зейделя. n всегда будет суммой двух квадратов, если n −1 — степень простого числа .

Учитывая симметричную матрицу конференции, матрицу S можно рассматривать как смежности Зейделя графа матрицу . Граф имеет n - 1 вершину, соответствующую строкам и столбцам S , и две вершины являются смежными, если соответствующая запись в S отрицательна. Этот граф является сильно регулярным и относится к типу, называемому (по названию матрицы) графом конференции .

Существование матриц конференций порядков n, допускаемых вышеуказанными ограничениями, известно только для некоторых значений n . Например, если n = q + 1, где q — степень простого числа, конгруэнтная 1 по модулю 4, то графы Пэли предоставляют примеры симметричных матриц конференций порядка n , принимая S в качестве матрицы Зейделя графа Пэли. Первые несколько возможных порядков симметричной матрицы конференции: n = 2, 6, 10, 14, 18 (не 22, поскольку 21 не является суммой двух квадратов), 26, 30 (не 34, поскольку 33 не является суммой двух квадратов). сумма двух квадратов), 38, 42, 46, 50, 54, (не 58), 62 (последовательность A000952 в OEIS ); для каждого из них известно, что существует симметричная матрица конференций такого порядка. Приказ 66 кажется открытой проблемой .

Пример

матрица По существу уникальная конференций порядка 6 имеет вид

${\begin{pmatrix}0&+1&+1&+1&+1&+1\\+1&0&+1&-1&-1&+1\\+1&+1&0&+1&-1&-1\\+1&-1&+1&0&+1&-1\\+1&-1&-1&+1&0&+1\\+1&+1&-1&-1&+1&0\end{pmatrix}}$.

Все остальные матрицы конференций порядка 6 получаются из этой путем перестановки знаков некоторой строки и/или столбца (и путем перестановки строк и/или столбцов в соответствии с используемым определением).

Кососимметричные

Кососимметричные матрицы также можно получить с помощью конструкции Пэли. Пусть q — степень простого числа с вычетом 3 по модулю 4. Тогда существует орграф Пэли порядка q кососимметричной матрице конференции порядка n = q + 1. Матрица получается, если в качестве S взять q , который приводит к × q матрица, которая имеет +1 в позиции ( i , j ) и -1 в позиции ( j , i ), если существует дуга орграфа от i до j и нулевая диагональ. Тогда C, построенный, как указано выше, из S , но с отрицательной первой строкой, является кососимметричной матрицей конференции.

Эта конструкция решает лишь небольшую часть проблемы определения, для каких четно-четных чисел n существуют кососимметричные матрицы конференций порядка n .

Обобщения

Иногда матрицу конференции порядка n определяют просто как взвешивающую матрицу вида W ( n, n −1), где Говорят, что W ( n,w ) имеет вес w > 0 и порядок n, если это квадратная матрица размера n с элементами из {−1, 0, +1}, удовлетворяющая W W ^Т = ш я . Используя это определение, нулевой элемент больше не обязательно должен находиться на диагонали, но легко видеть, что в каждой строке и столбце все равно должен быть ровно один нулевой элемент. Например, матрица

${\begin{pmatrix}1&0&1&1\\0&-1&-1&1\\1&-1&0&-1\\1&1&-1&0\end{pmatrix}}$

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

Дизайн конференции — это обобщение матриц конференции на непрямоугольные матрицы. Дизайн конференции C – это $N\times k$ матрица с элементами из {−1, 0, +1}, удовлетворяющими $W^{\mathrm {T} }W=(N-1)I_{k}$, где $I_{k}$ это $k\times k$ единичная матрица и не более одного нуля в каждой строке.Складные макеты конференц-проектов можно использовать в качестве окончательных макетов для отбора.

конференций

Тривиальная 2-портовая конференц-сеть

Белевич получил полные решения для матриц конференций для всех значений от n до 38 и предоставил схемы для некоторых меньших матриц. Идеальная конференц-сеть — это сеть, в которой потеря сигнала полностью вызвана разделением сигнала между несколькими абонентскими портами конференции. То есть потерь рассеивания внутри сети нет. В сети должны быть только идеальные трансформаторы и не должно быть сопротивлений. Идеальная конференц-сеть с n портами существует тогда и только тогда, когда существует матрица конференций порядка n . Например, 3-портовая конференц-сеть может быть построена с использованием хорошо известной схемы гибридного трансформатора, используемой для преобразования 2-проводной в 4-проводную связь в телефонных трубках и репитерах линии. Однако матрицы конференций третьего порядка не существует, и эта схема не создает идеальную конференц-сеть. Для согласования необходимо сопротивление, которое рассеивает сигнал, иначе сигнал будет потерян из-за несоответствия.

• 
  Реализация Белевичем 6-портовой идеальной конференц-сети
• 
  Реализация Белевичем 10-портовой идеальной конференц-сети

Как упоминалось выше, необходимым условием существования матрицы конференции является то, что n -1 должно быть суммой двух квадратов. Там, где существует более одной возможной суммы двух квадратов для n −1, будет существовать несколько существенно разных решений для соответствующей конференц-сети. Такая ситуация возникает при n, равном 26 и 66. Сети особенно просты, когда n −1 представляет собой полный квадрат ( n = 2, 10, 26, ...).

Ссылки

• Белевич В. (1950). «Теория 2n - терминальных сетей с приложениями к конференц-телефонии». Электрическая связь . 27 : 231–244.
• Гетальс Дж. М., Зайдель Дж. Дж. (1967). «Ортогональные матрицы с нулевой диагональю» . Канадский математический журнал . 19 : 1001–1010. дои : 10.4153/cjm-1967-091-8 . S2CID   197456608 .
• Лили Сяо и Деннис К.Дж. Линь и Фэншань Бай (2012). «Построение окончательного плана скрининга с использованием матриц конференций». Журнал технологий качества . 44 (1): 2–8. дои : 10.1080/00224065.2012.11917877 . S2CID   116145147 .
• Зайдель, Дж. Дж. (1991), изд. Д. Г. Корней и Р. Матон, Геометрия и комбинаторика: Избранные труды Дж. Дж. Зейделя . Бостон: Академическая пресса. Некоторые статьи посвящены матрицам конференций и их графикам.
• Колборн, Чарльз Дж.; Диниц, Джеффри Х. (2007) Справочник по комбинаторным расчетам , Бока-Ратон, Флорида: Чепмен и Холл/CRC Press, ISBN   1-58488-506-8 .
• ван Линт, Якобус Хендрик; Уилсон, Ричард Майкл (2001) Курс комбинаторики , Кембридж: Издательство Кембриджского университета, ISBN   0-521-00601-5 .
• Стинсон, Дуглас Роберт (2004) Комбинаторные планы: конструкции и анализ , Нью-Йорк: Springer, ISBN   0-387-95487-2 .
• Эрик Д. Шон, Питер Т. Эндебак, Питер Гус (2018). «Критерий классификации для окончательных планов скрининга». Анналы статистики . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )

Дальнейшее чтение

• Н. А. Балонин, Дженнифер Себерри, «Обзор и новые симметричные матрицы конференций» , Research Online , Университет Вуллонгонга, 2014. В приложении перечислены все известные и возможные матрицы конференций до 1002.