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

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

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

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

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

Матрица Якобсталя Q для $GF(q)$$GF(q)$  является $q\times <!--\; \times \; -->q$$q{\times }q$  матрицей со строками и столбцами, индексированными элементами конечного поля, такой, что элемент в строке a и столбце b равен $\mathrm{\chi <!--\; \chi \; -->}(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}}.$ 

Матрица Якобсталя имеет свойства $Q{Q}^T=qE-<!--\; -\; -->J$$QQ^{T}=qE-J$  и $QJ=JQ=0$$QJ=JQ=0$ , где E — $q\times <!--\; \times \; -->q$$q{\times }q$  единичная матрица, а J равна $q\times <!--\; \times \; -->q$$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$$q+1$ . Здесь j — вектор-столбец длины q, состоящий из -1, а E — $(q+1)\times <!--\; \times \; -->(q+1)$$(q+1)\times (q+1)$  единичная матрица. Матрица H является косоадамаровой матрицей, это означает, что она удовлетворяет равенству $H+H^T=2E$$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 <!--\; \pm \; -->1$${\pm }1$  на матрицу

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

является матрицей Адамара размера $2(q+1)$$2(q+1)$ . Это симметричная матрица Адамара.

ПримерыПравить

Если применить построение Палея I к матрице Якобсталя для GF(7), получим $8\times <!--\; \times \; -->8$$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$$x^{2}+x-1$  и корень a этого многочлена, девять элементов GF(9) могут быть записаны в виде $0,1,-<!--\; -\; -->1,a,a+1,a-<!--\; -\; -->1,-<!--\; -\; -->a,-<!--\; -\; -->a+1,-<!--\; -\; -->a-<!--\; -\; -->1$$0,1,-1,a,a+1,a-1,-a,-a+1,-a-1$ . Ненулевыми квадратами будут $1=(\pm <!--\; \pm \; -->1{)}^2,-<!--\; -\; -->a+1=(\pm <!--\; \pm \; -->a{)}^2,a-<!--\; -\; -->1=(\pm <!--\; \pm \; -->(a+1){)}^2$$1=({\pm }1)^{2},-a+1=({\pm }a)^{2},a-1=(\pm (a+1))^{2}$  и $-<!--\; -\; -->1=(\pm <!--\; \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 <!--\; \times \; -->3$$3 \times 3$  циркулярных блоков. Построение Палея II даёт симметричную $20\times <!--\; \times \; -->20$$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 <!--\; \times \; -->2$$2\times 2$  матрицы,

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

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

См. такжеПравить

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