Konferenční matice - Conference matrix

v matematika, a konferenční matice (také nazývaný a C-matice) je čtverec matice C s 0 na úhlopříčce a +1 a -1 mimo úhlopříčku, takové, že C^TC je násobkem matice identity Já. Pokud má tedy matice pořádek n, C^TC = (n−1)Já. Někteří autoři používají obecnější definici, která vyžaduje, aby v každém řádku a sloupci byla jedna 0, ale ne nutně na diagonále.^[1][2]

Konferenční matice poprvé vznikly v souvislosti s problémem v telefonie.^[3] Poprvé je popsal Vitold Belevitch, Který jim také dal své jméno. Belevitch se zajímal o konstrukci ideálu telefonní konference sítě od ideálu transformátory a zjistil, že takové sítě byly reprezentovány konferenčními maticemi, odtud název.^[4] Další aplikace jsou v statistika,^[5] a další je v eliptická geometrie.^[6]

Pro n > 1, existují dva druhy konferenční matice. Pojďme se normalizovat C tím, nejprve (pokud je použita obecnější definice), přeskupit řádky tak, aby všechny nuly byly na úhlopříčce, a poté negovat jakýkoli řádek nebo sloupec, jehož první položka je záporná. (Tyto operace nemění, zda je matice konferenční maticí.) Normalizovaná konferenční matice má tedy v prvním řádku a sloupci všechna 1, s výjimkou 0 v levém horním rohu a na diagonále je 0. Nechat S být matice, která zůstane, když první řádek a sloupec C jsou odstraněny. Pak buď n je rovnoměrně rovnoměrně (násobek 4) a S je antisymetrický (jak je normalizováno C pokud je jeho první řádek negován), nebo n je kupodivu dokonce (shodný s 2 modulo 4) a S je symetrický (jak je normalizováno C).

Symetrické konferenční matice

Li C je symetrická konferenční matice řádu n > 1, pak nejen musí n být shodný s 2 (mod 4), ale také n - 1 musí být součet dvou čtvercových celých čísel;^[7] existuje chytrý důkaz podle teorie elementárních matic u van Lint a Seidel.^[6] n bude vždy součtem dvou čtverců, pokud n - 1 je a hlavní síla.^[8]

Vzhledem k symetrické konferenční matici, matici S lze zobrazit jako Seidelská matice sousedství a graf. Graf má n - 1 vrcholy, odpovídající řádkům a sloupcům Sa dva vrcholy sousedí, pokud je odpovídající položka v S je negativní. Tento graf je velmi pravidelné volaného typu (po matici) a konferenční graf.

Existence konferenčních matic objednávek n povolená výše uvedenými omezeními je známa pouze pro některé hodnoty n. Například pokud n = q + 1 kde q je hlavní síla shodná s 1 (mod 4), pak Paleyovy grafy poskytnout příklady symetrických konferenčních matic objednávky ntím, že S být Seidelovou maticí Paleyova grafu. Prvních několik možných objednávek symetrické konferenční matice je 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 dvou čtverců), 38, 42, 46, 50, 54, (ne 58), 62 (sekvence A000952 v OEIS ); pro každý z nich je známo, že existuje symetrická konferenční matice tohoto řádu. Objednávka 66 se zdá být otevřeným problémem.

Příklad

The v podstatě jedinečný matice konference řádu 6 je dána

