В математике , то Палей конструкция представляет собой способ построения матриц Адамара с использованием конечных полей . Конструкция была описана в 1933 году английским математиком Раймондом Пэли .
Конструкция Пэли использует квадратичные вычеты в конечном поле GF ( q ), где q - степень нечетного простого числа . Есть две версии конструкции в зависимости от того, конгруэнтно q 1 или 3 (mod 4).
Квадратичный характер и матрица Якобсталя
Квадратичный характер χ ( a ) указывает, является ли данный элемент конечного поля a полным квадратом. В частности, χ (0) = 0, χ ( a ) = 1, если a = b 2 для некоторого ненулевого элемента конечного поля b , и χ ( a ) = −1, если a не является квадратом какого-либо элемента конечного поля. Например, в GF (7) ненулевые квадраты равны 1 = 1 2 = 6 2 , 4 = 2 2 = 5 2 и 2 = 3 2 = 4 2 . Следовательно, χ (0) = 0, χ (1) = χ (2) = χ (4) = 1 и χ (3) = χ (5) = χ (6) = −1.
Якобсталь матрица Q для GF ( Q ) является д × д матрица со строками и столбцами индексированных конечными элементами поля таким образом, что запись в строке а и столбец Ь является χ ( - б ). Например, в GF (7), если строки и столбцы матрицы Якобсталя индексируются элементами поля 0, 1, 2, 3, 4, 5, 6, то
Матрица Якобсталь обладает свойствами QQ Т = QI - J и QJ = JQ = 0 , где I является д × д единичная матрица , и J является д × д всего 1 матрица. Если q сравнимо с 1 (mod 4), то −1 - квадрат в GF ( q ), что означает, что Q - симметричная матрица . Если q сравнимо с 3 (mod 4), то −1 не является квадратом, а Q - кососимметричной матрицей . Когда q - простое число, Q - циркулянтная матрица . То есть каждая строка получается из строки выше циклической перестановкой.
Конструкция Пэли I
Если q конгруэнтно 3 (mod 4), то
- матрица Адамара размера q + 1. Здесь j - вектор-столбец длины q, состоящий из всех единиц, а I - единичная матрица ( q +1) × ( q +1). Матрица Н представляет собой перекос матрицы Адамара , а это значит , он удовлетворяет H + H T = 2 I .
Конструкция Палей II
Если q сравнимо с 1 (mod 4), то матрица, полученная заменой всех 0 элементов в
с матрицей
и все элементы ± 1 с матрицей
является матрицей Адамара размера 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) , полученного присоединением корня к неприводимым квадратичным . Различные неприводимые квадратики производят эквивалентные поля. Выбирая x 2 + x −1 и позволяя a быть корнем этого многочлена, девять элементов GF (9) могут быть записаны 0, 1, −1, a , a +1, a −1, - a , - a +1, - а −1. Ненулевые квадраты равны 1 = (± 1) 2 , - a +1 = (± a ) 2 , a −1 = (± ( a +1)) 2 и −1 = (± ( a −1) ) 2 . Матрица Якобсталя имеет вид
Это симметричная матрица, состоящая из девяти циркулянтных блоков 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-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. Произведение Кронекера двух матриц Адамара размеров m и n является матрицей Адамара размера mn . Формируя произведения Кронекера матриц из конструкции Пэли и матрицы 2 × 2,
Производятся матрицы Адамара всех разрешенных размеров до 100, кроме 92. В своей статье 1933 года Пэли говорит: «Кажется вероятным, что всякий раз, когда m делится на 4, можно построить ортогональную матрицу порядка m, составленную из ± 1, но общая теорема имеет все виды трудностей». Это, по-видимому, первое опубликованное утверждение гипотезы Адамара . Матрица размера 92 была в конечном итоге построена Баумертом, Голомбом и Холлом с использованием конструкции Уильямсона в сочетании с компьютерным поиском. В настоящее время показано, что матрицы Адамара существуют для всехдля m <668.
Смотрите также
Рекомендации
- Пейли, REAC (1933). «Об ортогональных матрицах». Журнал математики и физики . 12 : 311–320. DOI : 10.1002 / sapm1933121311 . Zbl 0007.10004 .
- Л. Д. Баумерт; С.В. Голомб ; М. Холл-младший (1962). «Открытие матрицы Адамара порядка 92» . Бык. Амер. Математика. Soc . 68 (3): 237–238. DOI : 10.1090 / S0002-9904-1962-10761-7 .
- FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . Северная Голландия. С. 47 , 56. ISBN 0-444-85193-3.