A Hadamard matrix is an \(n\times n\) matrix \(H\) whose entries are either \(+1\) or \(-1\) and whose rows are mutually orthogonal. For example, the matrix \(H_2\) defined by
is a Hadamard matrix. An \(n\times n\) matrix \(H\) whose entries are either \(+1\) or \(-1\) is a Hadamard matrix if and only if:
In general, the tensor product of an \(m\times m\) Hadamard matrix and an \(n\times n\) Hadamard matrix is an \((mn)\times (mn)\) matrix. In particular, if there is an \(n\times n\) Hadamard matrix then there is a \((2n)\times (2n)\) Hadamard matrix (since one may tensor with \(H_2\)). This particular case is sometimes called the Sylvester construction.
The Hadamard conjecture (possibly due to Paley) states that a Hadamard matrix of order \(n\) exists if and only if \(n= 1, 2\) or \(n\) is a multiple of \(4\).
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 \(p \cong 3 \mod{4}\) for a prime \(p\).
Todo
This construction holds more generally for prime powers \(q\) congruent to \(3 \mod{4}\). We should implement these but we first need to implement Quadratic character for \(GF(q)\).
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 \(p \cong 1 \mod{4}\) for a prime \(p\) (see [Hora]).
Todo
This construction holds more generally for prime powers \(q\) congruent to \(1 \mod{4}\). We should implement these but we first need to implement Quadratic character for \(GF(q)\).
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 \(hadamard_matrix()\) 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 \(p \cong 3 \mod{4}\) for a prime \(p\) (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 \(p \cong 1 \mod{4}\) for a prime \(p\) (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 \(H\) 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