${displaystyle {egin {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 & 0end {pmatrix}}}$,

všechny ostatní konferenční matice řádu 6 jsou z této získány převrácením znaků některých řádků a / nebo sloupců (a odebráním permutací řádků a / nebo sloupců podle používané definice).

Antisymetrické konferenční matice

Antisymetrické matice lze také vyrobit konstrukcí Paley. Nechat q být hlavní silou se zbytkem 3 (mod 4). Pak je tu Paley digraph řádu q což vede k antisymetrické konferenční matici řádu n = q + 1. Matice se získá převzetím pro S the q × q matice, která má +1 v poloze (já, j) a -1 v poloze (j, i) pokud existuje oblouk digrafu z i na ja nulová úhlopříčka. Pak C konstruovány jako výše z S, ale s první řadou všech záporných, je antisymetrická konferenční matice.

Tato konstrukce řeší jen malou část problému rozhodování, pro které jsou rovnoměrně sudá čísla n existují antisymetrické konferenční matice řádu n.

Zobecnění

Někdy konferenční matice objednávky n je definován jako vážicí matice formuláře Ž(n, n-1), kdeŽ(n, w) se říká, že má váhu w> 0 a objednat n pokud je to čtvercová matice velikosti n se záznamy od {−1, 0, +1} uspokojivé W W^t = w já.^[2] Při použití této definice již není nutné, aby byl nulový prvek na diagonále, ale je snadné vidět, že v každém řádku a sloupci musí být vždy přesně jeden nulový prvek. Například matice

${displaystyle {egin {pmatrix} 1 & 0 & 1 & 1 0 & -1 & -1 & 1 1 & -1 & 0 & -1 1 & 1 & -1 & 0end {pmatrix}}}$

by uspokojilo tuto uvolněnou definici, ale ne tu přísnější, která vyžaduje, aby byly nulové prvky na úhlopříčce.

Konferenční design je zobecněním konferenčních matic na ne-obdélníkové matice. Konferenční design C je ${displaystyle N imes k}$ matice s uspokojivými položkami od {-1, 0, +1} ${displaystyle W ^ {T} W = (N-1) I_ {k}}$, kde${displaystyle I_ {k}}$ je ${displaystyle k imes k}$ matice identity a maximálně jedna nula v každém řádku. Skládací návrhy konferenčních návrhů lze použít jako definitivní projekce promítání.^[9][10]

Telefonní konferenční obvody

Triviální 2portová konferenční síť

Belevitch získal kompletní řešení pro konferenční matice pro všechny hodnoty n až 38 a poskytl obvody pro některé z menších matic. An ideální konferenční síť je takový, kde ztráta signálu je zcela způsobena rozdělením signálu mezi více účastnických portů konference. To znamená, že v síti nedochází k žádným ztrátám ztrátou. Síť musí obsahovat pouze ideální transformátory a žádný odpor. An n-port ideální konferenční síť existuje právě tehdy, pokud existuje konferenční matice objednávky n. Například, 3-portová konferenční síť může být postavena s dobře známým hybridní transformátor obvod používaný pro 2vodičový na 4vodičový převod v telefonních sluchátkách a opakovačích linek. Neexistuje však žádná konferenční matice řádu 3 a tento obvod neprodukuje ideál konferenční síť. Pro přizpůsobení je nutný odpor, který rozptýlí signál, jinak dojde ke ztrátě signálu v důsledku nesouladu.^[11]

Jak již bylo zmíněno výše, nezbytnou podmínkou pro existenci konferenční matice je to n−1 musí být součet dvou čtverců. Pokud existuje více než jeden možný součet dvou čtverců pro n−1 pro příslušnou konferenční síť bude existovat několik v zásadě odlišných řešení. Tato situace nastává v n z 26 a 66. Sítě jsou obzvláště jednoduché, když n−1 je perfektní čtverec (n = 2, 10, 26, …).^[12]

Poznámky

Reference

• Belevitch V (1950). „Teorie 2n-koncové sítě s aplikacemi pro konferenční telefonii ". Elektrická komunikace. 27: 231–244.
• Goethals J.M., Seidel J.J. (1967). Msgstr "Ortogonální matice s nulovou úhlopříčkou". Kanadský žurnál matematiky. 19: 1001–1010. doi:10.4153 / cjm-1967-091-8.
• Lili Xiao a Dennis K. J. Lin a Fengshan Bai (2012). "Konstrukce definitivních návrhů promítání pomocí konferenčních matic". Journal of Quality Technology. 44 (1): 2–8. doi:10.1080/00224065.2012.11917877.
• Seidel, J.J. (1991), ed. D.G. Corneil a R. Mathon, Geometry and Combinatorics: Selected Works of J.J. Seidele. Boston: Academic Press. Několik článků se týká konferenčních matic a jejich grafů.
• Colbourn, Charles J .; Dinitz, Jeffrey H. (2007) Příručka kombinatorických vzorů, Boca Raton, Florida: Chapman and Hall / CRC Press, ISBN  1-58488-506-8.
• van Lint, Jacobus Hendricus; Wilson, Richard Michael (2001) Kurz kombinatoriky, Cambridge: Cambridge University Press, ISBN  0-521-00601-5.
• Stinson, Douglas Robert (2004) Kombinatorické návrhy: Konstrukce a analýza, New York: Springer, ISBN  0-387-95487-2.
• Eric D. Schoen, Pieter T. Eendebak, Peter Goos (2018). Msgstr "Kritérium klasifikace pro definitivní návrhy promítání". Annals of Statistics.CS1 maint: více jmen: seznam autorů (odkaz)

Další čtení

• N. A. Balonin, Jennifer Seberry, „Recenze a nové symetrické konferenční matice“, Výzkum online„University of Wollongong, 2014. V příloze jsou uvedeny všechny známé a možné konferenční matice až do výše 1002.