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

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

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

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

Для заданої симетричної конференційної матриці ${\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}$.

Примітки

1. Malcolm Greig, Harri Haanpää, and Petteri Kaski, Journal of Combinatorial Theory, Series A, vol. 113, no. 4, 2006, pp 703—711, DOI:10.1016/j.jcta.2005.05.005
2. Harald Gropp, More on orbital matrices, Electronic Notes in Discrete Mathematics, vol. 17, 2004, pp 179—183, DOI:10.1016/j.endm.2004.03.036
3. Belevitch, pp. 231—244.
4. Colbourn and Dinitz, (2007), p.19
   van Lint and Wilson, (2001), p.98
   Stinson, (2004), p.200
5. Raghavarao, D. Some optimum weighing designs // ^[en] : journal. — 1959. — Vol. 30, no. 2 (5 June). — P. 295—303. — DOI:10.1214/aoms/1177706253. з джерела 3 березня 2016.
6. van Lint, J.H., and Seidel, J.J. (1966), Equilateral point sets in elliptic geometry. Indagationes Mathematicae, vol. 28, pp. 335—348.
7. Belevitch, p.240
8. Stinson, p.78

Література

• 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. 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, .
• van Lint, Jacobus Hendricus; Wilson, Richard Michael (2001) A Course in Combinatorics, Cambridge: Cambridge University Press, .
• Stinson, Douglas Robert (2004) Combinatorial Designs: Constructions and Analysis, New York: Springer, .