Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Paley construction
Résumé
In mathematics, the Paley construction is a method for constructing Hadamard matrices using finite fields. The construction was described in 1933 by the English mathematician Raymond Paley.
The Paley construction uses quadratic residues in a finite field GF(q) where q is a power of an odd prime number. There are two versions of the construction depending on whether q is congruent to 1 or 3 (mod 4).
Let q be a power of an odd prime. In the finite field GF(q) the quadratic character χ(a) indicates whether the element a is zero, a non-zero perfect square, or a non-square:
For example, in GF(7) the non-zero squares are 1 = 12 = 62, 4 = 22 = 52, and 2 = 32 = 42. Hence χ(0) = 0, χ(1) = χ(2) = χ(4) = 1, and χ(3) = χ(5) = χ(6) = −1.
The Jacobsthal matrix Q for GF(q) is the q×q matrix with rows and columns indexed by finite field elements such that the entry in row a and column b is χ(a − b). For example, in GF(7), if the rows and columns of the Jacobsthal matrix are indexed by the field elements 0, 1, 2, 3, 4, 5, 6, then
The Jacobsthal matrix has the properties Q QT = q I − J and Q J = J Q = 0 where I is the q×q identity matrix and J is the q×q all 1 matrix. If q is congruent to 1 (mod 4) then −1 is a square in GF(q)
which implies that Q is a symmetric matrix. If q is congruent to 3 (mod 4) then −1 is not a square, and Q is a
skew-symmetric matrix. When q is a prime number and rows and columns are indexed by field elements in the usual 0, 1, 2, ... order, Q is a circulant matrix. That is, each row is obtained from the row above by cyclic permutation.
If q is congruent to 3 (mod 4) then
is a Hadamard matrix of size q + 1. Here j is the all-1 column vector of length q and I is the (q+1)×(q+1) identity matrix. The matrix H is a skew Hadamard matrix, which means it satisfies H+HT = 2I.
If q is congruent to 1 (mod 4) then the matrix obtained by replacing all 0 entries in
with the matrix
and all entries ±1 with the matrix
is a Hadamard matrix of size 2(q + 1). It is a symmetric Hadamard matrix.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.