Конференційна матриця

У математиці конференційна матриця (або C-матриця) — квадратна матриця ${\displaystyle C}$ з нулями на діагоналі, та з ${\displaystyle +1}$ і ${\displaystyle -1}$ поза діагоналлю така, що ${\displaystyle C^{T}C}$ кратна одиничній матриці ${\displaystyle I}$. Отже, якщо матриця має порядок ${\displaystyle n}$, то ${\displaystyle C^{T}C=(n-1)I}$. Деякі автори дають загальніше визначення, вимагаючи наявності нуля в кожному рядку і кожному стовпці, але не обов'язково на діагоналі^[1][2].

Конференційні матриці виникли у зв'язку із завданнями телефонії^[3]. Їх увів Вітольд Белевич^[en], термін «конференційна матриця» також увів він. Белевич цікавився створенням ідеальної телефонної мережі конференц-зв'язку з ідеальних трансформаторів. Він відкрив, що такі мережі можна подати конференційними матрицями, що й дало їм назву^[4]. Конференційні матриці також застосовують у статистиці^[5] та еліптичній геометрії^[6].

Для ${\displaystyle n>1}$ (${\displaystyle n}$ завжди парне) існує два види конференційних матриць. Якщо звести конференційну матрицю до нормального вигляду, вона стане симетричною (якщо ${\displaystyle n}$ ділиться на 4) чи антисиметричною (якщо ${\displaystyle n}$ парне, але не ділиться на 4).

Щоб отримати нормальний вигляд конференційної матриці ${\displaystyle C}$, потрібно:

1. Переставити рядки матриці ${\displaystyle C}$ так, щоб усі нулі опинилися на діагоналі (якщо використовується загальніше визначення конференційної матриці)
2. У рядках, перший елемент яких від'ємний, змінити знак у всіх елементів.
3. Змінити або не змінити знак у елементів першого рядка, щоб вийшла симетрична або антисиметрична матриця.

Отримана такими перетвореннями з конференційної матриці матриця також є конференційною матрицею. Перші елементи кожного рядка крім першого в конференційній матриці нормального вигляду дорівнюють 1 (у першому рядку перший елемент 0).

Якщо ${\displaystyle C}$ — симетрична конференційна матриця порядку ${\displaystyle n>1}$, то ${\displaystyle n}$ має бути не лише порівнянним із ${\displaystyle 2{\pmod {4}}}$, але також ${\displaystyle n-1}$ має бути сумою квадратів двох цілих чисел^[7]. Засобами елементарної теорії матриць можна довести^[6], що ${\displaystyle n-1}$ завжди буде сумою квадратів цілих чисел, якщо ${\displaystyle n-2}$ є степенем простого числа^[8].

Для заданої симетричної конференційної матриці ${\displaystyle C}$, підматрицю ${\displaystyle S}$, отриману викреслюванням із ${\displaystyle C}$першого рядка та стовпця, можна розглядати як зейделеву матрицю суміжності(інші мови) деякого графа. Це граф із ${\displaystyle n-1}$ вершиною, що відповідають рядкам і стовпцям матриці ${\displaystyle S}$, дві вершини є суміжними, якщо відповідні елементи матриці ${\displaystyle S}$ від'ємні. Отриманий граф є строго регулярним і належить до конференційних графів (названих саме через конференційні матриці).

Існування конференційних матриць порядку ${\displaystyle n}$, дозволене наведеними вище обмеженнями, відоме тільки для деяких значень ${\displaystyle n}$. Наприклад, якщо ${\displaystyle n=q+1}$ де ${\displaystyle q}$ — степінь простого числа, порівнянний з ${\displaystyle 1{\pmod {4}}}$ , то графи Пелі дають приклади симетричних матриць порядку ${\displaystyle n}$: як ${\displaystyle S}$ береться зейделева матриця суміжності графа Пелі. Перші кілька можливих порядків симетричних конференційних матриць ${\displaystyle n}$ = 2, 6, 10, 14, 18, (не 22, оскільки 21 не є сумою двох квадратів), 26, 30, (не 34, оскільки 33 не є сумою двох квадратів), 38, 42, 46, 50, 54, (не 58), 62 (послідовність A000952 з Онлайн енциклопедії послідовностей цілих чисел, OEIS); для всіх наведених значень відомо, що симетричні конференційні матриці існують. Для n = 66 питання залишається відкритим^[коли?].

Істотно єдина^[en] конференційна матриця порядку 6 має вигляд:

${\displaystyle {\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 можна отримати із даної зміною знака деяких рядків та/або стовпців (а також переставлянням рядків та/або стовпців, якщо використовується загальніше визначення).

Антисиметричні конференційні матриці можна отримати методом Пелі. Нехай ${\displaystyle q}$ — степінь простого числа із залишком ${\displaystyle 3{\pmod {4}}}$. Тоді існує граф Пелі порядку ${\displaystyle q}$, який приводить до антисиметричної конференційної матриці ${\displaystyle n=q+1}$. Ця матриця виходить, якщо для ${\displaystyle S}$ взяти ${\displaystyle q\times q}$-матрицю з ${\displaystyle +1}$ на ${\displaystyle (i,j)}$-ій позиції і ${\displaystyle -1}$ на ${\displaystyle (j,i)}$-ій, якщо існує ребро орграфа з ${\displaystyle i}$ в ${\displaystyle j}$, і нулями на діагоналі. Потім ${\displaystyle C}$ будується із ${\displaystyle S}$, як і в симетричному випадку, але перший рядок складається з недодатних чисел. Отримана в такий спосіб ${\displaystyle S}$ буде антисиметричною конференційною матрицею.

Цей метод вирішує лише невелику частину проблеми визначення, для яких ${\displaystyle n}$, що діляться на 4, існує антисиметрична конференційна матриця порядку ${\displaystyle n}$.

• Belevitch, V. (1950), Theorem of 2n-terminal networks with application to conference telephony. Electr. Commun., vol. 26, pp. 231—244.
• Goethals, J.M., and Seidel, J.J. (1967), Orthogonal matrices with zero diagonal. Canadian Journal of Mathematics, vol. 19, pp. 1001—1010.
• Seidel, J.J. (1991), ed. D.G. Corneil and R. Mathon, Geometry and Combinatorics: Selected Works of J.J. Seidel. Boston: Academic Press. Several of the articles are related to conference matrices and their graphs.
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007) Handbook of Combinatorial Designs, Boca Raton, Florida: Chapman and Hall/CRC Press, ISBN 1-58488-506-8.
• van Lint, Jacobus Hendricus; Wilson, Richard Michael (2001) A Course in Combinatorics, Cambridge: Cambridge University Press, ISBN 0-521-00601-5.
• Stinson, Douglas Robert (2004) Combinatorial Designs: Constructions and Analysis, New York: Springer, ISBN 0-387-95487-2.