Строительство Пейли - Paley construction - Wikipedia

В математика, то Строительство Пейли это метод построения Матрицы Адамара с помощью конечные поля. Строительство было описано в 1933 г. английский математик Раймонд Пейли.

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

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

Квадратичный персонаж χ (а) указывает, что данный конечный элемент поля а идеальный квадрат. В частности, χ (0) = 0, χ (а) = 1, если а = б² для некоторого ненулевого элемента конечного поля б, а χ (а) = −1, если а не является квадратом какого-либо элемента конечного поля. Например, в GF(7) ненулевые квадраты равны 1 = 1² = 6², 4 = 2² = 5², и 2 = 3² = 4². Следовательно, χ (0) = 0, χ (1) = χ (2) = χ (4) = 1 и χ (3) = χ (5) = χ (6) = −1.

В Jacobsthal матрица Q за GF(q) это q×q матрица со строками и столбцами, проиндексированными элементами конечного поля, так что запись в строке а и столбец б есть χ (а − б). Например, в GF(7), если строки и столбцы матрицы Якобсталя индексируются элементами поля 0, 1, 2, 3, 4, 5, 6, то

${\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}}.}$

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

Конструкция Пэли I

Если q конгруэнтно 3 (mod 4), то

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

матрица Адамара размера q + 1. Здесь j вектор-столбец длины q и я это (q+1)×(q+1) единичная матрица. Матрица ЧАС это перекос матрицы Адамара, что означает, что он удовлетворяет ЧАС+ЧАС^Т = 2я.

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

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

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

с матрицей

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

и все элементы ± 1 с матрицей

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

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

Примеры

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

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

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

${\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}}.}$

Это симметричная матрица, состоящая из девяти циркулянтных блоков 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--111 111-11 11---- ----111- 1---1- 1--1-1 -1-11-11 11111- --11-- 11----1- 1-1--- -11--1 1--1-111 --11-- 1-1111 ----111- -11--1 --1-1- -1-11-11 ----11 111-11 11----1- -1-11- 1---1- 1--1-111 11---- 11111- --11--1- 1--1-1 1-1--- -11--111 ----11 --11-- 1-11111- -1-11- -11--1 --1-1-11 11---- ----11 111-111- 1--1-1 -1-11- 1---1-11 --11-- 11---- 11111-1- -11--1 1--1-1 1-1---.

Гипотеза Адамара

Размер матрицы Адамара должен быть 1, 2 или кратным 4. Кронекер продукт двух матриц Адамара размеров м и п матрица Адамара размера мин. Формируя произведения Кронекера матриц из конструкции Пэли и матрицы 2 × 2,

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

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

Смотрите также

• Биплан Пэли
• Граф Пэли

Рекомендации

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