Hadamard matrices

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

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

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:

[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 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
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 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
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 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]
sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyI(n)

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]
sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyII(n)

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

Previous topic

Dancing links C++ wrapper

Next topic

Latin Squares

This Page