Matriz de Costas

En matemáticas, una matriz Costas puede considerarse geométricamente como un conjunto de n puntos, cada uno en el centro de un cuadrado en un mosaico de cuadrados n × n de modo que cada fila o columna contiene solo un punto, y todos los n ( n  − 1)/2 vectores de desplazamiento entre cada par de puntos son distintos. Esto da como resultado una función de autoambigüedad de "chincheta" ideal , lo que hace que las matrices sean útiles en aplicaciones como el sonar y el radar . Las matrices Costas pueden considerarse como primos bidimensionales de la construcción de la regla de Golomb unidimensional y, además de ser de interés matemático, tienen aplicaciones similares en el diseño experimental y la ingeniería de radares de matriz en fase .

Las matrices Costas reciben su nombre de John P. Costas , quien escribió sobre ellas por primera vez en un informe técnico de 1965. De forma independiente, Edgar Gilbert también escribió sobre ellas ese mismo año, publicando lo que ahora se conoce como el método logarítmico de Welch para construir matrices Costas. ^[1] La enumeración general de matrices Costas es un problema abierto en informática y encontrar un algoritmo que pueda resolverlo en tiempo polinomial es una pregunta de investigación abierta.

Una matriz Costas puede representarse numéricamente como una matriz de números n × n , donde cada entrada es 1, para un punto, o 0, para la ausencia de un punto. Cuando se interpretan como matrices binarias , estas matrices de números tienen la propiedad de que, dado que cada fila y columna tiene la restricción de que solo tiene un punto en ella, también son matrices de permutación . Por lo tanto, las matrices Costas para cualquier n dado son un subconjunto de las matrices de permutación de orden n .

Las matrices se describen generalmente como una serie de índices que especifican la columna de cualquier fila. Dado que se sabe que cualquier columna tiene solo un punto, es posible representar una matriz unidimensionalmente. Por ejemplo, la siguiente es una matriz Costas válida de orden N  = 4:

${\displaystyle {\begin{array}{|c|c|c|c|}\hline 0&0&0&1\\\hline 0&0&1&0\\\hline 1&0&0&0\\\hline 0&1&0&0\\\hline \end{array}}}$    o simplemente     ${\displaystyle {\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}}$

Hay puntos en las coordenadas: (1,2), (2,1), (3,3), (4,4)

Como la coordenada x aumenta linealmente, podemos escribir esto en forma abreviada como el conjunto de todas las coordenadas y . La posición en el conjunto sería entonces la coordenada x . Observe: {2,1,3,4} describiría la matriz mencionada anteriormente. Esto define una permutación. Esto facilita la comunicación de las matrices para un orden dado de N.

Los recuentos de la matriz Costas se conocen para los órdenes 1 a 29 ^[2] (secuencia A008404 en la OEIS ):

A continuación se muestran algunas matrices conocidas: N = 1 {1}

N = 2 {1,2} {2,1}

N = 3 {1,3,2} {2,1,3} {2,3,1} {3,1,2}

N = 4 {1,2,4,3} {1,3,4,2} {1,4,2,3} {2,1,3,4} {2,3,1,4} {2,4,3,1} {3,1,2,4} {3,2,4,1} {3,4,2,1} {4,1,3,2} {4,2,1,3} {4,3,1,2}

N = 5 {1,3,4,2,5} {1,4,2,3,5} {1,4,3,5,2} {1,4,5,3,2} {1,5,3,2,4} {1,5,4,2,3} {2,1,4,5,3} {2,1,5,3,4} {2,3,1,5,4} {2,3,5,1,4} {2,3,5,4,1} {2,4,1,5,3} {2,4,3,1,5} {2,5,1,3,4} {2,5,3,4,1} {2,5,4,1,3} {3,1,2,5,4} {3,1,4,5,2} {3,1,5,2,4} {3,2,4,5,1} {3,4,2,1,5} {3,5,1,4,2} {3,5,2,1,4} {3,5,4,1,2} {4,1,2,5,3} {4,1,3,2,5} {4,1,5,3,2} {4,2,3,5,1} {4,2,5,1,3} {4,3,1,2,5} {4,3,1,5,2} {4,3,5,1,2} ,5,1,3,2} {4,5,2,1,3} {5,1,2,4,3} {5,1,3,4,2} {5,2,1,3,4} {5,2,3,1,4} {5,2,4,3,1} {5,3,2,4,1}

