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

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

Конференційні матриці виникли у зв'язку із завданнями телефонії. Їх увів Шаблон:Нп, термін «конференційна матриця» також увів він. Белевич цікавився створенням ідеальної телефонної мережі конференц-зв'язку з ідеальних трансформаторів. Він відкрив, що такі мережі можна подати конференційними матрицями, що й дало їм назву. Конференційні матриці також застосовують у статистиці та еліптичній геометрії.

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

Нормальний вигляд конференційної матриці

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

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

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

Симетрична конференційна матриця

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

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

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

Приклад

Шаблон:Нп конференційна матриця порядку 6 має вигляд:

$\left(\begin{array}{cccccc}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{array}\right)$ ,

решту конференційних матриць порядку 6 можна отримати із даної зміною знака деяких рядків та/або стовпців (а також переставлянням рядків та/або стовпців, якщо використовується загальніше визначення).

Антисиметричні конференційні матриці

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

Цей метод вирішує лише невелику частину проблеми визначення, для яких $n$, що діляться на 4, існує антисиметрична конференційна матриця порядку $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.