Палейское строительство

В математике конструкция Пэли — это метод построения матриц Адамара с использованием конечных полей . Конструкция была описана в 1933 году английским математиком Раймондом Пейли .

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

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

Пусть q — степень нечетного простого числа. В конечном поле GF( q ) квадратичный характер χ( a ) указывает, является ли элемент a нулем, ненулевым квадратом или неквадратом:

\chi (a)={\begin{cases}0&{\text{if }}a=0\\1&{\text{if }}a=b^{2}{\text{ for some non-zero }}b\in \mathrm {GF} (q)\\-1&{\text{if }}a{\text{ is not the square of any element in }}\mathrm {GF} (q).\end{cases}}

Например, в GF(7) ненулевые квадраты равны 1 = 1. ² = 6 ², 4 = 2 ² = 5 ², и 2 = 3 ² = 4 ². Следовательно, χ(0) = 0, χ(1) = χ(2) = χ(4) = 1 и χ(3) = χ(5) = χ(6) = −1.

Матрица Якобсталя q Q для GF( q ) — это q × со строками и столбцами , матрица индексированными элементами GF( q ), такая, что запись в строке a и столбце b равна χ( 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}}.

Матрица Якобсталя обладает свойствами QQ ^Т = qI − J и QJ = JQ = 0, где I — q × q единичная матрица , а J — матрица q × q все 1 . Если q конгруэнтно 1 по модулю 4, то −1 является квадратом в GF( q ) откуда следует, что Q — симметричная матрица . Если q конгруэнтно 3 по модулю 4, то −1 не является квадратом, а Q — кососимметричная матрица . Когда q — простое число, а строки и столбцы индексируются элементами поля в обычном порядке 0, 1, 2,…, Q — циркулянтная матрица . То есть каждая строка получается из строки выше путем циклической перестановки .

Палейская конструкция I

Если q конгруэнтно 3 по модулю 4, то

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

— матрица Адамара размера q + 1. Здесь j — вектор-столбец «все 1» длины q , а I — единичная матрица ( q +1)×( q +1). Матрица H является косой матрицей Адамара , что означает, что она удовлетворяет условию H + H. ^Т = 2 я .

Палейское строительство II

Если q конгруэнтно 1 по модулю 4, то матрица, полученная заменой всех 0 элементов в

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

с матрицей

{\begin{bmatrix}1&-1\\-1&-1\end{bmatrix}}

и все записи ±1 с матрицей

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

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

Примеры

Применяя конструкцию Пэли I к матрице Якобсталя для GF(7), получаем матрицу Адамара 8 × 8:

{\begin{bmatrix}1&1&1&1&1&1&1&1\\-1&1&-1&-1&1&-1&1&1\\-1&1&1&-1&-1&1&-1&1\\-1&1&1&1&-1&-1&1&-1\\-1&-1&1&1&1&-1&-1&1\\-1&1&-1&1&1&1&-1&-1\\-1&-1&1&-1&1&1&1&-1\\-1&-1&-1&1&-1&1&1&1\end{bmatrix}}.

В качестве примера конструкции Пэли II, когда q является степенью простого числа, а не простым числом, рассмотрим GF(9). Это поле расширения GF(3), полученное присоединением корня уравнения неприводимого квадратичного . Различные неприводимые квадратичные дроби создают эквивалентные поля. Выбор х ²+ x −1 и если a является корнем этого многочлена , девять элементов GF(9) можно записать 0, 1, −1, a , a +1, a −1, − a , − a +1, − а −1. Ненулевые квадраты: 1 = (±1) ², − а +1 = (± а ) ², а −1 = (±( а +1)) ², и −1 = (±( a −1)) ². Матрица Якобсталя

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×3. Paley Construction II создает симметричную матрицу Адамара 20 × 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 × 2,

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

Создаются матрицы Адамара всех допустимых размеров до 100, кроме 92. В своей статье 1933 года Пейли говорит: «Кажется вероятным, что всякий раз, когда m делится на 4, можно построить ортогональную матрицу порядка m, составленную из ±1, но общая теорема имеет все видимые трудности». Похоже, это первое опубликованное утверждение гипотезы Адамара . Матрица размера 92 была в конечном итоге построена Баумертом, Голомбом и Холлом , используя конструкцию Уильямсона в сочетании с компьютерным поиском. В настоящее время показано, что матрицы Адамара существуют для всех $m\,\equiv \,0\mod 4$ для м < 668.

См. также

Ссылки

Пейли, REAC (1933). «Об ортогональных матрицах». Журнал математики и физики . 12 : 311–320. дои : 10.1002/sapm1933121311 . Збл 0007.10004 .
Л.Д. Баумерт; SW Голомб ; М. Холл-младший (1962). «Открытие матрицы Адамара 92-го порядка» . Бык. амер. Математика. Соц . 68 (3): 237–238. дои : 10.1090/S0002-9904-1962-10761-7 .
Ф. Дж. МакВильямс ; НЯА Слоан (1977). Теория кодов, исправляющих ошибки . Северная Голландия. стр. 47 , 56. ISBN. 0-444-85193-3 .