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

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

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

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

Квадратний ${\displaystyle \chi (a)}$ показує, чи є елемент a скінченного поля повним квадратом. Зокрема, ${\displaystyle \chi (0)=0,\chi (a)=1}$, якщо ${\displaystyle a=b^{2}}$ для деякого ненульового елемента скінченного поля b, і ${\displaystyle \chi (a)=-1}$, якщо a не є квадратом будь-якого елемента скінченного поля. Наприклад, в GF(7) ненульовими квадратами є ${\displaystyle 1=1^{2}=6^{2}}$, ${\displaystyle 4=2^{2}=5^{2}}$ і ${\displaystyle 2=3^{2}=4^{2}}$. Отже, ${\displaystyle \chi (0)=0,\chi (1)=\chi (2)=\chi (4)=1}$ і ${\displaystyle \chi (3)=\chi (5)=\chi (6)=-1}$.

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

${\displaystyle 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}}.}$

Матриця Якобсталя має властивості ${\displaystyle QQ^{T}=qE-J}$ і ${\displaystyle QJ=JQ=0}$, де E — ${\displaystyle q{\times }q}$ одинична матриця, а J рівна ${\displaystyle 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), то

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

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

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

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

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

на матрицю

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

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

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

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

Приклади

Якщо застосувати побудову Пелі I до матриці Якобсталя для GF(7), отримаємо ${\displaystyle 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), отримане додаванням кореня незвідного квадратного многочлена. Різні незвідні квадратні многочлени дають еквівалентні поля. Якщо вибрати ${\displaystyle x^{2}+x-1}$ і корінь a цього многочлена, дев'ять елементів GF(9) можна записати у вигляді ${\displaystyle 0,1,-1,a,a+1,a-1,-a,-a+1,-a-1}$. Ненульовими квадратами будуть ${\displaystyle 1=({\pm }1)^{2},-a+1=({\pm }a)^{2},a-1=(\pm (a+1))^{2}}$ і ${\displaystyle -1=(\pm (a-1))^{2}}$. Матриця Якобсталя дорівнює

${\displaystyle 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}}.}$

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

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

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

Див. також

• Граф Пелі

Примітки

Література

• Paley R.E.A.C. On orthogonal matrices // Journal of Mathematics and Physics. — 1933. — Т. 12 (1 липня). — С. 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 (1 липня). — С. 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. — .