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

Побудова Пелі — це метод побудови матриць Адамара за допомогою скінченного поля. Побудову описав 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=\left[\begin{array}{ccccccc}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{array}\right].$

Матриця Якобсталя має властивості $Q{Q}^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+\left[\begin{array}{cc}0& j^T\\ -j& Q\end{array}\right]$

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

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

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

$\left[\begin{array}{cc}0& j^T\\ j& Q\end{array}\right]$

на матрицю

$\left[\begin{array}{cc}1& -1\\ -1& -1\end{array}\right]$,

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

$\pm \left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$,

є матрицею Адамара розміру $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=\left[\begin{array}{ccccccccc}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{array}\right].$

Це симетрична матриця, що складається з

$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=\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right],$

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

Див. також

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

Література

• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга