Paleyn rakentaminen

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25. maaliskuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Paley-konstruktio on menetelmä Hadamard-matriisien muodostamiseksi äärellisen kentän avulla . Rakennuksen kuvasi vuonna 1933 englantilainen matemaatikko Raymond Paley .

Paleyn konstruktio käyttää neliöllisiä jäännöksiä äärellisessä kentässä GF ( q ), jossa q on parittoman alkuluvun potenssi . Rakenteesta on kaksi versiota riippuen siitä, onko q yhtäpitävä 1 vai 3 modulo 4:n kanssa.

Neliömerkki ja Jacobstal-matriisi

Neliömerkki ilmaisee, onko äärellisen kentän elementti a täydellinen neliö . Erityisesti jos jollekin äärellisen kentän nollasta poikkeavalle alkiolle b , ja jos a ei ole minkä tahansa äärellisen kentän alkion neliö. Esimerkiksi GF :ssä (7) , , ja ovat nollasta poikkeavia neliöitä . Siksi ja . $\chi(a)$ ${\näyttötyyli \chi (0)=0,\chi (a)=1}$ $a=b^{2}$ ${\näyttötyyli \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-matriisi Q for on matriisi, jossa rivit ja sarakkeet on indeksoitu äärellisen kentän elementeillä siten, että rivin a ja sarakkeen b elementti on . Esimerkiksi GF :ssä (7), jos Jacobstal-matriisin rivit ja sarakkeet indeksoidaan kenttäelementeillä 0, 1, 2, 3, 4, 5, 6, $GF(q)$ $q{\times }q$ ${\näyttötyyli \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{bmatrix}}.

Jacobstal-matriisilla on ominaisuudet ja , jossa E on identiteettimatriisi ja J on yhtä suuri kuin matriisi, jonka kaikki elementit ovat yhtä suuria kuin -1. Jos q on kongruentti 1:n kanssa (mod 4), niin −1 on neliö GF :ssä ( q ), mikä tarkoittaa, että Q on symmetrinen matriisi . Jos q on kongruentti 3:n kanssa (mod 4), niin −1 ei ole neliö ja Q on vinosymmetrinen matriisi . Jos q on alkuluku, Q on ympyrä . Toisin sanoen jokainen rivi saadaan yllä olevasta rivistä syklisellä permutaatiolla. $QQ^{T}=qE-J$ $QJ=JQ=0$ $q{\times }q$ $q{\times }q$

Paley I:n rakentaminen

Jos q on verrattavissa 3:een (mod 4), niin

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

on Hadamard-matriisi, jonka koko on . Tässä j on sarakevektori, jonka pituus on q ja joka koostuu arvosta -1, ja E on identiteettimatriisi. Matriisi H on vino- Hadamard-matriisi , mikä tarkoittaa, että se täyttää yhtälön . $q+1$ ${\näyttötyyli (q+1)\times (q+1)}$ $H+H^{T}=2E$

Paley II:n rakentaminen

Jos q on verrattavissa 1:een (mod 4), niin matriisi, joka saadaan korvaamalla kaikki 0:t

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

matriisiin

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

ja kaikki elementit matriisiin ${\pm }1$

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

on Hadamard-matriisi, jonka koko on . Tämä on symmetrinen Hadamard-matriisi. ${\näyttötyyli 2(q+1)}$

Esimerkkejä

Jos soveltamme Paley I:n konstruktiota Jacobstal-matriisiin GF :lle (7), saamme Hadamard-matriisin, $8{\times }8$

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

Esimerkkinä Paley II -konstruktiosta, jossa q on alkuluvun potenssi alkuluvun sijaan, harkitse GF (9). Tämä on kentän GF (3) laajennus , joka saadaan lisäämällä pelkistymättömän neliöpolynomin juuri . Erilaiset redusoitumattomat neliöpolynomit antavat vastaavat kentät. Jos valitsemme myös tämän polynomin juuren a , GF :n (9) yhdeksän alkiota voidaan kirjoittaa muodossa . Ja ne ovat nollasta poikkeavia neliöitä . Jacobstal-matriisi on $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{bmatrix}}.

Tämä on symmetrinen matriisi, joka koostuu pyöreistä lohkoista. Paley II:n rakenne antaa symmetrisen Hadamard-matriisin, $3 kertaa 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---.

Hadamardin arvelu

Hadamard-matriisin koon on oltava yhtä suuri kuin 1, 2 tai 4:n kerrannainen. Kahden Hadamard-matriisin, joiden koko on m ja n , Kronecker -tulo on Hadamard-matriisi, jonka koko on mn . Kun muodostetaan matriisien Kronecker-tulo Paley-konstruktiosta ja matriisista, $2 kertaa 2$

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

saadaan Hadamard-matriisit, joiden koko on sallittu aina 100 asti lukuun ottamatta 92:ta. Paley sanoo vuoden 1933 artikkelissaan: "On melko todennäköistä, että tapauksessa, jossa m on jaollinen 4:llä, voidaan rakentaa ortogonaalinen matriisi , jonka kertaluku on m ja joka koostuu , mutta yleisessä lauseessa on useita vaikeuksia." Tämä näyttää olevan ensimmäinen julkaisu Hadamardin olettamuksesta . 92-koon matriisin rakensivat lopulta Baumert, Golomb ja Hall käyttämällä Williamsonin rakennetta yhdistettynä tietokonehakuun. Tällä hetkellä on osoitettu, että Hadamard-matriiseja on olemassa kaikille varten . ${\pm }1$ $m\,\equiv \,0\mod 4$ $m<668$

Katso myös

Muistiinpanot

Kirjallisuus

Paley REAC ortogonaalisista matriiseista // Journal of Mathematics and Physics. - 1933. - T. 12 . — S. 311–320 .
Baumert LD, Golomb SW , Hall M. Jr. Hadamard-matriisin löytäminen luokkaa 92 // Tiedote. amer. Matematiikka. Soc .. - 1962. - T. 68 , no. 3 . — S. 237–238 . - doi : 10.1090/S0002-9904-1962-10761-7 .
MacWilliams FJ, Sloane NJA Virheenkorjauskoodien teoria . - 1977. - S. 47 , 56. - ISBN 0-444-85193-3 .