En matemáticas , la construcción de Paley es un método para construir matrices de Hadamard utilizando campos finitos . La construcción fue descrita en 1933 por el matemático inglés Raymond Paley .
La construcción de Paley utiliza 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 3 (mod 4).
Carácter cuadrático y matriz de Jacobsthal
El carácter cuadrático χ ( a ) indica si el elemento de campo finito dado a es un cuadrado perfecto. Específicamente, χ (0) = 0, χ ( a ) = 1 si a = b 2 para algún elemento de campo finito b distinto de cero , y χ ( a ) = −1 si a no es el cuadrado de ningún elemento de campo finito. Por ejemplo, en GF (7) los cuadrados distintos de cero son 1 = 1 2 = 6 2 , 4 = 2 2 = 5 2 y 2 = 3 2 = 4 2 . Por lo tanto, χ (0) = 0, χ (1) = χ (2) = χ (4) = 1 y χ (3) = χ (5) = χ (6) = −1.
El Jacobsthal matriz Q para GF ( q ) es la q × q matriz con filas y columnas indexadas por elementos finitos de campo tales que la entrada en la fila una y la columna B es χ ( un - b ). Por ejemplo, en GF (7), si las filas y columnas de la matriz de Jacobsthal están indexadas por los elementos de campo 0, 1, 2, 3, 4, 5, 6, entonces
La matriz de Jacobsthal tiene las propiedades QQ T = qI - J y QJ = JQ = 0 donde I es la matriz identidad q × q y J es la matriz q × q todo 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 de simetría oblicua . Cuando q es un número primo, Q es una matriz circulante . Es decir, cada fila se obtiene de la fila anterior mediante permutación cíclica.
Paley construcción I
Si q es congruente con 3 (mod 4) entonces
es una matriz de Hadamard de tamaño q + 1. Aquí j es el vector de columna todo-1 de longitud q e I es la matriz de identidad ( q +1) × ( q +1). La matriz H es una matriz de sesgo Hadamard , lo que significa que satisface H + H T = 2 I .
Construcción Paley II
Si q es congruente con 1 (mod 4), entonces la matriz obtenida reemplazando todas las entradas 0 en
con la matriz
y todas las entradas ± 1 con la matriz
es una matriz de Hadamard de tamaño 2 ( q + 1). Es una matriz simétrica de Hadamard.
Ejemplos de
Aplicando la construcción de Paley I a la matriz de Jacobsthal para GF (7), se produce la matriz de Hadamard de 8 × 8,
11111111-1--1-11-11--1-1-111--1---111--1-1-111----1-111---- 1-111.
Para obtener un ejemplo de la construcción de Paley II cuando q es una potencia prima en lugar de un número primo, considere GF (9). Este es un campo de extensión de GF (3) obtenido al unir una raíz de una cuadrática irreducible . Diferentes cuadráticas irreducibles producen campos equivalentes. Al elegir x 2 + x −1 y dejar que a sea una raíz de este polinomio, los nueve elementos de GF (9) se pueden escribir 0, 1, −1, a , a +1, a −1, - a , - a +1, - a −1. Los cuadrados distintos de cero son 1 = (± 1) 2 , - a +1 = (± a ) 2 , a −1 = (± ( a +1)) 2 y −1 = (± ( a −1) ) 2 . La matriz de Jacobsthal es
Es una matriz simétrica que consta de nueve bloques circulantes de 3 × 3. Paley Construction II produce la matriz simétrica de Hadamard de 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 ---- 11111-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 ---.
La conjetura de Hadamard
El tamaño de una matriz Hadamard debe ser 1, 2, o un múltiplo de 4. El producto de Kronecker de dos matrices de Hadamard de tamaños m y n es una matriz de Hadamard de tamaño mn . Al formar productos de Kronecker de matrices a partir de la construcción de Paley y la matriz 2 × 2,
Se producen matrices Hadamard de todos los tamaños permitidos hasta 100 excepto 92. En su artículo de 1933, Paley dice: "Parece probable que, siempre que m sea divisible por 4, sea posible construir una matriz ortogonal de orden m compuesta de ± 1, pero el teorema general tiene toda apariencia de dificultad". Esta parece ser la primera declaración publicada de la conjetura de Hadamard . Una matriz de tamaño 92 fue finalmente construida por Baumert, Golomb y Hall , usando una construcción de Williamson combinada con una búsqueda por computadora. Actualmente, se ha demostrado que las matrices de Hadamard existen para todospara m <668.
Ver también
Referencias
- Paley, REAC (1933). "Sobre matrices ortogonales". Revista de Matemáticas y Física . 12 : 311-320. doi : 10.1002 / sapm1933121311 . Zbl 0007.10004 .
- LD Baumert; SW Golomb ; M. Hall Jr. (1962). "Descubrimiento de una matriz de Hadamard de orden 92" . Toro. Amer. Matemáticas. Soc . 68 (3): 237–238. doi : 10.1090 / S0002-9904-1962-10761-7 .
- FJ MacWilliams ; NJA Sloane (1977). La teoría de los códigos de corrección de errores . Holanda Septentrional. págs. 47 , 56. ISBN 0-444-85193-3.