En matemáticas , la construcción de Paley es un método para construir matrices de Hadamard utilizando cuerpos 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 cuerpo finito GF( q ) donde q es una potencia de un número primo impar . Existen dos versiones de la construcción según si q es congruente con 1 o 3 módulo 4.
Sea q una potencia de un primo impar. En el cuerpo finito GF( q ) el carácter cuadrático χ( a ) indica si el elemento a es cero, un cuadrado distinto de cero o un no cuadrado:
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 tanto, χ(0) = 0, χ(1) = χ(2) = χ(4) = 1, y χ(3) = χ(5) = χ(6) = −1.
La matriz de Jacobsthal Q para GF( q ) es la matriz q × q con filas y columnas indexadas por elementos de GF( q ) de manera que la entrada en la fila a y la columna b es χ( a − 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 módulo 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 módulo 4 entonces −1 no es un cuadrado, y Q es una matriz antisimétrica . Cuando q es un número primo y las filas y columnas están indexadas por elementos de campo en el orden habitual 0, 1, 2, …, Q es una matriz circulante . Es decir, cada fila se obtiene de la fila superior por permutación cíclica .
Si q es congruente con 3 mod 4 entonces
es una matriz de Hadamard de tamaño q + 1. Aquí j es el vector columna de longitud q compuesto únicamente por 1 e I es la matriz identidad ( q + 1) × ( q + 1). La matriz H es una matriz de Hadamard sesgada , lo que significa que satisface H + H T = 2 I .
Si q es congruente con 1 mod 4 entonces la matriz obtenida al reemplazar 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 de Hadamard simétrica.
Aplicando la Construcción I de Paley a la matriz de Jacobsthal para GF(7), se produce la matriz de Hadamard de 8 × 8,
Para 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 cuerpo de extensión de GF(3) obtenido al adjuntar una raíz de una ecuación cuadrática irreducible . Diferentes ecuaciones cuadráticas irreducibles producen cuerpos equivalentes. Eligiendo x 2 + x −1 y dejando que a sea una raíz de este polinomio , los nueve elementos de GF(9) pueden escribirse 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 Hadamard simétrica 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 ----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---.
El tamaño de una matriz de 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 de 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 por ±1, pero el teorema general tiene todas las apariencias de ser difícil”. Esta parece ser la primera declaración publicada de la conjetura de Hadamard . Baumert, Golomb y Hall construyeron finalmente una matriz de tamaño 92 , utilizando una construcción debida a Williamson combinada con una búsqueda por computadora. Actualmente, se ha demostrado que existen matrices de Hadamard para todos los valores de m < 668.
