La construccion de paley

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de marzo de 2021; la verificación requiere 1 edición .

La construcción de Paley es un método para construir matrices de Hadamard usando un campo finito . La construcción fue descrita en 1933 por el matemático inglés Raymond Paley .

La construcción de Paley usa residuos cuadráticos en un campo finito GF ( q ), donde q es una potencia de un número primo impar . Hay dos versiones de la construcción, dependiendo de si q es congruente con 1 o con 3 módulo 4.

El carácter cuadrado y la matriz de Jacobstal

El carácter cuadrado indica si el elemento a del campo finito es un cuadrado perfecto . En particular, si para algún elemento distinto de cero del campo finito b , y si a no es el cuadrado de ningún elemento del campo finito. Por ejemplo, en GF (7) , y son cuadrados distintos de cero . Por lo tanto, y . $\chi(a)$ ${\ estilo de visualización \ chi (0) = 0, \ chi (a) = 1}$ ${\ estilo de visualización a = b ^ {2}}$ ${\ estilo de visualización \ chi (a) = -1}$ ${\ estilo de visualización 1 = 1 ^ {2} = 6 ^ {2}}$ ${\ estilo de visualización 4 = 2 ^ {2} = 5 ^ {2}}$ ${\ estilo de visualización 2 = 3 ^ {2} = 4 ^ {2}}$ ${\ estilo de visualización \ chi (0) = 0, \ chi (1) = \ chi (2) = \ chi (4) = 1}$ ${\ estilo de visualización \ chi (3) = \ chi (5) = \ chi (6) = -1}$

La matriz Q de Jacobstal es una matriz con filas y columnas indexadas por elementos de un campo finito, tal que el elemento en la fila ay la columna b es . Por ejemplo, en GF (7), si las filas y columnas de la matriz de Jacobstal están indexadas por elementos de campo 0, 1, 2, 3, 4, 5, 6, entonces $FG(q)$ $q{\veces}q$ ${\ estilo de visualización \ chi (ab)}$

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{bmatriz}}.

La matriz de Jacobstal tiene las propiedades y , donde E es la matriz identidad y J es igual a la matriz en la que todos los elementos son iguales a -1. Si q es congruente con 1 (mod 4), entonces −1 es un cuadrado en GF ( q ), lo que implica que Q es una matriz simétrica . Si q es congruente con 3 (mod 4), entonces −1 no es un cuadrado y Q es una matriz asimétrica . Si q es primo, Q es un circulante . Es decir, cada fila se obtiene de la fila anterior mediante una permutación cíclica. $QQ^{T}=qE-J$ $QJ=JQ=0$ $q{\veces}q$ $q{\veces}q$

Construcción de Paley I

Si q es comparable a 3 (mod 4), entonces

H=E+{\begin{bmatriz}0&j^{T}\\-j&Q\end{bmatriz}}

es una matriz de Hadamard de tamaño . Aquí j es un vector columna de longitud q que consta de -1, y E es la matriz identidad. La matriz H es una matriz sesgada de Hadamard , lo que significa que satisface la igualdad . ${\ estilo de visualización q+1}$ ${\ estilo de visualización (q + 1) \ veces (q + 1)}$ $H+H^{T}=2E$

Construcción de Paley II

Si q es comparable a 1 (mod 4), entonces la matriz obtenida reemplazando todos los 0 en

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

a la matriz

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

y todos los elementos a la matriz ${\ estilo de visualización {\ p. m.} 1}$

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

es una matriz de Hadamard de tamaño . Esta es una matriz de Hadamard simétrica. ${\ estilo de visualización 2 (q + 1)}$

Ejemplos

Si aplicamos la construcción de Paley I a la matriz de Jacobstal para GF (7), obtenemos la matriz de Hadamard, ${\ estilo de visualización 8 {\ veces} 8}$

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

Como ejemplo de una construcción de Paley II donde q es una potencia de un primo en lugar de un número primo, considere GF (9). Esta es una extensión del campo GF (3), obtenido al sumar la raíz de un polinomio cuadrado irreducible . Varios polinomios cuadrados irreducibles dan campos equivalentes. Si además elegimos la raíz a de este polinomio, los nueve elementos de GF (9) se pueden escribir como . Y serán cuadrados distintos de cero . La matriz de Jacobstal es ${\ estilo de visualización x^{2}+x-1}$ $0,1,-1,a,a+1,a-1,-a,-a+1,-a-1$ $1=({\pm }1)^{2},-a+1=({\pm }a)^{2},a-1=(\pm (a+1))^{2 }$ ${\ estilo de visualización -1 = (\ pm (a-1)) ^ {2}}$

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{matrizb}}.

Esta es una matriz simétrica que consta de bloques circulares. La construcción de Paley II da una matriz Hadamard simétrica, $3 veces 3$ ${\ estilo de visualización 20 \ veces 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---.

Conjetura de Hadamard

El tamaño de la matriz de Hadamard debe ser igual a 1, 2 o un múltiplo de 4. El producto de Kronecker de dos matrices de Hadamard de tamaño m y n será una matriz de Hadamard de tamaño mn . Al formar el producto de Kronecker de matrices a partir de la construcción de Paley y la matriz, $2\veces 2$

H_{2}={\begin{bmatriz}1&1\\1&-1\end{bmatriz)),

uno obtiene matrices de Hadamard de cualquier tamaño admisible hasta 100 excepto 92. En su artículo de 1933, Paley dice: “Es bastante probable que en el caso donde m es divisible por 4, uno puede construir una matriz ortogonal de orden m , que consta de , pero el teorema general tiene una serie de dificultades". Esta parece ser la primera publicación de una declaración de la conjetura de Hadamard . La matriz de 92 tamaños fue finalmente construida por Baumert, Golomb y Hall utilizando la construcción de Williamson combinada con la búsqueda por computadora. Actualmente se muestra que existen matrices de Hadamard para todos para . ${\ estilo de visualización {\ p. m.} 1}$ $m\,\equiv\,0\mod 4$ ${\ estilo de visualización m <668}$

Véase también

Notas

Literatura

Paley REAC Sobre matrices ortogonales // Revista de Matemáticas y Física. - 1933. - T. 12 . — S. 311–320 .
Baumert LD, Golomb SW , Hall M. Jr. Descubrimiento de una matriz de Hadamard de orden 92 // Bol. amer Matemáticas. Soc.. - 1962. - T. 68 , núm. 3 . — S. 237–238 . -doi : 10.1090 / S0002-9904-1962-10761-7 .
MacWilliams FJ, Sloane NJA La teoría de los códigos de corrección de errores . - 1977. - S. 47 , 56. - ISBN 0-444-85193-3 .