Реализация Белевичем идеальной 6-портовой конференц-сети- Реализация Белевичем идеальной 10-портовой конференц-сети
В математике конференц-матрица ( также называемая C - матрицей ) — это квадратная матрица C с 0 на диагонали и +1 и −1 вне диагонали, такая, что C T C является кратным единичной матрицы I. Таким образом, если матрица имеет порядок n , C T C = ( n −1) I. Некоторые авторы используют более общее определение, которое требует, чтобы в каждой строке и столбце был один 0, но не обязательно на диагонали. [1] [2]
Матрицы конференций впервые возникли в связи с проблемой в телефонии . [3] Впервые они были описаны Витольдом Белевичем , который также дал им название. Белевич интересовался построением идеальных сетей телефонных конференций из идеальных трансформаторов и обнаружил, что такие сети представляются матрицами конференций, отсюда и название. [4] Другие приложения находятся в статистике , [5] и еще одно в эллиптической геометрии . [6]
Для n > 1 существует два вида конференц-матриц. Давайте нормализуем C , сначала (если используется более общее определение), переставив строки так, чтобы все нули были на диагонали, а затем отрицая любую строку или столбец, первый элемент которых отрицателен. (Эти операции не меняют того, является ли матрица конференц-матрицей.) Таким образом, нормализованная конференц-матрица имеет все 1 в своей первой строке и столбце, за исключением 0 в верхнем левом углу, и равна 0 на диагонали. Пусть S будет матрицей, которая остается, когда удаляются первая строка и столбец C. Тогда либо n является четно-четным (кратным 4), а S является кососимметричной (как нормализованная C , если ее первая строка отрицательна), либо n является нечетно-четным ( конгруэнтным 2 по модулю 4), а S является симметричной (как нормализованная C ).
Если C — симметричная конференц-матрица порядка n > 1, то не только n должно быть сравнимо с 2 mod 4, но и n − 1 должно быть суммой двух квадратов ; [7] есть остроумное доказательство с помощью элементарной теории матриц у ван Линта и Зейделя. [6] n всегда будет суммой двух квадратов, если n − 1 — степень простого числа . [8]
При наличии симметричной конференц-матрицы матрицу S можно рассматривать как матрицу смежности Зейделя графа . Граф имеет 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 ); для каждого из них известно, что существует симметричная матрица конференций этого порядка. Приказ 66, похоже, остается нерешенной проблемой .
По сути уникальная матрица конференций порядка 6 имеет вид
Все остальные матрицы конференций порядка 6 получаются из этой путем изменения знаков некоторой строки и/или столбца (и путем перестановки строк и/или столбцов, согласно используемому определению).
Кососимметричные матрицы также могут быть получены с помощью конструкции Пейли. Пусть q будет степенью простого числа с остатком 3 mod 4. Тогда есть орграф Пейли порядка q , который приводит к кососимметричной матрице конференции порядка n = q + 1. Матрица получается путем взятия в качестве S матрицы q × q , которая имеет +1 в позиции ( i , j ) и −1 в позиции ( j , i ), если есть дуга орграфа от i до j и нулевая диагональ. Тогда C, построенная, как указано выше, из S , но с первой строкой, полностью отрицательной, является кососимметричной матрицей конференции.
Эта конструкция решает лишь малую часть проблемы определения, для каких четных чисел n существуют кососимметричные конференц-матрицы порядка n .
Иногда конференц-матрица порядка n определяется просто как матрица взвешивания вида W ( n, n −1), где W ( n,w ) считается имеющей вес w > 0 и порядок n, если это квадратная матрица размера n с элементами из {−1, 0, +1}, удовлетворяющая W W T = w I . [2] Используя это определение, нулевой элемент больше не обязан находиться на диагонали, но легко видеть, что по-прежнему должен быть ровно один нулевой элемент в каждой строке и столбце. Например, матрица
удовлетворяет этому смягченному определению, но не более строгому, требующему, чтобы нулевые элементы находились на диагонали.
Конференц-дизайн — это обобщение конференц-матриц до непрямоугольных матриц. Конференц-дизайн C — это матрица с элементами из {−1, 0, +1}, удовлетворяющая , где — единичная матрица и не более одного нуля в каждой строке. Складывающиеся дизайны конференц-дизайнов могут использоваться в качестве окончательных дизайнов скрининга. [9] [10]
Белевич получил полные решения для матриц конференций для всех значений n до 38 и предоставил схемы для некоторых меньших матриц. Идеальная сеть конференций — это та, в которой потеря сигнала полностью обусловлена разделением сигнала между несколькими портами абонентов конференции. То есть в сети нет потерь на рассеивание. Сеть должна содержать только идеальные трансформаторы и никаких сопротивлений. Идеальная сеть конференций с n -портами существует тогда и только тогда, когда существует матрица конференций порядка n . Например, сеть конференций с 3 портами может быть построена с помощью хорошо известной гибридной трансформаторной схемы, используемой для преобразования 2-проводной в 4-проводную в телефонных трубках и линейных ретрансляторах. Однако матрицы конференций порядка 3 не существует, и эта схема не создает идеальную сеть конференций. Для согласования необходимо сопротивление, которое рассеивает сигнал, иначе сигнал теряется из-за несоответствия. [11]
Как упоминалось выше, необходимым условием существования матрицы конференций является то, что n −1 должно быть суммой двух квадратов. Если существует более одной возможной суммы двух квадратов для n −1, то будет существовать несколько существенно различных решений для соответствующей сети конференций. Такая ситуация возникает при n 26 и 66. Сети особенно просты, когда n −1 является полным квадратом ( n = 2, 10, 26, ...). [12]