N = 6 {1,2,5,4,6,3} {1,2,6,4,3,5} {1,3,2,5,6,4} {1,3,2,6,4,5} {1,3,6,4,5,2} {1,4,3,5,6,2} {1,4,5,3,2,6} {1,4,6,5,2,3} {1,5,3,4,6,2} {1,5,3,6,2,4} {1,5,4,2,3,6} {1,5,4,6,2,3} {1,5,6,2,4,3} {1,5,6,3,2,4} {1,6,2,4,5,3} {1,6,3,2,4,5} {1,6,3,4,2,5} {1,6,3,5,4,2} {1,6,4,3,5,2} {2,3,1,5,4,6} {2,3,5,4,1,6} {2,3,6,1,5,4} {2,4,1,6,5,3} {2,4,3,1,5,6} {2,4,3,6,1,5} {2,4,5,1,6,3} {2,4,5,3,6,1} ,6,3,4} {2,5,1,6,4,3} {2,5,3,4,1,6} {2,5,3,4,6,1} {2,5,4,6,3,1} {2,6,1,4,3,5} {2,6,4,3,5,1} {2,6,4,5,1,3} {2,6,5,3,4,1} {3,1,2,5,4,6} {3,1,5,4,6,2} {3,1,5,6,2,4} {3,1,6,2,5,4} {3,1,6,5,2,4} {3,2,5,1,6,4} {3,2,5,6,4,1} {3,2,6,1,4,5} {3,2,6,4,5,1} ,6,2,5} {3,4,2,6,5,1} {3,4,6,1,5,2} {3,5,1,2,6,4} {3,5,1,4,2,6} {3,5,2,1,6,4} {3,5,4,1,2,6} {3,5,4,2,6,1} {3,5,6,1,4,2} {3,5,6,2,1,4} {3,6,1,5,4,2} {3,6,4,5,2,1} {3,6,5,1,2,4} {4,1,2,6,5,3} {4,1,3,2,5,6} {4,1,6,2,3,5} {4,2,1,5,6,3} {4,2,1,6,3,5} ,5,1,6} {4,2,3,6,5,1} {4,2,5,6,1,3} {4,2,6,3,5,1} {4,2,6,5,1,3} {4,3,1,6,2,5} {4,3,5,1,2,6} {4,3,6,1,5,2} {4,5,1,3,2,6} {4,5,1,6,3,2} {4,5,2,1,3,6} {4,5,2,6,1,3} {4,6,1,2,5,3} {4,6,1,5,2,3} {4,6,2,1,5,3} {4,6,2,3,1,5} {4,6,5,2,3,1} {5,1,2,4,3,6} ,2,6,4} {5,1,3,4,2,6} {5,1,6,3,4,2} {5,2,3,1,4,6} {5,2,4,3,1,6} {5,2,4,3,6,1} {5,2,6,1,3,4} {5,2,6,1,4,3} {5,3,2,4,1,6} {5,3,2,6,1,4} {5,3,4,1,6,2} {5,3,4,6,2,1} {5,3,6,1,2,4} {5,4,1,6,2,3} {5,4,2,3,6,1} {5,4,6,2,3,1} {6,1,3,4,2,5} {6,1,4,2,3,5} ,3,5,2} {6,1,4,5,3,2} {6,1,5,3,2,4} {6,2,1,4,5,3} {6,2,1,5,3,4} {6,2,3,1,5,4} {6,2,3,5,4,1} {6,2,4,1,5,3} {6,2,4,3,1,5} {6,3,1,2,5,4} {6,3,2,4,5,1} {6,3,4,2,1,5} {6,4,1,3,2,5} {6,4,5,1,3,2} {6,4,5,2,1,3} {6,5,1,3,4,2} {6,5,2,3,1,4}

Se encuentran disponibles enumeraciones de matrices Costas conocidas de orden 200, ^[3] orden 500 ^[4] y orden 1030 ^[5] . Aunque es probable que estas listas y bases de datos de estas matrices Costas estén casi completas, es posible que existan otras matrices Costas con órdenes superiores a 29 que no estén en estas listas. En general, el límite superior mejor conocido actualmente para el número de matrices Costas de orden es de forma asintótica . ^[6]${\displaystyle C(n)}$${\estilo de visualización n}$${\displaystyle C(n)/n!\leq e^{-\Theta (n)}}$

