Побудова Пелі

Побудова Пелі — це метод побудови матриць Адамара за допомогою скінченного поля. Побудову описав 1933 року англійський математик Реймонд Пелі.

Побудова Пелі використовує квадратичні лишки в скінченному полі GF(q), де q є степенем непарного простого числао. Є дві версії побудови, що залежать від того, q порівнянне з 1 чи 3 за модулем 4.

Квадратний характер і матриця Якобсталя

Квадратний характер $\chi (a)$ показує, чи є елемент a скінченного поля повним квадратом. Зокрема, $\chi (0)=0,\chi (a)=1$, якщо $a=b^{2}$ для деякого ненульового елемента скінченного поля b, і $\chi (a)=-1$, якщо a не є квадратом будь-якого елемента скінченного поля. Наприклад, в GF(7) ненульовими квадратами є $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$.

Матриця Якобсталя Q для $GF(q)$ є $q{\times }q$ матрицею з рядками і стовпцями, індексованими елементами скінченного поля, такою, що елемент у рядку a і стовпці b рівний $\chi (a-b)$. Наприклад, у GF(7), якщо рядки та стовпці матриці Якобсталя індексовані елементами поля 0, 1, 2, 3, 4, 5, 6, то

$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&0&-1&-1\\-1&1&-1&1&1&0&-1\\-1&-1&1&-1&1&1&0\end{bmatrix}}.$

Матриця Якобсталя має властивості $QQ^{T}=qE-J$ і $QJ=JQ=0$, де E — $q{\times }q$ одинична матриця, а J рівна $q{\times }q$ матриці, в якій усі елементи дорівнюють −1. Якщо q порівнянне з 1 (mod 4), то −1 є квадратом у GF(q), звідки випливає, що Q є симетричною матрицею. Якщо q порівнянне з 3 (mod 4), то −1 не є квадратом і Q є кососиметричною матрицею. Якщо q — просте число, Q є циркулянтом. Тобто кожен рядок виходить з рядка вище циклічною перестановкою.

Побудова Пелі I

Якщо q порівнянне з 3 (mod 4), то

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

є матрицею Адамара розміру $q+1$. Тут j — вектор-стовпець довжини q, що складається з −1, а E — $(q+1)\times (q+1)$ одинична матриця. Матриця H є косоадамаровою матрицею, це означає, що вона задовольняє рівності $H+H^{T}=2E$.

Побудова Пелі II

Якщо q порівнянне з 1 (mod 4), то матриця, отримана заміною всіх 0 у

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

на матрицю

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

а всіх елементів ${\pm }1$ на матрицю

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

є матрицею Адамара розміру $2(q+1)$. Це симетрична матриця Адамара.

Приклади

Якщо застосувати побудову Пелі I до матриці Якобсталя для GF(7), отримаємо $8{\times }8$ матрицю Адамара,

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

Як приклад побудови Пелі II, коли q є степенем простого, а не простим числом, розглянемо GF(9). Це розширення поля GF(3), отримане додаванням кореня незвідного квадратного многочлена. Різні незвідні квадратні многочлени дають еквівалентні поля. Якщо вибрати $x^{2}+x-1$ і корінь a цього многочлена, дев'ять елементів GF(9) можна записати у вигляді $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&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\end{bmatrix}}.$

Це симетрична матриця, що складається з $3\times 3$ циркулярних блоків. Побудова Пелі II дає симетричну $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---.

Гіпотеза Адамара

Розмір матриці Адамара має дорівнювати 1, 2 або бути кратним 4. Добуток Кронекера двох матриць Адамара розмірів m і n буде матрицею Адамара розміру mn. При утворенні добутку Кронекера матриць з побудови Пелі і $2\times 2$ матриці,

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

виходять матриці Адамара будь-якого допустимого розміру аж до 100, за винятком 92. У статті 1933 Пелі каже: «Цілком імовірно, що у випадку, коли m ділиться на 4, можна побудувати ортогональну матрицю порядку m, що складається з ${\pm }1$, але загальна теорема має низку труднощів». Це, мабуть, перша публікація твердження гіпотези Адамара. Матрицю розміру 92, зрештою, побудували Баумерт, Ґоломб і Голл за допомогою побудови Вільямсона, поєднаної з комп'ютерним пошуком. Нині показано, що матриці Адамара існують для всіх $m\,\equiv \,0\mod 4$ для $m<668$.

Див. також

• Біплощина Пелі
• Граф Пелі

Література

• Paley R.E.A.C. On orthogonal matrices // Journal of Mathematics and Physics. — 1933. — Т. 12 (21 квітня). — С. 311–320.
• Baumert L. D., Golomb S. W., Hall M. Jr. Discovery of an Hadamard matrix of order 92 // Bull. Amer. Math. Soc.. — 1962. — Т. 68, вип. 3 (21 квітня). — С. 237–238. — DOI:10.1090/S0002-9904-1962-10761-7.
• MacWilliams F.J., Sloane N.J.A. The Theory of Error-Correcting Codes. — 1977. — С. 47, 56. — ISBN 0-444-85193-3.