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 Modèle:Harv.

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 Modèle:Lien, 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}{cccc}0& 0& 0& 1\\ 0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 0\end{array}$    ou plus simplement     $\begin{array}{cccc}& & & \bullet \\ & & \bullet & \\ \bullet & & & \\ & \bullet & & \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\ne 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\le 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{array}{cccc}A& B& C& D\\ D& A& B& C\\ C& D& A& B\\ B& C& D& A\end{array}$

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 : Modèle:Citation 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\ne q$, alors $X(p+h)-X(p)\ne X(q+h)-X(q)$ pour $h>0$.

L'exemple suivant figure dans Modèle:Harv: La permutation $X$ donnée par (1 3 2 5 6 4) correspond à la matrice :

$\begin{array}{cccccc}\bullet & & & & & \\ & & \bullet & & & \\ & \bullet & & & & \\ & & & & & \bullet \\ & & & \bullet & & \\ & & & & \bullet & \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 Modèle:Harv, 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 Modèle:Lien 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\le m\le p-1$ sont distinctes modulo $p$). On définit une matrice $A$ de taille $n=p-1$ par

$A_{i,j}=\{\begin{array}{cc}1& \text{si }i\equiv g^j(\mathrm{mod}p)\\ 0& \text{sinon. }\end{array}$

Dans la notation en permutation, la suite $(g,g^2,\dots ,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=4mod5,3^3=27=2mod5,3^4=81=1mod5$. 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 à $\phi (p-1)$ pour un nombre premier $p$, où $\phi$ 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 ${𝐅}_q$ et définit, de manière semblable à la façon précédente, une matrice par :

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

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

Bibliographie

• Modèle:Article

• Modèle:Article.

• Modèle:Chapitre.

• Modèle:Ouvrage

• Modèle:Article.

• Modèle:Article

• Modèle:Article.

• Modèle:Article.

• Modèle:Ouvrage.

• Modèle:Chapitre.

• Modèle:Chapitre

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)$.