В математике конференс-матрица (также называемая 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, нужно:
- Переставить строки матрицы 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 имеет вид:
- ,
все остальные конференс-матрицы порядка 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. (1959). “Some optimum weighing designs”. Annals of Mathematical Statistics. 30 (2): 295—303. DOI:10.1214/aoms/1177706253. MR 0104322.
- 1 2 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.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .