Matriz de conferencias

En matemáticas , una matriz de conferencia (también llamado C - matriz ) es un cuadrado matriz C con 0 en la diagonal y 1 y -1 fuera de la diagonal, de manera que C ^T C es un múltiplo de la matriz de identidad I . Por lo tanto, si la matriz tiene orden n , C ^T C  = ( n -1) I . Algunos autores usan una definición más general, que requiere que haya un solo 0 en cada fila y columna, pero no necesariamente en la diagonal. ^{[1] [2]}

Las matrices de conferencias surgieron por primera vez en relación con un problema de telefonía . ^[3] Fueron descritos por primera vez por Vitold Belevitch , quien también les dio su nombre. Belevitch estaba interesado en construir redes de conferencias telefónicas ideales a partir de transformadores ideales y descubrió que tales redes estaban representadas por matrices de conferencias, de ahí el nombre. ^[4] Otras aplicaciones están en estadística , ^[5] y otra en geometría elíptica . ^[6]

Para n  > 1, hay dos tipos de matriz de conferencia. Normalicemos C , primero (si se usa la definición más general), reorganizando las filas para que todos los ceros estén en la diagonal, y luego negando cualquier fila o columna cuya primera entrada sea negativa. (Estas operaciones no cambian si una matriz es una matriz de conferencia). Por lo tanto, una matriz de conferencia normalizada tiene todos unos en su primera fila y columna, excepto un 0 en la esquina superior izquierda, y es 0 en la diagonal. Sea S la matriz que queda cuando se eliminan la primera fila y columna de C. Entonces n es uniformemente par (un múltiplo de 4) y S es antisimétrico(como es el normalizado C si su primera fila es negado), o n es extrañamente incluso (congruente a 2 módulo 4) y S es simétrica (como es el normalizado C ).

Matrices de conferencia simétricas

Si C es una matriz de conferencia simétrica de orden n  > 1, entonces n no solo debe ser congruente con 2 (mod 4) sino que también n - 1 debe ser una suma de dos enteros cuadrados; ^[7] hay una prueba inteligente mediante la teoría de matrices elementales en van Lint y Seidel. ^[6] n siempre será la suma de dos cuadrados si n - 1 es una potencia prima . ^[8]

Dada una matriz de conferencia simétrica, la matriz S puede verse como la matriz de adyacencia de Seidel de un gráfico . La gráfica tiene n - 1 vértices, correspondientes a las filas y columnas de S , y dos vértices son adyacentes si la entrada correspondiente en S es negativa. Este gráfico es muy regular del tipo llamado (después de la matriz) un gráfico de conferencia .

La existencia de matrices de conferencia de órdenes n permitidas por las restricciones anteriores se conoce solo para algunos valores de n . Por ejemplo, si n = q + 1 donde q es una potencia prima congruente con 1 (mod 4), entonces los gráficos de Paley proporcionan ejemplos de matrices de conferencia simétricas de orden n , tomando S como la matriz de Seidel del gráfico de Paley. Los primeros órdenes posibles de una matriz de conferencia simétrica son n = 2, 6, 10, 14, 18, (no 22, ya que 21 no es una suma de dos cuadrados), 26, 30, (no 34 ya que 33 no es un suma de dos cuadrados), 38, 42, 46, 50, 54, (no 58), 62 (secuencia A000952en la OEIS ); para cada uno de ellos, se sabe que existe una matriz de conferencia simétrica de ese orden. La orden 66 parece ser un problema abierto.

Ejemplo

La matriz de conferencia esencialmente única de orden 6 viene dada por

${\displaystyle {\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}}}$,

todas las demás matrices de conferencia de orden 6 se obtienen a partir de ésta volteando los signos de alguna fila y / o columna (y tomando permutaciones de filas y / o columnas, según la definición en uso).

Matrices de conferencia antisimétricas

También se pueden producir matrices antisimétricas mediante la construcción de Paley. Sea q una potencia prima con residuo 3 (mod 4). Luego hay un dígrafo de Paley de orden q que conduce a una matriz de conferencia antisimétrica de orden n = q + 1. La matriz se obtiene tomando para S la matriz q × q que tiene un +1 en la posición ( i, j ) y −1 en la posición ( j, i ) si hay un arco del dígrafo de i a j , y diagonal cero. Entonces C construido como arriba a partir de S, pero con la primera fila totalmente negativa, es una matriz de conferencia antisimétrica.

Esta construcción resuelve sólo una pequeña parte del problema de decidir para qué números pares n existen matrices de conferencia antisimétricas de orden n .

Generalizaciones

A veces, una matriz de conferencia de orden n se define simplemente como una matriz de ponderación de la forma W ( n, n −1), donde se dice que W ( n, w ) tiene un peso w > 0 y un orden n si es un cuadrado matriz de tamaño n con las entradas de {-1, 0, +1} satisfacer WW ^t = w I . ^[2] Usando esta definición, ya no se requiere que el elemento cero esté en la diagonal, pero es fácil ver que aún debe haber exactamente un elemento cero en cada fila y columna. Por ejemplo, la matriz

${\displaystyle {\begin{pmatrix}1&0&1&1\\0&-1&-1&1\\1&-1&0&-1\\1&1&-1&0\end{pmatrix}}}$

satisfaría esta definición relajada, pero no la más estricta que requiere que los elementos cero estén en la diagonal.

