Paley építkezése

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

A Paley -konstrukció egy módszer Hadamard-mátrixok készítésére véges mező felhasználásával . A szerkezetet 1933-ban írta le Raymond Paley angol matematikus .

Paley konstrukciója másodfokú maradékokat használ egy GF ( q ) véges mezőben , ahol q egy páratlan prím hatványa . A konstrukciónak két változata létezik, attól függően, hogy q kongruens-e 1 vagy 3 modulo 4-hez.

A négyzet karakter és a Jacobstal-mátrix

A négyzet karakter jelzi, hogy a véges mező a eleme tökéletes négyzet -e . Különösen, ha a b véges mező valamely nem nulla elemére , és ha a nem a véges mező bármely elemének négyzete. Például GF -ben (7) , , és nem nulla négyzetek . Ezért és . $\chi(a)$ $\chi (0)=0,\chi (a)=1$ $a=b^{2}$ $\chi (a)=-1$ $1=1^{2}=6^{2}$ $4=2^{2}=5^{2}$ $2=3^{2}=4^{2}$ $\chi (0)=0,\chi (1)=\chi (2)=\chi (4)=1$ $\chi (3)=\chi (5)=\chi (6)=-1$

A Q for Jacobstal-mátrix egy véges mező elemei által indexelt sorokat és oszlopokat tartalmazó mátrix úgy, hogy az a sor és a b oszlop eleme . Például a GF (7)-ben, ha a Jacobstal-mátrix sorait és oszlopait a 0, 1, 2, 3, 4, 5, 6 mezőelemek indexelik, akkor $GF(q)$ $q{\times }q$ $\chi (ab)$

Q={\begin{bmatrix}0&-1&-1&1&-1&1&1\\1&0&-1&-1&1&-1&1\\1&1&0&-1&-1&1&-1\\-1&1&1&0&-1&-1&1\\1&-1&1&1 1&-1\\-1&1&-1&1&1&0&-1\\-1&-1&1&-1&1&1&0\end{bmátrix}}.

A Jacobstal-mátrixnak és tulajdonságai vannak , ahol E az azonosságmátrix , J pedig egyenlő azzal a mátrixszal, amelyben minden elem egyenlő -1-gyel. Ha q kongruens 1-gyel (mod 4), akkor −1 egy négyzet GF -ben ( q ), ami azt jelenti, hogy Q szimmetrikus mátrix . Ha q kongruens 3-mal (mod 4), akkor −1 nem négyzet, Q pedig ferde-szimmetrikus mátrix . Ha q prím, akkor Q körkör . Vagyis minden sort a fenti sorból kapunk ciklikus permutációval. $QQ^{T}=qE-J$ $QJ=JQ=0$ $q{\times }q$ $q{\times }q$

Paley I építése

Ha q összehasonlítható a 3-mal (mod 4), akkor

H=E+{\begin{bmatrix}0&j^{T}\\-j&Q\end{bmatrix}}

méretű Hadamard mátrix . Itt j egy q hosszúságú oszlopvektor, amely -1-ből áll, E pedig az azonosságmátrix. A H mátrix egy ferde Hadamard mátrix , ami azt jelenti, hogy teljesíti az egyenlőséget . $q+1$ ${\megjelenítési stílus (q+1)\times (q+1)}$ $H+H^{T}=2E$

A Paley II építése

Ha q összehasonlítható 1-gyel (mod 4), akkor a mátrixot úgy kapjuk meg, hogy az összes 0-t lecseréljük

{\begin{bmatrix}0&j^{T}\\j&Q\end{bmatrix}}

mátrixhoz

{\begin{bmatrix}1&-1\\-1&-1\end{bmatrix}}

és minden elemet a mátrixba ${\pm }1$

\pm {\begin{bmatrix}1&1\\1&-1\end{bmatrix}}

méretű Hadamard mátrix . Ez egy szimmetrikus Hadamard-mátrix. $2(q+1)$

Példák

Ha a Paley I konstrukciót alkalmazzuk a GF (7) Jacobstal-mátrixára, megkapjuk a Hadamard-mátrixot, $8{\time }8$

11111111 -1--1-11 -11--1-1 -111--1- --111--1 -1-111-- --1-111- ---1-111.

