Конференс-матрица

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

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

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

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

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

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

Полученная такими преобразованиями из конференс-матрицы матрица также является конференс-матрицей. Первые элементы каждой строки кроме первой у нормального вида конференс-матрицы равны 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 имеет вид:

,

все остальные конференс-матрицы порядка 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.

Примечания
  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 (англ.) // Annals of Mathematical Statistics : journal. — 1959. — Vol. 30, no. 2. — P. 295—303. — doi:10.1214/aoms/1177706253.
  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. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.