Paleys konstruktion

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 25. marts 2021; verifikation kræver 1 redigering .

Paley-konstruktionen er en metode til at konstruere Hadamard-matricer ved hjælp af et begrænset felt . Konstruktionen blev beskrevet i 1933 af den engelske matematiker Raymond Paley .

Paleys konstruktion bruger kvadratiske rester i et endeligt felt GF ( q ), hvor q er en potens af et ulige primtal . Der er to versioner af konstruktionen, afhængig af om q er kongruent med 1 eller 3 modulo 4.

Den firkantede karakter og Jacobstal-matrixen

Det kvadratiske tegn angiver, om element a i det endelige felt er et perfekt kvadrat . Især hvis for et eller andet ikke-nul-element i det endelige felt b , og hvis a ikke er kvadratet af et element i det endelige felt. For eksempel er i GF (7) , , og kvadrater, der ikke er nul . Derfor, og . $\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$

Jacobstal-matricen Q for er en matrix med rækker og kolonner indekseret af elementer i et endeligt felt, således at elementet i række a og kolonne b er . For eksempel, i GF (7), hvis rækkerne og kolonnerne i Jacobstal-matricen er indekseret af feltelementerne 0, 1, 2, 3, 4, 5, 6, $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&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&0\end{bmatrix}}.

Jacobstal-matricen har egenskaberne og , hvor E er identitetsmatrixen , og J er lig med matrixen, hvor alle elementer er lig med -1. Hvis q er kongruent med 1 (mod 4), så er −1 et kvadrat i GF ( q ), hvilket betyder, at Q er en symmetrisk matrix . Hvis q er kongruent med 3 (mod 4), så er −1 ikke et kvadrat, og Q er en skæv-symmetrisk matrix . Hvis q er primtal, er Q en cirkulant . Det vil sige, at hver række opnås fra rækken ovenfor ved en cyklisk permutation. $QQ^{T}=qE-J$ $QJ=JQ=0$ $q{\times }q$ $q{\times }q$

Konstruktion af Paley I

Hvis q er sammenlignelig med 3 (mod 4), så

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

er en Hadamard matrix af størrelse . Her er j en kolonnevektor med længden q bestående af -1, og E er identitetsmatrixen. Matricen H er en skæv- Hadamard matrix , hvilket betyder, at den opfylder ligheden . $q+1$ $(q+1)\ gange (q+1)$ $H+H^{T}=2E$

Konstruktion af Paley II

Hvis q er sammenlignelig med 1 (mod 4), opnås matrixen ved at erstatte alle 0'er i

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

til matrix

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

og alle elementer til matrixen ${\pm }1$

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

er en Hadamard matrix af størrelse . Dette er en symmetrisk Hadamard matrix. $2(q+1)$

Eksempler

Hvis vi anvender konstruktionen af Paley I på Jacobstal-matricen for GF (7), får vi Hadamard-matricen, $8{\times }8$

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

Som et eksempel på en Paley II-konstruktion, hvor q er en potens af et primtal snarere end et primtal, kan du overveje GF (9). Dette er en forlængelse af feltet GF (3), opnået ved at tilføje roden af et irreducerbart kvadratisk polynomium . Forskellige irreducerbare kvadratiske polynomier giver ækvivalente felter. Hvis vi også vælger roden a af dette polynomium, kan de ni elementer i GF (9) skrives som . Og vil være kvadrater, der ikke er nul . Jacobstal-matricen er $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&1&1&0&1&1&-1&-1\\1&-1&-1&1&1&0&-1&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&0\end{bmatrix}}.

Dette er en symmetrisk matrix bestående af cirkulære blokke. Konstruktionen af Paley II giver en symmetrisk Hadamard matrix, $3 gange 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---.

Hadamards formodning

Størrelsen af Hadamard-matricen skal være lig med 1, 2 eller et multiplum af 4. Kronecker-produktet af to Hadamard-matricer af størrelserne m og n vil være en Hadamard-matrix af størrelsen mn . Ved dannelse af Kronecker-produktet af matricer fra Paley-konstruktionen og matrixen, $2 gange 2$

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

man opnår Hadamard-matricer af enhver tilladelig størrelse op til 100 undtagen 92. I sit papir fra 1933 siger Paley: "Det er ret sandsynligt, at i det tilfælde, hvor m er delelig med 4, kan man konstruere en ortogonal matrix af orden m , bestående af , men den generelle sætning har en række vanskeligheder." Dette ser ud til at være den første offentliggørelse af en erklæring om Hadamard-formodningen . Matrixen med 92 størrelser blev til sidst konstrueret af Baumert, Golomb og Hall ved hjælp af Williamsons konstruktion kombineret med computersøgning. Det er i øjeblikket vist, at Hadamard-matricer findes for alle for . ${\pm }1$ $m\,\equiv \,0\mod 4$ $m<668$

Se også

Noter

Litteratur

Paley REAC Om ortogonale matricer // Journal of Mathematics and Physics. - 1933. - T. 12 . — S. 311–320 .
Baumert LD, Golomb SW , Hall M. Jr. Opdagelse af en Hadamard-matrix af orden 92 // Bull. amer. Matematik. Soc .. - 1962. - T. 68 , no. 3 . — S. 237–238 . - doi : 10.1090/S0002-9904-1962-10761-7 .
MacWilliams FJ, Sloane NJA Theory of Error-Correcting Codes . - 1977. - S. 47 , 56. - ISBN 0-444-85193-3 .