Példaként egy Paley II konstrukcióra, ahol q egy prímszám hatványa, nem pedig prímszám, vegyük figyelembe a GF -et (9). Ez a GF (3) mező kiterjesztése , amelyet egy irreducibilis négyzetpolinom gyökének hozzáadásával kapunk . Különféle irreducibilis négyzetpolinomok ekvivalens mezőket adnak. Ha ennek a polinomnak a gyökét is választjuk , akkor a GF (9) kilenc elemét így írhatjuk fel . És nullától eltérő négyzetek lesznek . A Jacobstal-mátrix az $x^{2}+x-1$ $0,1,-1,a,a+1,a-1,-a,-a+1,-a-1$ $1=({\pm }1)^{2},-a+1=({\pm }a)^{2},a-1=(\pm (a+1))^{2 }$ $-1=(\pm (a-1))^{2}$

Q={\begin{bmatrix}0&1&1&-1&-1&1&-1&1&-1\\1&0&1&1&-1&-1&-1&-1&1\\1&1&0&-1&1&-1&1&-1&-1\\-1&1&-1&0&1 -1&1\\-1&-1&1&1&0&1&1&-1&-1\\1&-1&-1&1&1&0&-1&1&-1\\-1&-1&1&-1&1&-1&0&1&1\\1&-1&-1&-1&-1&1&1&1&1&1 -1&-1&1&1&0\end{bmátrix}}.

Ez egy szimmetrikus mátrix, amely kör alakú blokkokból áll. A Paley II felépítése szimmetrikus Hadamard-mátrixot ad, $3 alkalommal 3$ $20\times 20$

1-111111 111111 111111 -- 1-1-1- 1-1-1- 1-1-1- 11 1-1111 ----11 --11-- 1- --1-1- -1-11- -11--1 11 111-11 11---- ----11 1- 1---1- 1--1-1 -1-11- 11 11111- --11-- 11---- 1- 1-1--- -11--1 1--1-1 11 --11-- 1-1111 ----11 1- -11--1 --1-1- -1-11- 11----11 111-11 11---- 1- -1-11- 1---1- 1--1-1 11 11---- 11111- --11-- 1- 1--1-1 1-1--- -11--1 11 ----11 --11-- 1-1111 1- -1-11- -11--1 --1-1- 11 11---- ----11 111-11 1- 1--1-1 -1-11- 1---1- 11 --11-- 11---- 11111- 1- -11--1 1--1-1 1-1---.

Hadamard sejtése

A Hadamard-mátrix méretének egyenlőnek kell lennie 1-gyel, 2-vel vagy 4 többszörösével. Két m és n méretű Hadamard-mátrix Kronecker-szorzata egy mn méretű Hadamard-mátrix lesz . Amikor a Paley-konstrukcióból és a mátrixból a mátrixok Kronecker-szorzatát képezzük , $2\szer 2$

H_{2}={\begin{bmatrix}1&1\\1&-1\end{bmátrix)),

100-ig tetszőleges méretű Hadamard-mátrixot kapunk, kivéve 92-t. 1933-as cikkében Paley ezt mondja: „Nagyon valószínű, hogy abban az esetben, ha m osztható 4-gyel, meg lehet alkotni egy m rendű ortogonális mátrixot , amely a következőkből áll: , de az általános tételnek számos nehézsége van." Úgy tűnik, hogy ez a Hadamard-sejtés kijelentésének első publikációja . A 92 méretű mátrixot végül Baumert, Golomb és Hall készítette Williamson konstrukciójával, számítógépes kereséssel kombinálva. Jelenleg kimutatták, hogy a Hadamard-mátrixok mindenki számára léteznek . ${\pm }1$ $m\,\equiv \,0\mod 4$ $m<668$

Lásd még

Jegyzetek

Irodalom

Paley REAC Az ortogonális mátrixokról // Journal of Mathematics and Physics. - 1933. - T. 12 . – S. 311–320 .
Baumert LD, Golomb SW , Hall M. Jr. Egy 92-es rendű Hadamard-mátrix felfedezése // Bull. amer. Math. Soc .. - 1962. - T. 68 , 1. sz. 3 . – S. 237–238 . - doi : 10.1090/S0002-9904-1962-10761-7 .
MacWilliams FJ, Sloane NJA A hibajavító kódok elmélete . - 1977. - S. 47 , 56. - ISBN 0-444-85193-3 .