Konferenciamátrix

A matematikában egy konferenciamátrix (vagy C-mátrix) olyan C négyzetes mátrix, melynek átlóján csak 0, az átlón kívül csak +1 és −1 elemek szerepelnek, és C^TC az I egységmátrix többszöröse. Tehát, ha a mátrix rendje n, C^TC = (n−1)I. Egyes szerzők általánosabb definíciót használnak, melyben minden sorban és oszlopban egyetlen 0 kell szerepeljen, de ennek nem kell feltétlenül az átlón lennie.

A konferenciamátrixok először a telefónia területén bukkantak fel. Elsőként Vitold Belevitch írta le őket és adott nevet nekik. Belevitch ideális transzformátorokból próbált ideális telefonkonferencia-hálózatokat összeállítani és úgy találta, hogy ezeket a hálózatokat a konferenciamátrixok reprezentálják. Egyéb alkalmazásaik a statisztika és az elliptikus geometria területén vannak.

Ha n > 1, kétfajta konferenciamátrixról beszélhetünk. Amennyiben az általánosabb definíciót használtuk, először normalizáljuk C-t a sorok átrendezésével úgy, hogy a nullák az átlón legyenek, majd a negatív értékkel kezdődő sorok vagy oszlopok negálásával (ezek a műveletek nem változtatják meg a tényt, hogy a mátrix egy konferenciamátrix). Az így létrejött normalizált konferenciamátrix első sorában és oszlopában csak 1-esek vannak, eltekintve a sarok 0-jától, és az átlóban csak 0-k találhatók. Legyen az S az a mátrix, amit C első sorának és oszlopának eltávolításával nyerünk. Ekkor két eset lehetséges: vagy n kétszeresen páros (azaz 4 többszöröse), S pedig antiszimmetrikus (ahogy a normalizált C is, ha az első sort negálni kellett), vagy n egyszeresen páros (kongruens 2 modulo 4) és S szimmetrikus (ahogy a normalizált C).

Szimmetrikus konferenciamátrixok

Ha C n > 1 rendű szimmetrikus konferenciamátrix, akkor azon túl, hogy n kongruens 2 (mod 4), ráadásul n − 1-nek két négyzetszám összegének kell lennie; elemi mátrixelméleti módszerrel van Lint és Seidel trükkösen bizonyították. n mindig két négyzetszám össze lesz, ha n − 1 egy prímhatvány.

Adott szimmetrikus konferenciamátrix, S tekinthető úgy, mint egy gráf Seidel-féle szomszédsági mátrixa. A gráfnak S sorai és oszlopai szerint n − 1 csúcsa van, két csúcs pedig akkor van éllel összekötve, ha a nekik megfelelő S-beli érték negatív. Ezt az erősen reguláris gráfot nevezik (a mátrix neve után) konferenciagráfnak.

A fenti megszorítások által megengedett n-ek esetén sem ismert, hogy minden n-re létezik-e n-edrendű konferenciamátrix. Tudjuk például, hogy ha n = q + 1, ahol q 1-gyel kongruens (mod 4) prímhatvány, akkor a Paley-gráfok n-edrendű szimmetrikus konferenciamátrixokat adnak, ha S-et a Paley-gráf Seidel-mátrixának választjuk.

Az első néhány, szimmetrikus konferenciamátrixot megengedő rendszámok az n = 2, 6, 10, 14, 18, (a 22 nem, mivel a 21 nem két négyzet összege), 26, 30, (a 34 nem, mivel a 33 nem két négyzet összege), 38, 42, 46, 50, 54, (az 58 nem), 62 (A000952 sorozat az OEIS-ben); ezek mindegyikéről tudott, hogy létezik ilyen rendű konferenciamátrix. A 66 rendű mátrix létezése nyitott kérdés.

Példa

A lényegileg egyedi 6 rendű konferenciamátrix a következő:

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

az összes többi, 6 rendű konferenciamátrix előállítható ebből a mátrixból egyes sorok vagy oszlopok előjelének felcserélésével (és a használt definíció alapján sorok és vagy oszlopok sorrendjének felcserélésével). Tehát a mátrix sorok/oszlopok előjelének és/vagy sorrendjének felcserélése erejéig egyedi.

Antiszimmetrikus konferenciamátrixok

