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:
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:
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. |
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
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
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]
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]
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]
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]
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