Matrice de Costas

Un tableau de Costas de taille huit. Si les points sont interprétés comme des tours sur un échiquier, ils ne peuvent pas se prendre mutuellement (Taylor et Dinitz 2007).

En mathématiques, une matrice de Costas ou tableau de Costas, est un ensemble de $n$ points disposés sur une grille régulière de telle sorte que chaque ligne et chaque colonne ne contient qu'un seul point, et tels que les $n(n-1)/2$ segments de droite reliant deux points sont tous différents en longueur ou en pente.

Ces propriétés rendent les tableaux utiles dans des applications comme le sonar ou le radar. Les tableaux de Costas peuvent être considérés comme des versions bidimensionnelles de la règle de Golomb et, en plus de leur intérêt mathématique, ont des applications similaires dans les plans d'expérience et l’ingénierie des antennes réseau à commande de phase.

Les tableaux de Costas sont nommés ainsi d'après John P. Costas (en), un ingénieur en électrotechnique, qui les a étudiés en premier dans un rapport technique écrit en 1965. Indépendamment, Edgar Gilbert a également écrit un article sur ces objets la même année dans une étude sur les carrés latins, et a publié ce qui est maintenant connu comme la méthode de Welch logarithmique pour la construction de matrices de Costas.

Représentation numérique

Une matrice de Costas est une matrice carrée binaire, où le 1 resp. 0 est interprété comme la présence resp. l'absence d'un point, vérifiant les deux conditions suivantes :

1. il n'y a qu'un seul point par ligne et par colonne ;
2. les segments de droite joignant les paires de points sont deux-à-deux différents en longueur ou en pente.

La première des conditions signifie qu'une matrice de Costas est une matrice de permutation. Ainsi, les matrices de Costas de $n$ points sont un sous-ensemble de l'ensemble des matrices de permutation d'ordre $n$. La deuxième condition peut aussi s'exprimer en disant que les vecteurs de déplacements entre paires de points sont deux-à-deux distincts.

Une matrice peut être décrite par une suite de couples d'indices qui spécifient la ligne et la colonne pour chaque entrée non nulle ; comme il n'y a qu'un point par colonne, une matrice peut-être représentée par une suite unidimensionnelle. Prenons par exemple la matrice suivante, qui est une matrice de Costas d'ordre 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}}$    ou plus simplement     ${\begin{array}{|c|c|c|c|}\hline &&&\bullet \\\hline &&\bullet &\\\hline \bullet &&&\\\hline &\bullet &&\\\hline \end{array}}$

Les points se trouvent en positions (3,1), (4,2), (2,3), (1,4). Et comme il n'y a qu'une entrée non nulle par colonne, il suffit de donner la suite des indices de lignes, dans notre cas la suite (3,4,2,1). Ceci définit une permutation.

De manière générale, la suite des indices de lignes d'une matrice de Costas d'ordre $n$ définit une permutation des entiers de $1$ à $n$ ; si on la note $X$, cette permutation la propriété que les couples

$(p-q,X(p)-X(q))$,

pour $p\neq q$ entre $1$ et $n$, sont deux-à-deux distincts. En cela, les matrices de Costas généralisent les permutations à différences distinctes qui, elles, satisfont à la propriété que les différences

$X(q+1)-X(q)$

pour $1\leq q<n$ sont toutes distincts. Citons Sterling : « Gilbert cherchait des carré latins le plus irréguliers possibles, en ce sens que des paires de lettres identiques ne se répètent pas à distances égales sur deux lignes. Par exemple, le carré latin

${\begin{matrix}A&B&C&D\\D&A&B&C\\C&D&A&B\\B&C&D&A\\\end{matrix}}$

