Конференс-матрица
В математике, конференс-матрица (также называемая 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 имеет вид:
- <math>\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}</math>,
все остальные конференс-матрицы порядка 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). «[projecteuclid.org/euclid.aoms/1177706253 Some optimum weighing designs]». Annals of Mathematical Statistics 30 (2): 295–303. DOI:10.1214/aoms/1177706253.
- ↑ 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.
Отрывок, характеризующий Конференс-матрица
– Ах это ужасно, ужасно! – сказал Пьер. – Я не понимаю только – как можно жить с такими мыслями. На меня находили такие же минуты, это недавно было, в Москве и дорогой, но тогда я опускаюсь до такой степени, что я не живу, всё мне гадко… главное, я сам. Тогда я не ем, не умываюсь… ну, как же вы?…– Отчего же не умываться, это не чисто, – сказал князь Андрей; – напротив, надо стараться сделать свою жизнь как можно более приятной. Я живу и в этом не виноват, стало быть надо как нибудь получше, никому не мешая, дожить до смерти.
– Но что же вас побуждает жить с такими мыслями? Будешь сидеть не двигаясь, ничего не предпринимая…
– Жизнь и так не оставляет в покое. Я бы рад ничего не делать, а вот, с одной стороны, дворянство здешнее удостоило меня чести избрания в предводители: я насилу отделался. Они не могли понять, что во мне нет того, что нужно, нет этой известной добродушной и озабоченной пошлости, которая нужна для этого. Потом вот этот дом, который надо было построить, чтобы иметь свой угол, где можно быть спокойным. Теперь ополчение.
– Отчего вы не служите в армии?
– После Аустерлица! – мрачно сказал князь Андрей. – Нет; покорно благодарю, я дал себе слово, что служить в действующей русской армии я не буду. И не буду, ежели бы Бонапарте стоял тут, у Смоленска, угрожая Лысым Горам, и тогда бы я не стал служить в русской армии. Ну, так я тебе говорил, – успокоиваясь продолжал князь Андрей. – Теперь ополченье, отец главнокомандующим 3 го округа, и единственное средство мне избавиться от службы – быть при нем.
– Стало быть вы служите?
– Служу. – Он помолчал немного.
– Так зачем же вы служите?
– А вот зачем. Отец мой один из замечательнейших людей своего века. Но он становится стар, и он не то что жесток, но он слишком деятельного характера. Он страшен своей привычкой к неограниченной власти, и теперь этой властью, данной Государем главнокомандующим над ополчением. Ежели бы я два часа опоздал две недели тому назад, он бы повесил протоколиста в Юхнове, – сказал князь Андрей с улыбкой; – так я служу потому, что кроме меня никто не имеет влияния на отца, и я кое где спасу его от поступка, от которого бы он после мучился.
– А, ну так вот видите!
– Да, mais ce n'est pas comme vous l'entendez, [но это не так, как вы это понимаете,] – продолжал князь Андрей. – Я ни малейшего добра не желал и не желаю этому мерзавцу протоколисту, который украл какие то сапоги у ополченцев; я даже очень был бы доволен видеть его повешенным, но мне жалко отца, то есть опять себя же.
Князь Андрей всё более и более оживлялся. Глаза его лихорадочно блестели в то время, как он старался доказать Пьеру, что никогда в его поступке не было желания добра ближнему.
– Ну, вот ты хочешь освободить крестьян, – продолжал он. – Это очень хорошо; но не для тебя (ты, я думаю, никого не засекал и не посылал в Сибирь), и еще меньше для крестьян. Ежели их бьют, секут, посылают в Сибирь, то я думаю, что им от этого нисколько не хуже. В Сибири ведет он ту же свою скотскую жизнь, а рубцы на теле заживут, и он так же счастлив, как и был прежде. А нужно это для тех людей, которые гибнут нравственно, наживают себе раскаяние, подавляют это раскаяние и грубеют от того, что у них есть возможность казнить право и неправо. Вот кого мне жалко, и для кого бы я желал освободить крестьян. Ты, может быть, не видал, а я видел, как хорошие люди, воспитанные в этих преданиях неограниченной власти, с годами, когда они делаются раздражительнее, делаются жестоки, грубы, знают это, не могут удержаться и всё делаются несчастнее и несчастнее. – Князь Андрей говорил это с таким увлечением, что Пьер невольно подумал о том, что мысли эти наведены были Андрею его отцом. Он ничего не отвечал ему.
– Так вот кого мне жалко – человеческого достоинства, спокойствия совести, чистоты, а не их спин и лбов, которые, сколько ни секи, сколько ни брей, всё останутся такими же спинами и лбами.
– Нет, нет и тысячу раз нет, я никогда не соглашусь с вами, – сказал Пьер.
Вечером князь Андрей и Пьер сели в коляску и поехали в Лысые Горы. Князь Андрей, поглядывая на Пьера, прерывал изредка молчание речами, доказывавшими, что он находился в хорошем расположении духа.
Он говорил ему, указывая на поля, о своих хозяйственных усовершенствованиях.
Пьер мрачно молчал, отвечая односложно, и казался погруженным в свои мысли.
Пьер думал о том, что князь Андрей несчастлив, что он заблуждается, что он не знает истинного света и что Пьер должен притти на помощь ему, просветить и поднять его. Но как только Пьер придумывал, как и что он станет говорить, он предчувствовал, что князь Андрей одним словом, одним аргументом уронит всё в его ученьи, и он боялся начать, боялся выставить на возможность осмеяния свою любимую святыню.
– Нет, отчего же вы думаете, – вдруг начал Пьер, опуская голову и принимая вид бодающегося быка, отчего вы так думаете? Вы не должны так думать.
– Про что я думаю? – спросил князь Андрей с удивлением.
– Про жизнь, про назначение человека. Это не может быть. Я так же думал, и меня спасло, вы знаете что? масонство. Нет, вы не улыбайтесь. Масонство – это не религиозная, не обрядная секта, как и я думал, а масонство есть лучшее, единственное выражение лучших, вечных сторон человечества. – И он начал излагать князю Андрею масонство, как он понимал его.
Он говорил, что масонство есть учение христианства, освободившегося от государственных и религиозных оков; учение равенства, братства и любви.
– Только наше святое братство имеет действительный смысл в жизни; всё остальное есть сон, – говорил Пьер. – Вы поймите, мой друг, что вне этого союза всё исполнено лжи и неправды, и я согласен с вами, что умному и доброму человеку ничего не остается, как только, как вы, доживать свою жизнь, стараясь только не мешать другим. Но усвойте себе наши основные убеждения, вступите в наше братство, дайте нам себя, позвольте руководить собой, и вы сейчас почувствуете себя, как и я почувствовал частью этой огромной, невидимой цепи, которой начало скрывается в небесах, – говорил Пьер.