Una matriz Welch–Costas , o simplemente matriz Welch, es una matriz Costas generada utilizando el siguiente método, descubierto por primera vez por Edgar Gilbert en 1965 y redescubierto en 1982 por Lloyd R. Welch . La matriz Welch–Costas se construye tomando una raíz primitiva g de un número primo p y definiendo la matriz A por si , en caso contrario 0. El resultado es una matriz Costas de tamaño p  − 1. ${\displaystyle A_{i,j}=1}$${\displaystyle j\equiv g^{i}{\bmod {p}}}$

Ejemplo:

3 es un elemento primitivo módulo 5.

3 ¹ = 3 ≡ 3 (mód 5)

3 ² = 9 ≡ 4 (mód 5)

3 ³ = 27 ≡ 2 (mód 5)

3 ⁴ = 81 ≡ 1 (mód 5)

Por lo tanto, [3 4 2 1] es una permutación de Costas. Más específicamente, se trata de una matriz de Welch exponencial. La transposición de la matriz es una matriz de Welch logarítmica.

La cantidad de matrices Welch-Costas que existen para un tamaño determinado depende de la función totient .

La construcción de Lempel-Golomb toma α y β como elementos primitivos del cuerpo finito GF( q ) y, de manera similar, define si , de lo contrario 0. El resultado es una matriz Costas de tamaño q  − 2. Si α  +  β  = 1, entonces la primera fila y columna se pueden eliminar para formar otra matriz Costas de tamaño q  − 3: tal par de elementos primitivos existe para cada potencia prima q>2 . ${\displaystyle A_{i,j}=1}$${\displaystyle \alpha ^{i}+\beta ^{j}=1}$

La generación de nuevas matrices Costas mediante la adición o sustracción de una fila/columna o dos con un 1 o un par de 1 en una esquina se publicó en un artículo centrado en los métodos de generación ^[7] y en el artículo de referencia de Golomb y Taylor de 1984. ^[8]

En 1992 se publicaron métodos más sofisticados para generar nuevas matrices Costas eliminando filas y columnas de matrices Costas existentes que fueron generadas por los generadores Welch, Lempel o Golomb. ^[9] No existe un límite superior en el orden en el que estos generadores producirán matrices Costas.

^{En 2004 [10]} y 2007 se publicaron dos métodos que encontraron matrices Costas hasta el orden 52 utilizando métodos más complicados de agregar o eliminar filas y columnas. ^[11]

Las matrices de Costas en una red hexagonal se conocen como matrices de panal . Se ha demostrado que solo hay un número finito de matrices de este tipo, que deben tener un número impar de elementos, dispuestos en forma de hexágono. Actualmente, se conocen 12 matrices de este tipo (hasta simetría), lo que se ha conjeturado como el número total. ^[12]

• Permutación
• Grupo diedro
• Diseño combinatorio

