PROFILPELAJAR.COM

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

Конференс-матрицы изначально возникли в связи с задачами телефонии^[3]. Их ввёл Витольд Белевич, термин конференс-матрица ввёл он же. Белевич интересовался созданием идеальной телефонной сети конференц-связи из идеальных трансформаторов. Он открыл, что такие сети могут быть представлены конференс-матрицами, что и дало им имя^[4]. Конференс-матрицы также применяются в статистике^[5] и эллиптической геометрии^[6].

Для n > 1 (n всегда чётно) существует два вида конференс-матриц. Если привести конференс-матрицу к нормальному виду, то она станет симметричной (если n делится на 4) или антисимметричной (если n чётно, но не делится на 4).

Нормальный вид конференс-матрицы

Для того чтобы получить нормальный вид конференс-матрицы C, нужно:

Переставить строки матрицы C так, чтобы все нули оказались на диагонали (если используется более общее определение конференс-матрицы)
В тех строках, в которых первый элемент является отрицательным, сменить знак у всех элементов.
Сменить или не сменить знак у элементов первой строки, чтобы получилась симметричная или антисимметричная матрица.

Полученная такими преобразованиями из конференс-матрицы матрица также является конференс-матрицей. Первые элементы каждой строки кроме первой у нормального вида конференс-матрицы равны 1 (у первой строки первый элемент 0).

Симметричная конференс-матрица

Если C — симметрична конференс-матрица порядка n > 1, то n должно быть не только сравнимо с 2 (mod 4), но также n − 1 должно быть суммой квадратов двух целых чисел^[7]. Посредством элементарной теории матриц можно доказать^[6], n − 1 всегда будет суммой квадратов целых чисел, если n − 2 является степенью простого числа^[8].

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

Существование конференс-матриц порядка n, разрешаемое вышеуказнными ограничениями известно только для некоторых значений n. Например, если n = q + 1 где q является простой степенью сравнимой с 1 (mod 4), то графы Пэли дают примеры симметричных матриц порядка n: в качестве S берётся зейделева матрица смежности графа Пэли. Первые несколько возможных порядков симметричных конференс-матриц n = 2, 6, 10, 14, 18, (не 22, так как 21 не является суммой двух квадратов), 26, 30, (не 34, так как 33 не является суммой двух квадратов), 38, 42, 46, 50, 54, (не 58), 62 (последовательность A000952 в OEIS); для всех приведённых значений известно, что симметричные конференс-матрицы существуют. Для n = 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 (mod 4). Тогда существует граф Пэли порядка q, который приводит к антисимметричной конференс-матрице порядка n = q + 1. Данная матрица получается, если для S взять q×q-матрицу с +1 на (i, j)-й позиции и −1 на (j, i)-й, если существует ребро орграфа из i в j, и нулями на диагонали. Затем S строится из S как и в симметричном случае, но первая строка составляется из неположительных чисел. Полученная таким образом S будет антисимметричной конференс-матрицей.

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

Примечания

↑ 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
↑ 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
↑ Belevitch, pp. 231—244.
↑ Colbourn and Dinitz, (2007), p.19
van Lint and Wilson, (2001), p.98
Stinson, (2004), p.200
↑ Raghavarao, D. Some optimum weighing designs (англ.) // Annals of Mathematical Statistics^[англ.] : journal. — 1959. — Vol. 30, no. 2. — P. 295—303. — doi:10.1214/aoms/1177706253. Архивировано 3 марта 2016 года.
↑ ¹ ² van Lint, J.H., and Seidel, J.J. (1966), Equilateral point sets in elliptic geometry. Indagationes Mathematicae, vol. 28, pp. 335—348.
↑ Belevitch, p.240
↑ 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. 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.