Конструкция Пэли - Википедия - Paley construction

В математика, то Строительство Пейли это метод построения Матрицы Адамара с помощью конечные поля. Строительство было описано в 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 м , эквив , 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.