Construcția lui Paley

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 25 martie 2021; verificarea necesită 1 editare .

Construcția Paley este o metodă de construire a matricilor Hadamard folosind un câmp finit . Construcția a fost descrisă în 1933 de matematicianul englez Raymond Paley .

Construcția lui Paley folosește reziduuri pătratice într-un câmp finit GF ( q ), unde q este o putere a unui prim impar . Există două versiuni ale construcției, în funcție de faptul dacă q este congruent cu 1 sau 3 modulo 4.

Caracterul pătrat și matricea Jacobstal

Caracterul pătrat indică dacă elementul a al câmpului finit este un pătrat perfect . În special, dacă pentru un element diferit de zero al câmpului finit b și dacă a nu este pătratul vreunui element al câmpului finit. De exemplu, în GF (7) , , și sunt pătrate diferite de zero . Prin urmare, și . $\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$

Matricea Jacobstal Q for este o matrice cu rânduri și coloane indexate de elemente ale unui câmp finit, astfel încât elementul din rândul a și coloana b să fie . De exemplu, în GF (7), dacă rândurile și coloanele matricei Jacobstal sunt indexate prin elementele de câmp 0, 1, 2, 3, 4, 5, 6, atunci $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&0&-1\\-1&-1&1&-1&1&1&0\end{bmatrix}}.

Matricea Jacobstal are proprietățile și , unde E este matricea de identitate și J este egal cu matricea în care toate elementele sunt egale cu -1. Dacă q este congruent cu 1 (mod 4), atunci −1 este un pătrat în GF ( q ), ceea ce implică că Q este o matrice simetrică . Dacă q este congruent cu 3 (mod 4), atunci −1 nu este un pătrat și Q este o matrice simetrică oblică . Dacă q este prim, Q este un circulant . Adică, fiecare rând este obținut din rândul de mai sus printr-o permutare ciclică. $QQ^{T}=qE-J$ $QJ=JQ=0$ $q{\times }q$ $q{\times }q$

Construcția lui Paley I

Dacă q este comparabil cu 3 (mod 4), atunci

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

este o matrice Hadamard de dimensiune . Aici j este un vector coloană de lungime q format din -1, iar E este matricea de identitate. Matricea H este o matrice Hadamard oblică , ceea ce înseamnă că satisface egalitatea . $q+1$ $(q+1)\times (q+1)$ $H+H^{T}=2E$

Construcția lui Paley II

Dacă q este comparabil cu 1 (mod 4), atunci matricea obținută prin înlocuirea tuturor 0-urilor în

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

la matrice

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

și toate elementele matricei ${\pm }1$

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

este o matrice Hadamard de dimensiune . Aceasta este o matrice Hadamard simetrică. $2(q+1)$

Exemple

Dacă aplicăm construcția lui Paley I la matricea Jacobstal pentru GF (7), obținem matricea Hadamard, $8{\times }8$

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

Ca exemplu de construcție Paley II în care q este o putere a unui număr prim și nu a unui număr prim, luați în considerare GF (9). Aceasta este o extensie a câmpului GF (3), obținută prin adăugarea rădăcinii unui polinom pătrat ireductibil . Diverse polinoame pătrate ireductibile dau câmpuri echivalente. Dacă alegem și rădăcina a acestui polinom, cele nouă elemente ale lui GF (9) pot fi scrise ca . Și vor fi pătrate diferite de zero . Matricea Jacobstal este $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&-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&1&1&1&1&1&- -1&-1&1&1&0\end{bmatrix}}.

Aceasta este o matrice simetrică formată din blocuri circulare. Construcția lui Paley II dă o matrice Hadamard simetrică, $de 3 ori 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---.

Conjectura lui Hadamard

Mărimea matricei Hadamard trebuie să fie egală cu 1, 2 sau un multiplu de 4. Produsul Kronecker a două matrice Hadamard de dimensiunile m și n va fi o matrice Hadamard de dimensiunea mn . Când se formează produsul Kronecker al matricelor din construcția Paley și matricea, $2\ ori 2$

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

se obțin matrici Hadamard de orice dimensiune admisibilă până la 100, cu excepția 92. În lucrarea sa din 1933, Paley spune: „Este destul de probabil ca în cazul în care m este divizibil cu 4, se poate construi o matrice ortogonală de ordinul m , constând din , dar teorema generală are o serie de dificultăți." Aceasta pare a fi prima publicație a unei declarații a conjecturei Hadamard . Matricea de 92 de dimensiuni a fost în cele din urmă construită de Baumert, Golomb și Hall folosind construcția lui Williamson combinată cu căutarea pe computer. În prezent se arată că matricele Hadamard există pentru toate pentru . ${\pm }1$ $m\,\equiv \,0\mod 4$ $m<668$

Vezi și

Note

Literatură

Paley REAC Despre matrici ortogonale // Journal of Mathematics and Physics. - 1933. - T. 12 . — S. 311–320 .
Baumert LD, Golomb SW , Hall M. Jr. Descoperirea unei matrice Hadamard de ordinul 92 // Bull. amer. Matematică. Soc .. - 1962. - T. 68 , nr. 3 . — S. 237–238 . - doi : 10.1090/S0002-9904-1962-10761-7 .
MacWilliams FJ, Sloane NJA Teoria codurilor de corectare a erorilor . - 1977. - S. 47 , 56. - ISBN 0-444-85193-3 .