A Paley-konstrukcióval antiszimmetrikus mátrixok is előállíthatók. Legyen q egy prímhatvány, ami kongruens 3 (mod 4). Ekkor létezik olyan, q rendű irányított Paley-gráf, ami egy n = q + 1 rendű antiszimmetrikus konferenciamátrixhoz vezet. A mátrix megkapható, ha az S-t olyan q × q méretű mátrixnak választjuk, melynek (i,j) pozícióiban akkor található +1, (j,i) pozícióiban pedig −1, ha létezik irányított, i-ből j-be mutató él; az átlóban értelemszerűen 0-k szerepelnek. Ekkor C megkapható a fenti módon S-ből, de mivel az első sor teljesen negatív, ez egy antiszimmetrikus konferenciamátrix.

Ez a konstrukció csak nagyon kis részét oldja meg annak a problémának, hogy mely kétszeresen páros n-ekre létezik n rendű antiszimmetrikus konferenciamátrix.

Általánosítások

Néha az n rendű konferenciamátrixot úgy definiálják, mint egy W(n, n−1) alakú súlyozó mátrix, ahol W(n,w) akkor w>0 súlyú és n rendű, ha n méretű négyzetes mátrix, {−1, 0, +1} értékekkel, mely kielégíti a következőt: W W^t = w I. Ezt a definíciót használva a nulláknak nem kell az átlón lenni, de könnyen belátható, hogy továbbra is minden sorban és oszlopban pontosan egy nullának kell lennie. Például a

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

mátrix kielégíti ezt a könnyített definíciót, de a szigorúbb, az átlón lévő nullákat megkövetelőt már nem.

Telefonkonferencia-áramkörök

A triviális, 2 portos konferenciahálózat

Belevitch teljes megoldásokat állított elő egészen n = 38-ig a konferenciamátrixokra és néhány kisebb mátrixhoz az áramköröket is megrajzolta. Egy ideális konferenciahálózat működése során a jelek gyengülése kizárólag abból adódik, hogy felosztódik a konferencia előfizetői portjai között, tehát nincs hálózati disszipációs veszteség. A hálózat nem tartalmaz ellenállásokat és csak ideális transzformátorok vannak benne. Egy n-portos ideális konferenciahálózat pontosan akkor létezik, ha létezik n rendű konferenciamátrix. Például, egy 3 portos konferenciahálózat létrehozható a telefonos kézibeszélőkben és vonali erősítőkben 2 vezetékről 4 vezetékre átalakításkor alkalmazott, jól ismert villaáramkör (hibrid) segítségével. 3 rendű konferenciamátrix azonban nem létezik, és a villaáramkör nem nyújt ideális konferenciahálózatot. Be kell iktatni egy kiegyenlítő ellenállást, ami csillapítja a jelet, ellenkező esetben a mikrofon jele nem lesz hallható a fejhallgatóban..

• 
  Belevitch 6 portos ideális konferenciahálózata
• 
  Belevitch 10 portos ideális konferenciahálózata

A fent említettek szerint a konferenciamátrix létezésének szükséges feltétele, hogy n−1 két négyzetszám összege legyen. Ha n−1 többféleképpen is előállítható két négyzet összegeként, több megoldás lesz a konferenciahálózat előállítására. Ez a helyzet az n = 26 és 66 esetekben. A hálózatok különösen egyszerűek, amikor n−1 teljes négyzet (n = 2, 10, 26, …).

Fordítás

• Ez a szócikk részben vagy egészben a Conference matrix című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Belevitch V (1950). „Theory of 2n-terminal networks with applications to conference telephony”. Electrical Communication 27, 231–244. o. 
• Goethals J.M., Seidel J.J. (1967). „Orthogonal matrices with zero diagonal”. Canadian Journal of Mathematics 19, 1001–1010. o. DOI:10.4153/cjm-1967-091-8. 
• Seidel, J.J. (1991), ed. D.G. Corneil and R. Mathon, Geometry and Combinatorics: Selected Works of J.J. Seidel. Boston: Academic Press. Several of the articles are related to conference matrices and their graphs.
• Colbourn, Charles J.; Dinitz, Jeffrey H. (2007) Handbook of Combinatorial Designs, Boca Raton, Florida: 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) Combinatorial Designs: Constructions and Analysis, New York: Springer, ISBN 0-387-95487-2.