Konferencia Mátrix

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. július 13-án felülvizsgált verziótól ; az ellenőrzéshez 1 szerkesztés szükséges .

A matematikában a konferencia mátrix (más néven C-mátrix , konferencia mátrix ) egy C négyzetmátrix , amelynek átlóján nullák vannak, és +1 és -1 az átlón kívül, így C T C az I azonosságmátrix többszöröse. . Így ha a C mátrix n rendű , akkor C T C = ( n −1) I . Egyes szerzők általánosabb definíciót adnak, minden sorban és minden oszlopban nullát írnak elő, de nem feltétlenül az [1] [2] átlón .

A konferencia mátrixok eredetileg a telefonálás feladatai kapcsán merültek fel [3] . Vitold Belevich vezette be őket , a konferencia mátrix kifejezést ő vezette be. Belevicset érdekelte egy ideális konferenciatelefon hálózat létrehozása ideális transzformátorokból . Felfedezte, hogy az ilyen hálózatokat konferencia mátrixokkal is le lehet ábrázolni, amelyek a nevüket is adták [4] . A konferenciamátrixokat a statisztikában [5] és az elliptikus geometriában [6] is használják .

Ha n > 1 ( n mindig páros), kétféle konferenciamátrix létezik. Ha a konferencia mátrixot normál formába hozzuk, akkor szimmetrikus (ha n osztható 4-gyel) vagy antiszimmetrikus (ha n páros, de nem osztható 4-gyel).

A konferencia mátrix normál nézete

A C konferenciamátrix normál formájának eléréséhez a következőkre van szüksége:

  1. Rendezd át a C mátrix sorait úgy, hogy minden nulla az átlón legyen (ha a konferencia mátrix általánosabb definícióját használod)
  2. Azokban a sorokban, amelyekben az első elem negatív, változtassa meg az összes elem előjelét.
  3. Módosítsa vagy ne módosítsa az első sor elemeinek előjelét, hogy szimmetrikus vagy antiszimmetrikus mátrixot kapjon.

A konferencia mátrixból az ilyen transzformációkkal kapott mátrix egyben konferencia mátrix is. A konferencia mátrix normál nézetében az első kivételével minden sor első eleme 1 (az első sor első eleme 0).

Szimmetrikus konferenciamátrix

Ha C egy n > 1  rendű szimmetrikus konferenciamátrix , akkor nemcsak n -nek kell kongruensnek lennie 2-vel (mod 4), hanem n − 1-nek is két egész szám négyzetének összegének kell lennie [7] . Az elemi mátrixelmélet segítségével bebizonyíthatjuk [6] , hogy n − 1 mindig az egész számok négyzeteinek összege lesz, ha n − 2 egy prímszám hatványa [8] .

Adott egy szimmetrikus C konferenciamátrix , a C -ből az első sor és oszlop törlésével kapott S részmátrixot valamely gráf Seidel szomszédsági mátrixának tekinthetjük . Ez egy n − 1 csúcsú gráf, amely megfelel az S mátrix sorainak és oszlopainak , két csúcs szomszédos, ha az S mátrix megfelelő elemei negatívak. Az így kapott gráf szigorúan szabályos , és a konferencia gráfok típusába tartozik (pontosan a konferencia mátrix miatt nevezték így).

A fenti megszorítások által megengedett n rendű konferencia mátrixok létezése csak néhány n értéknél ismert . Például, ha n = q + 1, ahol q egy 1-gyel kongruens prímhatvány (mod 4), akkor a Paley-gráfok példákat adnak n rendű szimmetrikus mátrixokra : a Paley-gráf Seidel-szomszédsági mátrixát S -nek vesszük . A szimmetrikus konferenciamátrixok első néhány lehetséges sorrendje n = 2, 6, 10, 14, 18, (nem 22, mivel a 21 nem két négyzet összege), 26, 30, (nem 34, mivel a 33 nem az összege két négyzet ), 38, 42, 46, 50, 54, (nem 58), 62 ( OEIS sorozat A000952 ); az összes megadott értékre ismert, hogy léteznek szimmetrikus konferenciamátrixok. n = 66 esetén a kérdés nyitott marad.

Példa

A 6. sorrend lényegében egyedi konferenciamátrixának a formája:

,

az összes többi 6-os rendű konferencia mátrixot ebből kapjuk néhány sor és/vagy oszlop előjelének megváltoztatásával (és általánosabb definíció esetén sorok és/vagy oszlopok permutálásával is).

Antiszimmetrikus konferencia mátrixok

Antiszimmetrikus konferencia mátrixok is előállíthatók a Paley módszerrel. Legyen q prímhatvány  3 maradékkal ( mod 4). Ezután van egy q rendű Paley-gráf , amely egy n = q + 1 rendű antiszimmetrikus konferenciamátrixhoz vezet . Ezt a mátrixot úgy kapjuk meg, hogy felveszünk egy q × q mátrixot S -re, ahol +1 az ( i, j )-edik. pozíció és −1 a ( j, i )-edik helyen, ha van egy digráf él i - től j - ig , és nullák az átlón. Ekkor S az S -ből épül fel, mint a szimmetrikus esetben, de az első sor nem pozitív számokból épül fel. A kapott S egy antiszimmetrikus konferenciamátrix lesz.

Ez a módszer csak egy kis részét oldja meg annak a problémának, hogy melyik n -re osztható 4-gyel, vannak n -es rendű antiszimmetrikus konferenciamátrixok .

Jegyzetek

  1. ↑ Malcolm Greig, Harri Haanpää és Petteri Kaski, Journal of Combinatorial Theory, Series A, vol. 113. sz. 4, 2006, 703-711. o., doi : 10.1016/j.jcta.2005.05.005
  2. ↑ Harald Gropp, Bővebben a pályamátrixokról, Electronic Notes in Discrete Mathematics, vol. 17, 2004, pp. 179-183, doi : 10.1016/j.endm.2004.03.036
  3. ↑ Belevics, pp. 231-244.
  4. ↑ Colbourn és Dinitz, (2007), 19. o.
    van Lint és Wilson, (2001), 98. o.
    Stinson, (2004), 200.
  5. ↑ Raghavarao, D. Néhány optimális mérlegelési terv  //  Annals of Mathematical Statistics : folyóirat. - 1959. - 1. évf. 30 , sz. 2 . - P. 295-303 . - doi : 10.1214/aoms/1177706253 .
  6. ↑ 1 2 van Lint, JH és Seidel, JJ (1966), Egyenlőoldali ponthalmazok elliptikus geometriában. Indagationes Mathematicae , vol. 28, pp. 335-348.
  7. ↑ Belevics, 240. o
  8. ↑ Stinson, 78. o

Irodalom