Построение Палея

Построение Палея — это метод построения матриц Адамара с помощью конечного поля. Построение описал в 1933 году английский математик Реймонд Палей.

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

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

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

Матрица Якобсталя Q для G F ( q ) {displaystyle GF(q)} является q × q {displaystyle q{ imes }q} матрицей со строками и столбцами, индексированными элементами конечного поля, такой, что элемент в строке a и столбце b равен χ ( a − b ) {displaystyle chi (a-b)} . Например, в GF(7), если строки и столбцы матрицы Якобсталя индексированы элементами поля 0, 1, 2, 3, 4, 5, 6, то

Q = [ 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 ] . {displaystyle Q={egin{bmatrix}0&-1&-1&1&-1&1&11&0&-1&-1&1&-1&11&1&0&-1&-1&1&-1-1&1&1&0&-1&-1&11&-1&1&1&0&-1&-1-1&1&-1&1&1&0&-1-1&-1&1&-1&1&1&0end{bmatrix}}.}

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

Построение Палея I

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

H = E + [ 0 j T − j Q ] {displaystyle H=E+{egin{bmatrix}0&j^{T}-j&Qend{bmatrix}}}

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

Построение Палея II

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

[ 0 j T j Q ] {displaystyle {egin{bmatrix}0&j^{T}j&Qend{bmatrix}}}

на матрицу

[ 1 − 1 − 1 − 1 ] {displaystyle {egin{bmatrix}1&-1-1&-1end{bmatrix}}} ,

а всех элементов ± 1 {displaystyle {pm }1} на матрицу

± [ 1 1 1 − 1 ] {displaystyle pm {egin{bmatrix}1&11&-1end{bmatrix}}} ,

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

Примеры

Если применить построение Палея I к матрице Якобсталя для GF(7), получим 8 × 8 {displaystyle 8{ imes }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 {displaystyle x^{2}+x-1} и корень a этого многочлена, девять элементов GF(9) могут быть записаны в виде 0 , 1 , − 1 , a , a + 1 , a − 1 , − a , − a + 1 , − a − 1 {displaystyle 0,1,-1,a,a+1,a-1,-a,-a+1,-a-1} . Ненулевыми квадратами будут 1 = ( ± 1 ) 2 , − a + 1 = ( ± a ) 2 , a − 1 = ( ± ( a + 1 ) ) 2 {displaystyle 1=({pm }1)^{2},-a+1=({pm }a)^{2},a-1=(pm (a+1))^{2}} и − 1 = ( ± ( a − 1 ) ) 2 {displaystyle -1=(pm (a-1))^{2}} . Матрица Якобсталя равна

Q = [ 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 ] . {displaystyle Q={egin{bmatrix}0&1&1&-1&-1&1&-1&1&-11&0&1&1&-1&-1&-1&-1&11&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&-11&-1&-1&1&1&0&-1&1&-1-1&-1&1&-1&1&-1&0&1&11&-1&-1&-1&-1&1&1&0&1-1&1&-1&1&-1&-1&1&1&0end{bmatrix}}.}

Это симметричная матрица состоящая из 3 × 3 {displaystyle 3 imes 3} циркулярных блоков. Построение Палея II даёт симметричную 20 × 20 {displaystyle 20 imes 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 {displaystyle 2 imes 2} матрицы,

H 2 = [ 1 1 1 − 1 ] , {displaystyle H_{2}={egin{bmatrix}1&11&-1end{bmatrix}},}

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