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.

Representación numérica

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:

{\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

{\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.

Matrices conocidas

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] $C(n)$ ${\estilo de visualización n}$ $C(n)/n!\leq e^{-\Theta (n)}$

Construcciones

Gallo

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. $A_{i,j}=1$ $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 .

Lempel-Golomb

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 . $A_{i,j}=1$ $\alpha ^{i}+\beta ^{j}=1$

Extensiones de Taylor, Lempel y Golomb

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.

Otros métodos

^{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]

Variantes

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]

Véase también

Notas

^ Costas (1965); Gilbert (1965); Un descubrimiento independiente de los conjuntos de Costas, Aaron Sterling, 9 de octubre de 2011.
^ Barba (2006); Drakakis et al. (2008); Drakakis, Iorio y Rickard (2011); Drakakis et al. (2011)
^ Barba (2006).
^ Barba (2008).
^ Beard (2017); Beard, James K., Archivos para descargar: Costas Arrays , consultado el 20 de abril de 2020
^ Warnke, Correll y Swanson (2023).
^ Golomb (1984).
^ Golomb y Taylor (1984).
^ Golomb (1992).
^ Rickard (2004).
^ Barba y otros (2007).
^ Blackburn, Simon R.; Panoui, Anastasia; Paterson, Maura B.; Stinson, Douglas R. (10 de diciembre de 2010). "Matrices en forma de panal". Revista Electrónica de Combinatoria . 17 : R172. doi : 10.37236/444 . ISSN 1077-8926.

Referencias

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.

Enlaces externos

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]