n'est pas bon parce que le couple $AB$ se répète en trois lignes, et $BC$ de même. Gilbert écrit dans son article : « Les éléments dans un carré latin représentent des stimuli qui sont présentés à un sujet dans une séquence temporelle... Chaque ligne ou colonne d'un carré latin peut donner un ordre approprié de présentation. Mais si l'expérience doit être répétée plusieurs fois, le lignes du carré doivent se ressembler le moins possible. Si un stimulus peut influencer la réponse du sujet au stimulus suivant, alors deux ordres de présentation ne doivent pas répéter la même paire de stimuli consécutivement. » C'est pourquoi on cherche à construire des carrés latins où chaque paire de lettres adjacentes n'apparaît qu'une fois au plus horizontalement, et une fois au plus verticalement. Gilbert résout ce problème en construisant ce qu'on appelle un carré additif, à partir de deux permutations avec des différences distinctes. Les permutations des matrices de Costas en sont une extension.

La généralisation des permutations à différences distinctes demande que pour chaque $h>0$, et pas seulement pour $h=1$, les différences

$X(p+h)-X(p)$

soient deux-à-deux distinctes, pour tous les $p$, formellement :

si $p\neq q$, alors $X(p+h)-X(p)\neq X(q+h)-X(q)$ pour $h>0$.

L'exemple suivant figure dans (Arce-Nazario et Ortiz-Ubarri 2012): La permutation $X$ donnée par (1 3 2 5 6 4) correspond à la matrice :

${\begin{array}{|c|c|c|c|c|c|}\hline \bullet &&&&&\\\hline &&\bullet &&&\\\hline &\bullet &&&&\\\hline &&&&&\bullet \\\hline &&&\bullet &&\\\hline &&&&\bullet &\\\hline \end{array}}$

Pour chaque $h$, les différences $X(p+h)-X(p)$ doivent être toutes distinctes. Ces différences sont :

• pour $h$=1 : 2 –1 3 1 –2
• pour $h$=2 : 1 2 4 -1
• pour $h$=3 : 4 3 2
• pour $h$=4 : 5 1
• pour $h$=5 : 3

Il n'y a jamais deux nombres égaux dans une ligne, la matrice est donc une matrice de Costas.

Tableaux de Costas connus

Tous les tableaux de Costas sont connus jusqu'à la taille 29 . Des matrices de Costas sont connues pour une infinité de tailles. On ne sait pas si des matrices de Costas existent pour toutes les tailles. Actuellement, les plus petites tailles pour lesquelles on ne connaît pas de tableaux sont 32 et 33.

Il existe deux méthodes principales pour construire ces tableaux. Ces méthodes sont connues sous le nom méthodes de génération de Welch et de Lempel-Golomb, et utilisent des concepts de la théorie de corps finis.

La table suivante donne toutes les matrices de taille inférieure ou égale à 5. Une liste complète des matrices pour les tailles qui ont été testées de manière exhaustive est disponible en ligne.

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} {4,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}

Les 12 matrices de Costas d'ordre 4. Elles sont groupées par classes d'équivalence du groupe diédral. La première classe, rouge, a 4 éléments, la deuxième, verte, en a 8.

Un certain nombre de symétries existent pour les matrices de Costas qui permettent de les grouper en classes. Par exemple, une rotation d'une matrice de Costas donne encore une matrice de Costas, et une réflexion également. En d'autres termes, l'action du groupe diédral $D_{2}$ préserve les matrices de Costas. Dans l'exemple des matrices d'ordre 4, dont la liste est donné dans la figure, les quatre premières matrices sont fermées par rotation (et par réflexion, mais comme elles sont symétriques par rapport à la diagonale, cela ne produit pas de nouvel élément). Les huit matrices suivantes forment une deuxième classe. Avec (Taylor et Dinitz 2007), dont sont tirés ces diagrammes, notons le nombre de matrices de taille de taille $n$ par $C(n)$, le nombre de classes d'équivalence par le groupe diédral par $c(n)$, et $s(n)$ le nombre de ces classes formées de matrices symétriques par rapport à la diagonale. On a donc $C(4)=12$, $c(4)=2$ et $s(4)=1$. En général, pour $n>2$,

