Построение Палея

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

Построение Палея использует квадратичные вычеты в конечном поле GF(q), где q является степенью нечётного простого числа. Имеется две версии построения, зависящие от того, q сравнимо с 1 или 3 по модулю 4.

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

Квадратный характер [math]\displaystyle{ \chi(a) }[/math] показывает, является ли элемент a конечного поля полным квадратом. В частности, [math]\displaystyle{ \chi(0) = 0, \chi(a) = 1 }[/math], если [math]\displaystyle{ a = b^2 }[/math] для некоторого ненулевого элемента конечного поля b, и [math]\displaystyle{ \chi(a) = -1 }[/math], если a не является квадратом какого-либо элемента конечного поля. Например, в GF(7) ненулевыми квадратами являются [math]\displaystyle{ 1 = 1^2 = 6^2 }[/math], [math]\displaystyle{ 4 = 2^2 = 5^2 }[/math] и [math]\displaystyle{ 2 = 3^2 = 4^2 }[/math]. Следовательно, [math]\displaystyle{ \chi(0) = 0, \chi(1) = \chi(2) = \chi(4) = 1 }[/math] и [math]\displaystyle{ \chi(3) = \chi(5) = \chi(6) = -1 }[/math].

Матрица Якобсталя Q для [math]\displaystyle{ GF(q) }[/math] является [math]\displaystyle{ q{\times}q }[/math] матрицей со строками и столбцами, индексированными элементами конечного поля, такой, что элемент в строке a и столбце b равен [math]\displaystyle{ \chi(a - b) }[/math]. Например, в GF(7), если строки и столбцы матрицы Якобсталя индексированы элементами поля 0, 1, 2, 3, 4, 5, 6, то

[math]\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}. }[/math]

Матрица Якобсталя имеет свойства [math]\displaystyle{ QQ^T = qE - J }[/math] и [math]\displaystyle{ QJ = JQ = 0 }[/math], где E — [math]\displaystyle{ q{\times}q }[/math] единичная матрица, а J равна [math]\displaystyle{ q{\times}q }[/math] матрице, в которой все элементы равны -1. Если q сравнимо с 1 (mod 4), то −1 является квадратом в GF(q), откуда следует, что Q является симметричной матрицей. Если q сравнимо с 3 (mod 4), то −1 не является квадратом и Q является кососимметричной матрице. Если q — простое число, Q является циркулянтом. То есть каждая строка получается из строки выше циклической перестановкой.

Построение Палея I

Если q сравнимо с 3 (mod 4), то

[math]\displaystyle{ H=E+\begin{bmatrix} 0 & j^T\\ -j & Q\end{bmatrix} }[/math]

является матрицей Адамара размера [math]\displaystyle{ q + 1 }[/math]. Здесь j — вектор-столбец длины q, состоящий из -1, а E — [math]\displaystyle{ (q+1)\times(q+1) }[/math] единичная матрица. Матрица H является косоадамаровой матрицей, это означает, что она удовлетворяет равенству [math]\displaystyle{ H+H^T = 2E }[/math].

Построение Палея II

Если q сравнимо с 1 (mod 4), то матрица, полученная заменой всех 0 в

[math]\displaystyle{ \begin{bmatrix} 0 & j^T\\ j & Q\end{bmatrix} }[/math]

на матрицу

[math]\displaystyle{ \begin{bmatrix} 1 & -1\\ -1 & -1\end{bmatrix} }[/math],

а всех элементов [math]\displaystyle{ {\pm}1 }[/math] на матрицу

[math]\displaystyle{ \pm\begin{bmatrix} 1 & 1\\ 1 & -1\end{bmatrix} }[/math],

является матрицей Адамара размера [math]\displaystyle{ 2(q + 1) }[/math]. Это симметричная матрица Адамара.

Примеры

Если применить построение Палея I к матрице Якобсталя для GF(7), получим [math]\displaystyle{ 8{\times}8 }[/math] матрицу Адамара,

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

В качестве примера построения Палея II, когда q является степенью простого, а не простым числом, рассмотрим GF(9). Это расширение поля GF(3), полученная добавлением корня неприводимого квадратного многочлена. Различные неприводимые квадратные многочлены дают эквивалентные поля. Если выбрать [math]\displaystyle{ x^2+x-1 }[/math] и корень a этого многочлена, девять элементов GF(9) могут быть записаны в виде [math]\displaystyle{ 0, 1, -1, a, a+1, a-1, -a, -a+1, -a-1 }[/math]. Ненулевыми квадратами будут [math]\displaystyle{ 1 = ({\pm}1)^2, -a+1 = ({\pm}a)^2, a-1 = (\pm(a+1))^2 }[/math] и [math]\displaystyle{ -1 = (\pm(a-1))^2 }[/math]. Матрица Якобсталя равна

[math]\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}. }[/math]

Это симметричная матрица состоящая из [math]\displaystyle{ 3 \times 3 }[/math] циркулярных блоков. Построение Палея II даёт симметричную [math]\displaystyle{ 20 \times 20 }[/math] матрицу Адамара,

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. При образовании произведения Кронекера матриц из построения Палея и [math]\displaystyle{ 2\times 2 }[/math] матрицы,

[math]\displaystyle{ H_2 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}, }[/math]

получаются матрицы Адамара любого допустимого размера вплоть до 100, за исключением 92. В своей статье 1933 год Палей говорит: «Вполне вероятно, что в случае, когда m делится на 4, можно построить ортогональную матрицу порядка m, состоящую из [math]\displaystyle{ {\pm}1 }[/math], но общая теорема имеет ряд трудностей.» Это, по-видимому, первая публикация утверждения гипотезы Адамара. Матрицу размера 92, в конце концов, построили Баумерт, Голомб и Холл с помощью построения Вильямсона, совмещённого с компьютерным поиском. В настоящее время показано, что матрицы Адамара существуют для всех [math]\displaystyle{ m \,\equiv\, 0 \mod 4 }[/math] для [math]\displaystyle{ m \lt 668 }[/math].

См. также

• Биплоскость Палея
• Граф Пэли