• Barker, L.; Drakakis, K.; Rickard, S. (2009), "Sobre la complejidad de la verificación de la propiedad Costas" (PDF) , Actas del IEEE , 97 (3): 586–593, doi :10.1109/JPROC.2008.2011947, S2CID  29776660, archivado desde el original (PDF) el 25 de abril de 2012 , consultado el 10 de octubre de 2011.
• Beard, James (marzo de 2006), "Generación de matrices Costas hasta el orden de 200", 40.ª Conferencia anual de 2006 sobre ciencias y sistemas de la información , IEEE, doi : 10.1109/ciss.2006.286635, S2CID  2241386.
• Beard, James K. (marzo de 2008), "Polinomios generadores de matrices Costas en campos finitos", 42.ª Conferencia Anual de 2008 sobre Ciencias de la Información y Sistemas , IEEE, doi :10.1109/ciss.2008.4558709, S2CID  614347.
• Beard, James K. (2017), Matrices y enumeración de Costas hasta el orden 1030, IEEE Dataport, doi :10.21227/H21P42.
• Beard, J.; Russo, J.; Erickson, K.; Monteleone, M.; Wright, M. (2004), "Colaboración combinatoria en conjuntos Costas y aplicaciones de radar", IEEE Radar Conference, Filadelfia, Pensilvania (PDF) , págs. 260–265, doi :10.1109/NRC.2004.1316432, S2CID  7733481, archivado desde el original (PDF) el 25 de abril de 2012 , consultado el 10 de octubre de 2011.
• Beard, James; Russo, Jon; Erickson, Keith; Monteleone, Michael; Wright, Michael (abril de 2007), "Metodología de búsqueda y generación de matrices Costas", IEEE Transactions on Aerospace and Electronic Systems , 43 (2): 522–538, doi :10.1109/taes.2007.4285351, S2CID  32271456.
• Costas, JP (1965), Restricciones medias en el diseño y el rendimiento del sonar , Informe de clase 1 R65EMH33, GE Corporation
• Costas, JP (1984), "Un estudio de una clase de formas de onda de detección que tienen propiedades de ambigüedad Doppler de rango casi ideales" (PDF) , Actas del IEEE , 72 (8): 996–1009, doi :10.1109/PROC.1984.12967, S2CID  2742217, archivado desde el original (PDF) el 2011-09-30 , consultado el 2011-10-10.
• Drakakis, Konstantinos; Rickard, Scott; Beard, James K.; Caballero, Rodrigo; Iorio, Francesco; O'Brien, Gareth; Walsh, John (octubre de 2008), "Resultados de la enumeración de matrices Costas de orden 27", IEEE Transactions on Information Theory , 54 (10): 4684–4687, doi :10.1109/tit.2008.928979, hdl : 2262/59260.
• Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott (2011), "La enumeración de matrices de Costas de orden 28 y sus consecuencias", Avances en Matemáticas de las Comunicaciones
• Drakakis, Konstantinos; Iorio, Francesco; Rickard, Scott; Walsh, John (agosto de 2011), "Resultados de la enumeración de matrices de Costas de orden 29", Advances in Mathematics of Communications , 5 (3): 547–553, doi : 10.3934/amc.2011.5.547 , hdl : 2262/59260.
• Gilbert, EN (1965), "Cuadrados latinos que no contienen digramas repetidos", SIAM Review , 7 (2): 189–198, doi :10.1137/1007035, MR  0179095.
• Golomb, Solomon W. (1984), "Construcciones algebraicas para matrices Costas", Journal of Combinatorial Theory , Serie A, 37 (1): 13–21, doi :10.1016/0097-3165(84)90015-3, MR  0749508.
• Golomb, Solomon W. (1992), "Las construcciones y para matrices Costas", IEEE Transactions on Information Theory , 38 (4): 1404–1406, doi :10.1109/18.144726, MR  1168761$Estilo de visualización T_{4}$$Estilo de visualización G_{4}$
• Golomb, SW ; Taylor, H. (1984), "Construcción y propiedades de matrices Costas" (PDF) , Actas del IEEE , 72 (9): 1143–1163, doi :10.1109/PROC.1984.12994, S2CID  39718506, archivado desde el original (PDF) el 2011-09-30 , consultado el 2011-10-10.
• Guy, Richard K. (2004), "Secciones C18 y F9", Problemas sin resolver en teoría de números (3.ª ed.), Springer Verlag , ISBN 0-387-20860-7.
• Moreno, Oscar (1999), "Estudio de resultados sobre patrones de señales para la localización de uno o varios objetivos", en Pott, Alexander; Kumar, P. Vijay; Helleseth, Tor; et al. (eds.), Conjuntos de diferencias, secuencias y sus propiedades de correlación , NATO Advanced Science Institutes Series, vol. 542, Kluwer, p. 353, ISBN 0-7923-5958-5.
• Rickard, Scott (2004), "Búsqueda de matrices Costas utilizando propiedades de periodicidad", Conferencia internacional IMA sobre matemáticas en procesamiento de señales.
• Warnke, Lutz; Correll, Bill; Swanson, Christopher (2023), "La densidad de las matrices Costas decae exponencialmente", IEEE Transactions on Information Theory , 69 (1): 575–581, doi :10.1109/TIT.2022.3202507, MR  4544975.

• Desafío del programador MacTech 1999: Matrices Costas
• Enciclopedia en línea de secuencias de números enteros :
  • A008404: Número de matrices Costas de orden n, contando rotaciones y giros como distintos.
  • A001441: Número de matrices de Costas no equivalentes de orden n bajo el grupo diedro.
• "Matriz de Costas", Enciclopedia de Matemáticas , EMS Press , 2001 [1994]