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

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

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

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

${\displaystyle \chi (a)={\begin{cases}0&{\text{if }}a=0\\1&{\text{if }}a=b^{2}{\text{ для некоторого ненулевого }}b\in \mathrm {GF} (q)\\-1&{\text{if }}a{\text{ не является квадратом ни одного элемента из }}\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 для GF( q ) — это матрица q  ×  q со строками и столбцами, индексированными элементами GF( q ) такими, что запись в строке a и столбце b равна χ( a  −  b ). Например, в 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 ^T = qI  −  J и QJ = JQ = 0, где I — единичная матрица размера q  ×  q , а J — матрица размера q  ×  q all 1. Если q сравнимо с 1 mod 4, то −1 является квадратом в GF( q ), что подразумевает, что Q — симметричная матрица . Если q сравнимо с 3 mod 4, то −1 не является квадратом, а Q — кососимметричная матрица . Когда q — простое число, а строки и столбцы индексируются элементами поля в обычном порядке 0, 1, 2, …, Q является циркулянтной матрицей . То есть каждая строка получается из строки выше с помощью циклической перестановки .

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

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

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

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

${\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,

${\displaystyle {\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), полученное присоединением корня неприводимого квадратичного уравнения . Различные неприводимые квадратичные уравнения дают эквивалентные поля. Выбрав x2 + x −1 и позволив a быть корнем этого многочлена , девять элементов GF(9) можно записать как 0, 1, −1, ^a , a + 1, a −1, − a , − a +1, − a −1. Ненулевые квадраты — это 1 = (±1) ² , − a +1 = (± a ) ² , a −1 = (±( a +1)) ² и −1 = (±( a −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. Конструкция Пейли 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. Произведение Кронекера двух матриц Адамара размеров m и n является матрицей Адамара размера mn . Образуя произведения Кронекера матриц из конструкции Пэли и матрицы 2 × 2,

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

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

• биплан Пейли
• График Пейли

• Paley, REAC (1933). «Об ортогональных матрицах». Журнал математики и физики . 12 : 311–320. doi :10.1002/sapm1933121311. Zbl  0007.10004.
• LD Baumert; SW Golomb ; M. Hall Jr (1962). «Открытие матрицы Адамара порядка 92». Bull. Amer. Math. Soc . 68 (3): 237–238. doi : 10.1090/S0002-9904-1962-10761-7 .
• FJ MacWilliams ; NJA Sloane (1977). Теория кодов, исправляющих ошибки . North-Holland. стр. 47, 56. ISBN 0-444-85193-3.