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

$\begin{split}\left(\begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\right)\end{split}$

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:

1. $$|det(H)|=n^{n/2}$$ or
2. $$H*H^t = n\cdot I_n$$, where $$I_n$$ is the identity matrix.

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:

• David Joyner (2009-05-17): initial version

REFERENCES:

 [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
[1]
[ 1  1]
[ 1 -1]
[ 1  1  1  1  1  1  1  1]
[ 1 -1  1 -1  1 -1  1 -1]
[ 1  1 -1 -1  1  1 -1 -1]
[ 1 -1 -1  1  1 -1 -1  1]
[ 1  1  1  1 -1 -1 -1 -1]
[ 1 -1  1 -1 -1  1 -1  1]
[ 1  1 -1 -1 -1 -1  1  1]
[ 1 -1 -1  1 -1  1  1 -1]
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]
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))