Matrice de conférence - Conference matrix

En mathématiques , une matrice de conférence (également appelé C - matrice ) est un carré matrice C à 0 sur la diagonale et +1 et -1 hors de la diagonale, de telle sorte que C ^T C est un multiple de la matrice identité I . Ainsi, si la matrice est d'ordre n , C ^T C  = ( n −1) I . Certains auteurs utilisent une définition plus générale, qui exige qu'il y ait un seul 0 dans chaque ligne et colonne mais pas nécessairement sur la diagonale.

Les matrices de conférence sont d'abord apparues à propos d'un problème de téléphonie . Ils ont été décrits pour la première fois par Vitold Belevitch , qui leur a également donné leur nom. Belevitch s'intéressait à la construction de réseaux de conférence téléphonique idéaux à partir de transformateurs idéaux et a découvert que ces réseaux étaient représentés par des matrices de conférence, d'où le nom. D'autres applications sont en statistiques et une autre en géométrie elliptique .

Pour n  > 1, il existe deux types de matrice de conférence. Normalisons C en commençant par (si la définition la plus générale est utilisée) en réorganisant les lignes de manière à ce que tous les zéros soient sur la diagonale, puis en annulant toute ligne ou colonne dont la première entrée est négative. (Ces opérations ne changent pas si une matrice est une matrice de conférence.) Ainsi, une matrice de conférence normalisée a tous les 1 dans sa première ligne et colonne, à l'exception d'un 0 dans le coin supérieur gauche, et est de 0 sur la diagonale. Soit S la matrice qui reste lorsque la première ligne et la première colonne de C sont supprimées. Alors soit n est pair (un multiple de 4), et S est antisymétrique (comme l'est le C normalisé si sa première ligne est niée), ou n est impairment pair (congru à 2 modulo 4) et S est symétrique (comme c'est le C normalisé ).

Matrices de conférence symétriques

Si C est une matrice de conférence symétrique d'ordre n  > 1, alors non seulement n doit être congru à 2 (mod 4) mais aussi n − 1 doit être une somme de deux entiers carrés ; il y a une preuve intelligente par la théorie des matrices élémentaires dans van Lint et Seidel. n sera toujours la somme de deux carrés si n − 1 est une puissance première .

Étant donné une matrice de conférence symétrique, la matrice S peut être considérée comme la matrice d'adjacence de Seidel d'un graphe . Le graphe a n − 1 sommets, correspondant aux lignes et colonnes de S , et deux sommets sont adjacents si l'entrée correspondante dans S est négative. Ce graphe est fortement régulier du type appelé (d'après la matrice) graphe de conférence .

L'existence de matrices de conférence d'ordres n autorisées par les restrictions ci-dessus n'est connue que pour certaines valeurs de n . Par exemple, si n = q + 1 où q est une puissance première congruente à 1 (mod 4), alors les graphes de Paley fournissent des exemples de matrices de conférence symétriques d'ordre n , en prenant S comme matrice de Seidel du graphe de Paley. Les premiers ordres possibles d'une matrice de conférence symétrique sont n = 2, 6, 10, 14, 18, (pas 22, puisque 21 n'est pas une somme de deux carrés), 26, 30, (pas 34 puisque 33 n'est pas un somme de deux carrés), 38, 42, 46, 50, 54, (pas 58), 62 (séquence A000952 dans l' OEIS ); pour chacun d'entre eux, on sait qu'il existe une matrice de conférence symétrique de cet ordre. L'ordre 66 semble être un problème ouvert.

Exemple

La matrice de conférence essentiellement unique d'ordre 6 est donnée par

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

toutes les autres matrices de conférence d'ordre 6 sont obtenues à partir de celle-ci en retournant les signes d'une ligne et/ou colonne (et en prenant des permutations de lignes et/ou colonnes, selon la définition en usage).

Matrices de conférence antisymétriques

Des matrices antisymétriques peuvent également être produites par la construction de Paley. Soit q une puissance première de résidu 3 (mod 4). Alors il existe un digraphe de Paley d'ordre q qui conduit à une matrice de conférence antisymétrique d'ordre n = q + 1. La matrice est obtenue en prenant pour S la matrice q × q qui a un +1 en position ( i,j ) et −1 en position ( j,i ) s'il y a un arc du digraphe de i à j , et zéro diagonale. Alors C construit comme ci-dessus à partir de S , mais avec la première ligne entièrement négative, est une matrice de conférence antisymétrique.

Cette construction ne résout qu'une petite partie du problème de décider pour quels nombres pairs n il existe des matrices de conférence antisymétriques d'ordre n .

Généralisations

