Construcción Paley

En matemáticas , la construcción de Paley es un método para construir matrices de Hadamard utilizando cuerpos finitos . Esta 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, dependiendo de 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 elemento no cuadrado:

${\displaystyle \chi (a)={\begin{cases}0&{\text{si }}a=0\\1&{\text{si }}a=b^{2}{\text{ para algún }}b\in \mathrm {GF} (q)\\-1&{\text{si }}a{\text{ no es el cuadrado de ningún elemento en }}\mathrm {GF} (q).\end{cases}}}$

Por ejemplo, en GF(7) los cuadrados distintos de cero son 1 = 1 ² = 6 ² , 4 = 2 ² = 5 ² y 2 = 3 ² = 4 ² . 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 ) tales 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 del campo 0, 1, 2, 3, 4, 5, 6, entonces  

${\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}}.}$

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 con todos los elementos 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 antisimétrica . Cuando q es un número primo y las filas y columnas están indexadas por elementos de campo en el orden usual 0, 1, 2, …, Q es una matriz circulante . Es decir, cada fila se obtiene de la fila superior mediante permutación cíclica . 

Si q es congruente con 3 mod 4 entonces

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

es una matriz de Hadamard de tamaño q  +  1. Aquí j es el vector columna de 1 de longitud q 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

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

con la matriz

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

y todas las entradas ±1 con la matriz

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

es una matriz de Hadamard de tamaño 2( q  +  1). Es una matriz de Hadamard simétrica.

Aplicando la construcción de Paley I a la matriz de Jacobsthal para GF(7), se obtiene la matriz de Hadamard de 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}}.}$

Para un ejemplo de la construcción de Paley II cuando q es una potencia prima en lugar de un número primo, consideremos GF(9). Este es un cuerpo de extensión de GF(3) obtenido al adjuntar una raíz de un polinomio cuadrático irreducible . Diferentes polinomios cuadráticos irreducibles producen cuerpos equivalentes. Eligiendo x² + x − 1 y siendo a una raíz de este polinomio , los nueve elementos de GF(9) se pueden escribir como 0, 1, −1, ^a , a + 1 , a − 1 , −a, −a+ 1 , −a − 1. Los cuadrados no nulos son 1 = (±1) ^² , −a + 1 = (± a ) ^² , a − 1 = (±( a +1)) ^² y − 1 = (±( a − 1)) ^² . La matriz de Jacobsthal es

${\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}}.}$

Es una matriz simétrica que consta de nueve bloques circulantes de 3 × 3. La construcción de Paley II produce la matriz de 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--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---. 

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 de la construcción de Paley y la matriz de 2 × 2,

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

Se producen matrices de Hadamard de todos los tamaños permisibles 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 parece bastante difícil”. Esta parece ser la primera formulación publicada de la conjetura de Hadamard . Finalmente, Baumert, Golomb y Hall construyeron 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${\displaystyle m\,\equiv \,0\mod 4}$para m  <  668.

• Biplano Paley
• Gráfico de Paley

• Paley, REAC (1933). "Sobre matrices ortogonales". Journal of Mathematics and Physics . 12 ( 1– 4): 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" . Bull. Amer. Math. 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 correctores de errores . North-Holland. págs. 47 , 56. ISBN  0-444-85193-3.