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

\[\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:

[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

Finite combinatorial classes

Next topic

Restricted growth arrays

This Page