$C(n)=8c(n)-4s(n)$.

Constructions

Méthode de Welch

Une matrice de Welch-Costas, ou simplement une matrice de Welch, est une matrice de Costas engendrée en utilisant la méthode décrite ci-dessous. Cette méthode a d'abord été décrite par Edgar Gilbert in 1965 et redécouverte par Lloyd R. Welch (en) en 1982. Dans cette méthode, on choisit une racine primitive $g$ d'un nombre premier $p$ (c'est un entier tel que toutes les puissances $g^{m}$, pour $1\leq m\leq p-1$ sont distinctes modulo $p$). On définit une matrice $A$ de taille $n=p-1$ par

$A_{i,j}={\begin{cases}1&{\text{si }}i\equiv g^{j}{\pmod {p}}\\0&{\text{sinon. }}\end{cases}}$

Dans la notation en permutation, la suite $(g,g^{2},\ldots ,g^{p-1})$ est la notation de la transposée de la matrice A.

Exemple

3 est une racine primitive pour 5, et on a $3^{1}=3,3^{2}=9=4{\bmod {5}},3^{3}=27=2{\bmod {5}},3^{4}=81=1{\bmod {5}}$. D'après la construction, (3 4 2 1) est une matrice de Costas. Cette matrice est appelée la matrice de Welch exponentielle, et sa transposée une matrice de Welch logarithmique.

Le nombre de matrices de Welch-Costas que l'on peut construire de cette manière est égal au nombre de racines primitives pour un nombre premier. Ce nombre est égal à $\varphi (p-1)$ pour un nombre premier $p$, où $\varphi$ est l'indicatrice d'Euler.

Méthode de Lempel-Golomb

La construction de Lempel-Golomb utilise deux éléments primitifs $\alpha$ et $\beta$ d'un corps fini $\mathbf {F} _{q}$ et définit, de manière semblable à la façon précédente, une matrice par :

$A_{i,j}={\begin{cases}1&{\text{si }}\alpha ^{i}+\beta ^{j}=1\\0&{\text{sinon. }}\end{cases}}$

Le résultat est une matrice de Costas de taille $q-2$. On distingue en fait la construction de Lempel de la construction de Golomb : la construction de Lempel est celle de Golomb pour $\beta =\alpha$, donc ne prend qu'un seul élément primitif.

Si $\alpha +\beta =1$, on peut supprimer la première ligne et la première colonne, et on obtient une autre matrice de Costas, de taille q-3. On peut toujours choisir une paire d'éléments primitifs avec cette propriété additionnelle pour toute puissance de nombre premier $q>2$.

Variantes

Diverses variantes des tableaux de Costas ont été introduites. Citons les Honeycomb Costas arrays ou tableaux de Costas alvéolaires: Ce sont des matrices de Costas de taille impaire $2r+1$ qui ont la propriété supplémentaire que les couples $(i,j)$ contenant un point prennent toutes les valeurs, de $-r$ à $r$, une fois et une seule. Un exemple d'un telle matrice est donné par la permutation (1,3,6,2,7,5,4). La suite des différences est : (0,-1,-3,2,-2,1,3). Elles tirent leur nom d'une transformation cisaillement qui permet de les représenter sur une grille hexagonale

On a aussi considéré le problème des huit dames et ses variantes. Il n'a a pas de solution au problème des huit dames qui soit un tableau de Costas de taille 8. On peut en revanche poser 9 dames qui ne peuvent se prendre mutuellement sur une grille de taille 10. Le problème des rois qui ne peuvent se prendre est plus facile à résoudre. Il s'agit de place des points sur une grille de sorte que la distance de Manhattan entre deux points (le nombre de cases à parcourir pour aller d'un point à un autre) soit au moins égal à 3. On peut placer seize rois sur un échiquier traditionnel, et on peut en place huit qui forment un tableau de Costas. C'est l'exemple reproduit au début de cet article.

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Costas array » (voir la liste des auteurs).

Bibliographie

• Rafael A. Arce-Nazario et José Ortiz-Ubarri, « Multidimensional Costas Arrays and Their Enumeration Using GPUs and FPGAs », International Journal of Reconfigurable Computing, vol. 2012, n^o article : 196761, 9 pages,‎ 2012 (DOI 10.1155/2012/196761, lire en ligne)

• Lionel Barker, Konstantinos Drakakis et Scott Rickard, « On the complexity of the verification of the Costas property », Proceedings of the IEEE, vol. 97, n^o 3,‎ 2009, p. 586–593 (DOI 10.1109/JPROC.2008.2011947, lire en ligne).

• James K. Beard, John C. Russo, Keith Erickson, Michael Monteleone et Mike Wright, « Combinatoric collaboration on Costas arrays and radar applications », dans IEEE Radar Conference, Philadelphia, Pennsylvania, 2004 (DOI 10.1109/NRC.2004.1316432, lire en ligne), p. 260–265.

• John P. Costas, Medium constraints on sonar design and performance, G.E. Corporation, coll. « Class 1 Report R65EMH33 », 1965

• John P. Costas, « A study of a class of detection waveforms having nearly ideal range-Doppler ambiguity properties », Proceedings of the IEEE, vol. 72, n^o 8,‎ 1984, p. 996–1009 (DOI 10.1109/PROC.1984.12967, lire en ligne [archive du 30 septembre 2011]).

• Konstantinos Drakakis, Francesco Iorio, Scott Rickard et John Walsh, « Results of the enumeration of Costas arrays of order 29 », Advances in Mathematics of Communications, vol. 5, n^o 3,‎ août 2011, p. 547 - 553 (ISSN 1930-5338, DOI 10.3934/amc.2011.5.547, lire en ligne)

• Edgar N. Gilbert, « Latin squares which contain no repeated digrams », SIAM Review, vol. 7,‎ 1965, p. 189–198 (DOI 10.1137/1007035, MR 0179095).

• Solomon W. Golomb et Herbert Taylor, « Construction and properties of Costas arrays », Proceedings of the IEEE, vol. 72, n^o 9,‎ 1984, p. 1143–1163 (DOI 10.1109/PROC.1984.12994, lire en ligne [archive du 30 septembre 2011]).

• (en) Richard K. Guy, Unsolved Problems in Number Theory, New York, Springer Verlag, 2004, 3^e éd., 437 p. (ISBN 0-387-20860-7, lire en ligne), p. 200 et 377, Sections C18 et F9.

• Oscar Moreno, « Survey of results on signal patterns for locating one or multiple targets », dans Alexander Pott, P. Vijay Kumar, Tor Helleseth et Dieter Jungnickel (éditeurs), Difference Sets, Sequences and Their Correlation Properties, Kluwer, coll. « NATO Advanced Science Institutes Series » (n^o 542), 1999 (ISBN 0-7923-5958-5), p. 353-368.

• Herbert Taylor et Jeffrey H. Dinitz, « Part VI. Chapter 9 - Costas Array », dans Charles J. Colburn et Jeffrey H. Dinitz (éditeurs), Handbook of Combinatoiral Designs, Chapmand & Hall/CRC, coll. « Discrete Mathematics and its Applications », 2007, 2^e éd. (ISBN 978-1584885061), p. 357-361

Articles connexes

• Problème des huit dames
• Permutation
• Groupe diédral
• Design combinatoire

Liens externes

• Site consacré aux matrices de Costas.
• Dans l'encyclopédie en ligne des suites de nombres entiers (OEIS), deux suites concernent les matrices Costas:

A008404 : Nombre de matrices de Costas d'ordre n, en comptant aussi les matrices obtenues par rotation et réflexion, noté plus haut $C(n)$.

A001441 : Nombre de matrices de Costas d'ordre n inéquivalentes sous l'action du groupe diédral, noté plus haut $c(n)$.