Parfois, une matrice de conférence d'ordre n est simplement définie comme une matrice de pondération de la forme W ( n, n −1), où W ( n,w ) est dit de poids w > 0 et d'ordre n s'il s'agit d'un carré matrice de taille n avec des entrées de {−1, 0, +1} satisfaisant WW ^t = w I . En utilisant cette définition, l'élément zéro n'a plus besoin d'être sur la diagonale, mais il est facile de voir qu'il doit toujours y avoir exactement un élément zéro dans chaque ligne et colonne. Par exemple, la matrice

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

satisferait cette définition assouplie, mais pas la plus stricte exigeant que les éléments zéro soient sur la diagonale.

Un design de conférence est une généralisation des matrices de conférence à des matrices non rectangulaires. Un plan de conférence C est une matrice, avec des entrées de {-1, 0, +1} satisfaisant , où est la matrice d'identité et au plus un zéro dans chaque ligne. Les conceptions repliées des conceptions de conférence peuvent être utilisées comme conceptions de criblage définitives. ${\style d'affichage N\fois k}$${\displaystyle W^{T}W=(N-1)I_{k}}$${\style d'affichage I_{k}}$${\style d'affichage k\fois k}$

Circuits de conférence téléphonique

Le réseau de conférence trivial à 2 ports

Belevitch a obtenu des solutions complètes pour les matrices de conférence pour toutes les valeurs de n jusqu'à 38 et a fourni des circuits pour certaines des plus petites matrices. Un réseau de conférence idéal est un réseau où la perte de signal est entièrement due à la division du signal entre plusieurs ports d'abonné de conférence. C'est-à-dire qu'il n'y a pas de pertes de dissipation dans le réseau. Le réseau doit contenir uniquement des transformateurs idéaux et aucune résistance. Un réseau de conférence idéal à n ports existe si et seulement s'il existe une matrice de conférence d'ordre n . Par exemple, un réseau de conférence à 3 ports peut être construit avec le circuit de transformateur hybride bien connu utilisé pour la conversion 2 fils en 4 fils dans les combinés téléphoniques et les répéteurs de ligne. Cependant, il n'y a pas de matrice de conférence d'ordre 3 et ce circuit ne produit pas un réseau de conférence idéal . Une résistance est nécessaire pour l'appariement qui dissipe le signal, sinon le signal est perdu à cause d'une inadéquation.

Comme mentionné ci-dessus, une condition nécessaire pour qu'une matrice de conférence existe est que n -1 doit être la somme de deux carrés. Lorsqu'il existe plus d'une somme possible de deux carrés pour n -1, il existera plusieurs solutions essentiellement différentes pour le réseau de conférence correspondant. Cette situation se produit à n de 26 et 66. Les réseaux sont particulièrement simples lorsque n −1 est un carré parfait ( n = 2, 10, 26, ...).

Remarques

Les références

• Belévitch V (1950). « Théorie des réseaux 2 n -terminaux avec applications à la téléphonie de conférence ». Communication électrique . 27 : 231–244.
• Goethals JM, Seidel JJ (1967). "Matrices orthogonales avec zéro diagonale". Revue canadienne de mathématiques . 19 : 1001-1010. doi : 10.4153/cjm-1967-091-8 .
• Lili Xiao et Dennis KJ Lin et Fengshan Bai (2012). "Construire des conceptions de criblage définitives à l'aide de matrices de conférence". Journal de la technologie de qualité . 44 (1) : 2–8. doi : 10.1080/00224065.2012.11917877 .
• Seidel, JJ (1991), éd. DG Corneil et R. Mathon, Géométrie et Combinatoire : uvres choisies de JJ Seidel . Boston : Presse académique. Plusieurs des articles sont liés aux matrices de conférence et à leurs graphiques.
• Colbourn, Charles J. ; Dinitz, Jeffrey H. (2007) Handbook of Combinatorial Designs , Boca Raton, Floride : Chapman and Hall/CRC Press, ISBN  1-58488-506-8 .
• van Lint, Jacobus Hendricus; Wilson, Richard Michael (2001) A Course in Combinatorics , Cambridge: Cambridge University Press, ISBN  0-521-00601-5 .
• Stinson, Douglas Robert (2004) Conceptions combinatoires : Constructions et analyse , New York : Springer, ISBN  0-387-95487-2 .
• Eric D. Schoen, Pieter T. Eendebak, Peter Goos (2018). « Un critère de classification pour les conceptions de criblage définitives ». Annales de statistiques .CS1 maint : plusieurs noms : liste des auteurs ( lien )

Lectures complémentaires

• NA Balonin, Jennifer Seberry, "A Review and New Symmetric Conference Matrices" , Research Online , University of Wollongong, 2014. L'annexe répertorie toutes les matrices de conférence connues et possibles jusqu'à 1002.