Paley konstrukcja

W matematyce konstrukcja Paleya jest metodą konstruowania macierzy Hadamarda przy użyciu pól skończonych . Konstrukcję opisał w 1933 roku angielski matematyk Raymond Paley .

Konstrukcja Paleya wykorzystuje reszty kwadratowe w ciele skończonym GF ( q ), gdzie q jest potęgą nieparzystej liczby pierwszej . Istnieją dwie wersje konstrukcji w zależności od tego, czy q jest przystające do 1 czy 3 (mod 4).

Charakter kwadratowy i macierz Jacobsthal

Niech q będzie potęgą nieparzystej liczby pierwszej. W polu skończonym GF ( q ) znak kwadratowy χ ( a ) wskazuje, czy element a jest równy zeru, niezerowemu doskonałemu kwadratowi, czy nie-kwadratowemu:

{\ Displaystyle \ chi (a) = {\ rozpocząć {przypadki} 0 & {\ tekst {jeśli}} a = 0 \\1 & {\ tekst {jeśli}} a = b ^ {2} {\ tekst {dla niektórych nie -zero element pola skończonego }}b\\-1&{\text{if }}a{\text{ nie jest kwadratem żadnego elementu ciała skończonego.}}\end{przypadki}}}

Na przykład w GF (7) niezerowe kwadraty to 1 = 1 ² = 6 ² , 4 = 2 ² = 5 ² i 2 = 3 ² = 4 ² . Stąd χ(0) = 0, χ(1) = χ(2) = χ(4) = 1 i χ(3) = χ(5) = χ(6) = −1.

Macierz Jacobsthala Q dla GF ( q ) to macierz q × q z wierszami i kolumnami indeksowanymi przez elementy pola skończonego , tak że wpis w wierszu a i kolumnie b to χ ( a - b ). Na przykład w GF (7), jeśli wiersze i kolumny macierzy Jacobsthal są indeksowane przez elementy pola 0, 1, 2, 3, 4, 5, 6, to

{\ Displaystyle Q = {\ rozpocząć {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&0&- 1&-1\\-1&1&-1&1&1&0&-1\\-1&-1&1&-1&1&1&0\koniec{bmacierz}}.}

Macierz Jacobsthal ma właściwości QQ ^T = q I - J i QJ = JQ = 0, gdzie I jest macierzą identyczności q × q , a J jest macierzą q × q wszystkich 1. Jeśli q jest przystające do 1 (mod 4), to −1 jest kwadratem w GF ( q ), co implikuje, że Q jest macierzą symetryczną . jeśli q jest przystający do 3 (mod 4), to −1 nie jest kwadratem, a Q jest macierzą skośno-symetryczną . Kiedy q jest liczbą pierwszą, a wiersze i kolumny są indeksowane elementami pola w zwykłym porządku 0, 1, 2,…, Q jest macierzą krążącą . Oznacza to, że każdy wiersz jest uzyskiwany z wiersza powyżej przez permutację cykliczną.

Konstrukcja Paleya I

Jeśli q jest przystające do 3 (mod 4), to

{\ Displaystyle H = ja + {\ rozpocząć {bmatrix} 0 i j ^ {T} \\ - j & Q \ koniec {bmatrix}}}

jest macierzą Hadamarda o rozmiarze q + 1. Tutaj j to wektor kolumnowy all-1 o długości q , a I to ( q +1) × ( q +1) macierz identyczności. Macierz H jest skośną macierzą Hadamarda , co oznacza, że spełnia H + H ^T = 2 I .

Paley konstrukcja II

Jeśli q jest przystające do 1 (mod 4), to macierz uzyskana przez zastąpienie wszystkich wpisów 0 w

{\ Displaystyle {\ rozpocząć {bmatrix} 0 i j ^ {T} \\ j&Q \ koniec {bmatrix}}}

z matrixem

{\ Displaystyle {\ rozpocząć {bmatrix} 1 i -1 \\ -1 i -1 \ koniec {bmatrix}}}

a wszystkie wpisy ±1 z macierzą

{\ Displaystyle \ pm {\ rozpocząć {bmatrix} 1 i 1 \\ 1 i -1 \ koniec {bmatrix}}}

jest macierzą Hadamarda o rozmiarze 2 ( q + 1). Jest to symetryczna macierz Hadamarda.

Przykłady

Stosując Konstrukcję Paleya I do macierzy Jacobsthala dla GF (7), uzyskuje się macierz Hadamarda 8 × 8,

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

Jako przykład konstrukcji Paleya II, gdy q jest potęgą pierwszą, a nie liczbą pierwszą, rozważmy GF (9). Jest to pole rozszerzenia GF (3 ) otrzymane przez dołączenie pierwiastka nierozkładalnej kwadratowej . Różne nieredukowalne kwadraty wytwarzają równoważne pola. Wybierając x ² + x −1 i przyjmując, że a będzie pierwiastkiem tego wielomianu, dziewięć elementów GF (9) można zapisać jako 0, 1, −1, a , a +1, a -1, - za , - za +1, - za -1. Kwadraty niezerowe to 1 = (±1) ² , − a +1 = (± a ) ² , a −1 = (±( a +1)) ² i −1 = (±( a −1) ) ² . Macierz Jacobsthal jest

{\ Displaystyle Q = {\ zacząć {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&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&0&1\\-1&1&-1&1& -1&-1&1&1&0\koniec{bmacierz}}.}

Jest to symetryczna macierz składająca się z dziewięciu krążących bloków 3 × 3. Paley Construction II produkuje symetryczną macierz Hadamarda 20×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---.

Hipoteza Hadamarda

Rozmiar macierzy Hadamarda musi wynosić 1, 2 lub wielokrotność 4. Iloczyn Kroneckera dwóch macierzy Hadamarda o rozmiarach m i n jest macierzą Hadamarda o rozmiarze mn . Tworząc produkty Kroneckera macierzy z konstrukcji Paleya i macierzy 2×2,

{\ Displaystyle H_ {2} = {\ rozpocząć {bmatrix} 1 i 1 \\ 1 i -1 \ koniec {bmatrix}}}

Produkowane są matryce Hadamarda we wszystkich dopuszczalnych rozmiarach do 100 z wyjątkiem 92. W swoim artykule z 1933 r. Paley mówi: „Wydaje się prawdopodobne, że ilekroć m jest podzielne przez 4, możliwe jest skonstruowanie macierzy ortogonalnej rzędu m złożonej z ± 1, ale ogólne twierdzenie ma wszelkie pozory trudności”. Wydaje się, że jest to pierwsze opublikowane stwierdzenie hipotezy Hadamarda . Macierz o rozmiarze 92 została ostatecznie skonstruowana przez Baumerta, Golomba i Halla , wykorzystując konstrukcję Williamsona połączoną z wyszukiwaniem komputerowym. Obecnie wykazano, że macierze Hadamarda $istnieją$ m 668 .

Zobacz też

Paley, REAC (1933). „O macierzach ortogonalnych”. Dziennik matematyki i fizyki . 12 : 311–320. doi : 10.1002/sapm1933121311 . Zbl 0007.10004 .
LD Baumert; SW Golomb ; M. Hall Jr. (1962). „Odkrycie macierzy Hadamarda rzędu 92” . Byk. Amer. Matematyka soc . 68 (3): 237–238. doi : 10.1090/S0002-9904-1962-10761-7 .
FJ MacWilliams ; NJA Sloane (1977). Teoria kodów korygujących błędy . Holandia Północna. s. 47 , 56. ISBN 0-444-85193-3 .