Hadamard matrices¶
A Hadamard matrix is an matrix
whose entries are either
or
and whose rows are mutually orthogonal. For example, the matrix
defined by
is a Hadamard matrix. An matrix
whose entries are either
or
is a Hadamard matrix if and only if:
or
, where
is the identity matrix.
In general, the tensor product of an Hadamard matrix and an
Hadamard matrix is an
matrix. In
particular, if there is an
Hadamard matrix then there is a
Hadamard matrix (since one may tensor with
).
This particular case is sometimes called the Sylvester construction.
The Hadamard conjecture (possibly due to Paley) states that a Hadamard
matrix of order exists if and only if
or
is a multiple
of
.
The module below implements the Paley constructions (see for example [Hora]) and the Sylvester construction. It also allows you to pull a Hadamard matrix from the database at [HadaSloa].
AUTHORS:
- David Joyner (2009-05-17): initial version
REFERENCES:
[HadaSloa] | N.J.A. Sloane’s Library of Hadamard Matrices, at http://neilsloane.com/hadamard/ |
[HadaWiki] | Hadamard matrices on Wikipedia, Wikipedia article Hadamard_matrix |
[Hora] | (1, 2, 3, 4) K. J. Horadam, Hadamard Matrices and Their Applications, Princeton University Press, 2006. |
-
sage.combinat.matrices.hadamard_matrix.
H1
(i, j, p)¶ Returns the i,j-th entry of the Paley matrix, type I case. The Paley type I case corresponds to the case
for a prime
.
Todo
This construction holds more generally for prime powers
congruent to
. We should implement these but we first need to implement Quadratic character for
.
EXAMPLES:
sage: sage.combinat.matrices.hadamard_matrix.H1(1,2,3) 1
-
sage.combinat.matrices.hadamard_matrix.
H2
(i, j, p)¶ Returns the i,j-th entry of the Paley matrix, type II case.
The Paley type II case corresponds to the case
for a prime
(see [Hora]).
Todo
This construction holds more generally for prime powers
congruent to
. We should implement these but we first need to implement Quadratic character for
.
EXAMPLES:
sage: sage.combinat.matrices.hadamard_matrix.H2(1,2,5) 1
-
sage.combinat.matrices.hadamard_matrix.
hadamard_matrix
(n)¶ Tries to construct a Hadamard matrix using a combination of Paley and Sylvester constructions.
EXAMPLES:
sage: hadamard_matrix(12).det() 2985984 sage: 12^6 2985984 sage: hadamard_matrix(1) [1] sage: hadamard_matrix(2) [ 1 1] [ 1 -1] sage: hadamard_matrix(8) [ 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] sage: hadamard_matrix(8).det() == 8^4 True
We note that the method
returns a normalised Hadamard matrix (the entries in the first row and column are all +1)
sage: hadamard_matrix(12) [ 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 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 1 -1 -1 -1] [ 1 1 -1 -1 1 -1| 1 -1 1 1 -1 -1]
-
sage.combinat.matrices.hadamard_matrix.
hadamard_matrix_paleyI
(n)¶ Implements the Paley type I construction.
The Paley type I case corresponds to the case
for a prime
(see [Hora]).
EXAMPLES:
We note that this method returns a normalised Hadamard matrix
sage: sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyI(4) [ 1 1 1 1] [ 1 -1 -1 1] [ 1 1 -1 -1] [ 1 -1 1 -1]
-
sage.combinat.matrices.hadamard_matrix.
hadamard_matrix_paleyII
(n)¶ Implements the Paley type II construction.
The Paley type II case corresponds to the case
for a prime
(see [Hora]).
EXAMPLES:
sage: sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyII(12).det() 2985984 sage: 12^6 2985984
We note that the method returns a normalised Hadamard matrix
sage: sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyII(12) [ 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 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 1 -1 -1 -1] [ 1 1 -1 -1 1 -1| 1 -1 1 1 -1 -1]
-
sage.combinat.matrices.hadamard_matrix.
hadamard_matrix_www
(url_file, comments=False)¶ Pulls file from Sloane’s database and returns the corresponding Hadamard matrix as a Sage matrix.
You must input a filename of the form “had.n.xxx.txt” as described on the webpage http://neilsloane.com/hadamard/, where “xxx” could be empty or a number of some characters.
If comments=True then the “Automorphism...” line of the had.n.xxx.txt file is printed if it exists. Otherwise nothing is done.
EXAMPLES:
sage: hadamard_matrix_www("had.4.txt") # optional - internet [ 1 1 1 1] [ 1 -1 1 -1] [ 1 1 -1 -1] [ 1 -1 -1 1] sage: hadamard_matrix_www("had.16.2.txt",comments=True) # optional - internet Automorphism group has order = 49152 = 2^14 * 3 [ 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] [ 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] [ 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] [ 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]
-
sage.combinat.matrices.hadamard_matrix.
normalise_hadamard
(H)¶ Return the normalised Hadamard matrix corresponding to
H
.The normalised Hadamard matrix corresponding to a Hadamard matrix
is a matrix whose every entry in the first row and column is +1.
EXAMPLES:
sage: H = sage.combinat.matrices.hadamard_matrix.normalise_hadamard(hadamard_matrix(4)) sage: H == hadamard_matrix(4) True