Matice konference

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 13. července 2019; ověření vyžaduje 1 úpravu .

V matematice je konferenční matice (také nazývaná C-matice , konferenční matice ) čtvercová matice C s nulami na diagonále as +1 a -1 mimo diagonálu tak, že C T C je násobkem matice identity I. . Pokud má tedy matice C řád n , pak C T C = ( n −1) I . Někteří autoři dávají obecnější definici, vyžadující nulu v každém řádku a sloupci, ale ne nutně na [1] [2] diagonále .

Konferenční matrice původně vznikly v souvislosti s úkoly telefonie [3] . Zavedl je Vitold Belevich , termín konferenční matice zavedl on. Belevich se zajímal o vytvoření ideální konferenční telefonní sítě z ideálních transformátorů . Zjistil, že takové sítě mohou být reprezentovány konferenčními matricemi, které jim daly jméno [4] . Konferenční matice se používají také ve statistice [5] a eliptické geometrii [6] .

Pro n > 1 ( n je vždy sudé) existují dva druhy konferenčních matic. Pokud převedete konferenční matici do normálního tvaru, stane se symetrickou (pokud je n dělitelné 4) nebo antisymetrickou (pokud je n sudé, ale není dělitelné 4).

Normální pohled na matici konference

Abyste získali normální formu konferenční matice C , potřebujete:

  1. Uspořádejte řádky matice C tak, aby všechny nuly byly na diagonále (pokud je použita obecnější definice konferenční matice)
  2. V řádcích, ve kterých je první prvek záporný, změňte znaménko všech prvků.
  3. Změňte nebo neměňte znaménko prvků prvního řádku, abyste získali symetrickou nebo antisymetrickou matici.

Matice získaná takovými transformacemi z konferenční matice je také konferenční maticí. První prvky každého řádku kromě prvního v normálním zobrazení konferenční matice jsou 1 (první řádek má první prvek 0).

Symetrická konferenční matice

Je-li C  symetrická konferenční matice řádu n > 1, pak nejen že n musí být shodné s 2 (mod 4), ale také n − 1 musí být součtem druhých mocnin dvou celých čísel [7] . Pomocí teorie elementárních matic lze dokázat [6] , že n − 1 bude vždy součtem druhých mocnin celých čísel, jestliže n − 2 je mocninou prvočísla [8] .

Vzhledem k symetrické konferenční matici C lze submatici S získanou odstraněním prvního řádku a sloupce z C považovat za Seidelovu matici sousednosti nějakého grafu . Jedná se o graf s n − 1 vrcholy odpovídajícími řádkům a sloupcům matice S , dva vrcholy sousedí, pokud jsou odpovídající prvky matice S záporné. Výsledný graf je přísně pravidelný a patří do typu konferenčních grafů (pojmenovaných tak právě kvůli konferenční matici).

Existence konferenčních matic řádu n , povolená výše uvedenými omezeními, je známá pouze pro některé hodnoty n . Pokud například n = q + 1, kde q je prvočíslo kongruentní k 1 (mod 4), pak Paleyovy grafy uvádějí příklady symetrických matic řádu n : Seidelova matice sousedství Paleyho grafu je brána jako S. Prvních několik možných řádů symetrických konferenčních matic n = 2, 6, 10, 14, 18, (ne 22, protože 21 není součet dvou čtverců), 26, 30, (ne 34, protože 33 není součet dva čtverce), 38, 42, 46, 50, 54, (ne 58), 62 ( OEIS sekvence A000952 ); pro všechny dané hodnoty je známo, že existují symetrické konferenční matice. Pro n = 66 zůstává otázka otevřená.

Příklad

V podstatě unikátní konferenční matice řádu 6 má tvar:

,

všechny ostatní konferenční matice řádu 6 se získávají z této matice změnou znaménka některých řádků a/nebo sloupců (a také permutací řádků a/nebo sloupců, pokud je použita obecnější definice).

Antisymetrické konferenční matice

Antisymetrické konferenční matice lze získat také metodou Paley. Nechť q  je prvočíslo se zbytkem 3 (mod 4). Pak je tu Paleyův graf řádu q , který vede k antisymetrické konferenční matici řádu n = q + 1. Tato matice se získá tak, že vezmeme matici q × q pro S s +1 na ( i, j )-té pozici a −1 na ( j,i )té, pokud existuje hrana digrafu od i do j a nuly na diagonále. Potom se S sestaví z S jako v symetrickém případě, ale první řada se sestaví z nezákladných čísel. Výsledné S bude antisymetrická konferenční matice.

Tato metoda řeší jen malou část problému určení, pro které n dělitelné 4 existují antisymetrické konferenční matice řádu n .

Poznámky

  1. ↑ Malcolm Greig, Harri Haanpää a Petteri Kaski, Journal of Combinatorial Theory, Series A, sv. 113, č.p. 4, 2006, str. 703-711, doi : 10.1016/j.jcta.2005.05.005
  2. ↑ Harald Gropp, Více o orbitálních matricích, Electronic Notes in Discrete Mathematics, sv. 17, 2004, s. 179-183, doi : 10.1016/j.endm.2004.03.036
  3. ↑ Belevitch, str. 231-244.
  4. ↑ Colbourn a Dinitz, (2007), s. 19
    van Lint a Wilson, (2001), s. 98
    Stinson, (2004), s. 200
  5. ↑ Raghavarao, D. Některé optimální návrhy vážení  //  Annals of Mathematical Statistics : deník. - 1959. - Sv. 30 , č. 2 . - str. 295-303 . - doi : 10.1214/aoms/1177706253 .
  6. ↑ 1 2 van Lint, JH, and Seidel, JJ (1966), Rovnostranné množiny bodů v eliptické geometrii. Indagationes Mathematicae , sv. 28, str. 335-348.
  7. ↑ Belevitch, str. 240
  8. ↑ Stinson, str. 78

Literatura