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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

[править | править код]

Квадратный характер показывает, является ли элемент a конечного поля полным квадратом. В частности, , если для некоторого ненулевого элемента конечного поля b, и , если a не является квадратом какого-либо элемента конечного поля. Например, в GF(7) ненулевыми квадратами являются , и . Следовательно, и .

Матрица Якобсталя Q для является матрицей со строками и столбцами, индексированными элементами конечного поля, такой, что элемент в строке a и столбце b равен . Например, в GF(7), если строки и столбцы матрицы Якобсталя индексированы элементами поля 0, 1, 2, 3, 4, 5, 6, то

Матрица Якобсталя имеет свойства и , где E единичная матрица, а J равна матрице, в которой все элементы равны -1. Если q сравнимо с 1 (mod 4), то −1 является квадратом в GF(q), откуда следует, что Q является симметричной матрицей. Если q сравнимо с 3 (mod 4), то −1 не является квадратом и Q является кососимметричной матрице. Если q — простое число, Q является циркулянтом. То есть каждая строка получается из строки выше циклической перестановкой.

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

[править | править код]

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

является матрицей Адамара размера . Здесь jвектор-столбец длины q, состоящий из -1, а E единичная матрица. Матрица H является косоадамаровой матрицей, это означает, что она удовлетворяет равенству .

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

[править | править код]

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

на матрицу

,

а всех элементов на матрицу

,

является матрицей Адамара размера . Это симметричная матрица Адамара.

Если применить построение Палея I к матрице Якобсталя для GF(7), получим матрицу Адамара,

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

В качестве примера построения Палея II, когда q является степенью простого, а не простым числом, рассмотрим GF(9). Это расширение поля GF(3), полученная добавлением корня неприводимого квадратного многочлена. Различные неприводимые квадратные многочлены дают эквивалентные поля. Если выбрать и корень a этого многочлена, девять элементов GF(9) могут быть записаны в виде . Ненулевыми квадратами будут и . Матрица Якобсталя равна

Это симметричная матрица состоящая из циркулярных блоков. Построение Палея II даёт симметричную матрицу Адамара,

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. При образовании произведения Кронекера матриц из построения Палея и матрицы,

получаются матрицы Адамара любого допустимого размера вплоть до 100, за исключением 92. В своей статье 1933 год Палей говорит: «Вполне вероятно, что в случае, когда m делится на 4, можно построить ортогональную матрицу порядка m, состоящую из , но общая теорема имеет ряд трудностей.» Это, по-видимому, первая публикация утверждения гипотезы Адамара. Матрицу размера 92, в конце концов, построили Баумерт, Голомб и Холл с помощью построения Вильямсона, совмещённого с компьютерным поиском. В настоящее время показано, что матрицы Адамара существуют для всех для .

Примечания

[править | править код]

Литература

[править | править код]
  • Paley R.E.A.C. On orthogonal matrices // Journal of Mathematics and Physics. — 1933. — Т. 12. — С. 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. — С. 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.