Un diseño de conferencia es una generalización de matrices de conferencia a matrices no rectangulares. Un diseño de conferencia C es una matriz, con entradas de {-1, 0, +1} satisfactorias , donde está la matriz de identidad y como máximo un cero en cada fila. Los diseños plegables de los diseños de conferencias se pueden utilizar como diseños de proyección definitivos. ^{[9] [10]}${\displaystyle N\times k}$${\displaystyle W^{T}W=(N-1)I_{k}}$${\displaystyle I_{k}}$${\displaystyle k\times k}$

Circuitos de conferencias telefónicas

La trivial red de conferencias de 2 puertos

Belevitch obtuvo soluciones completas para matrices de conferencia para todos los valores de n hasta 38 y proporcionó circuitos para algunas de las matrices más pequeñas. Una red de conferencias ideal es aquella en la que la pérdida de señal se debe por completo a que la señal se divide entre varios puertos de suscriptores de conferencias. Es decir, no hay pérdidas por disipación dentro de la red. La red debe contener solo transformadores ideales y sin resistencias. Existe una red de conferencias ideal de n puertos si y solo si existe una matriz de conferencias de orden n . Por ejemplo, se puede construir una red de conferencias de 3 puertos con el conocido transformador híbridocircuito utilizado para la conversión de 2 hilos a 4 hilos en teléfonos y repetidores de línea. Sin embargo, no existe una matriz de conferencias de orden 3 y este circuito no produce una red de conferencias ideal . Se necesita una resistencia para la coincidencia que disipa la señal, o de lo contrario la señal se pierde por falta de coincidencia. ^[11]

• Implementación de Belevitch de la red de conferencias ideal de 6 puertos

• Implementación de Belevitch de la red de conferencias ideal de 10 puertos

Como se mencionó anteriormente, una condición necesaria para que exista una matriz de conferencia es que n −1 debe ser la suma de dos cuadrados. Donde hay más de una posible suma de dos cuadrados para n −1, existirán múltiples soluciones esencialmente diferentes para la red de conferencias correspondiente. Esta situación ocurre en n de 26 y 66. Las redes son particularmente simples cuando n −1 es un cuadrado perfecto ( n = 2, 10, 26,…). ^[12]

Notas

1. Greig Malcolm (2006). "Sobre la coexistencia de matrices de conferencias y diseños de 2- (2k + 1, k, k-1) casi resolubles" . Revista de Teoría Combinatoria, serie A . 113 (4): 703–711. doi : 10.1016 / j.jcta.2005.05.005 .
2. Gropp Harald (2004). "Más sobre matrices orbitales". Notas electrónicas en matemáticas discretas . 17 : 179-183. doi : 10.1016 / j.endm.2004.03.036 .
3. Belevitch, págs. 231-244.
4. Colbourn y Dinitz, (2007), p. 19
   van Lint y Wilson, (2001),p. 98
   Stinson, (2004), p. 200
5. Raghavarao, D. (1959). "Algunos diseños de pesaje óptimos" . Anales de estadística matemática . 30 (2): 295-303. doi : 10.1214 / aoms / 1177706253 . Señor 0104322 . 
6. van Lint JH, Seidel JJ (1966). "Conjuntos de puntos equiláteros en geometría elíptica". Indagationes Mathematicae . 28 : 335–348.
7. Belevitch, p.240
8. Stinson, p.78
9. Xiao y col. (2012)
10. Schoen y col. (2018)
11. Belevitch, págs. 240-242
12. Belevitch, p. 242

Referencias

• Belevitch V (1950). "Teoría de 2 redes de terminales n con aplicaciones a la telefonía de conferencias". Comunicación eléctrica . 27 : 231–244.
• Goethals JM, Seidel JJ (1967). "Matrices ortogonales con diagonal cero". Revista Canadiense de Matemáticas . 19 : 1001-1010. doi : 10.4153 / cjm-1967-091-8 .
• Lili Xiao y Dennis KJ Lin y Fengshan Bai (2012). "Construcción de diseños de cribado definitivo utilizando matrices de conferencia". Revista de tecnología de calidad . 44 (1): 2–8. doi : 10.1080 / 00224065.2012.11917877 .
• Seidel, JJ (1991), ed. DG Corneil y R. Mathon, Geometría y combinatoria: obras seleccionadas de JJ Seidel . Boston: Prensa académica. Varios de los artículos están relacionados con matrices de conferencias y sus gráficos.
• Colbourn, Charles J .; Dinitz, Jeffrey H. (2007) Manual de diseños combinatorios , Boca Raton, Florida: Chapman y Hall / CRC Press, ISBN 1-58488-506-8 . 
• van Lint, Jacobus Hendricus; Wilson, Richard Michael (2001) Un curso de combinatoria , Cambridge: Cambridge University Press, ISBN 0-521-00601-5 . 
• Stinson, Douglas Robert (2004) Diseños combinatorios: Construcciones y análisis , Nueva York: Springer, ISBN 0-387-95487-2 . 
• Eric D. Schoen, Pieter T. Eendebak, Peter Goos (2018). "Un criterio de clasificación para diseños de cribado definitivo". Annals of Statistics .

Otras lecturas

• NA Balonin, Jennifer Seberry, "Una revisión y nuevas matrices de conferencias simétricas" , Investigación en línea , Universidad de Wollongong, 2014. El apéndice enumera todas las matrices de conferencias conocidas y posibles hasta 1002.