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) K. J. Horadam, Hadamard Matrices and Their Applications, Princeton University Press, 2006.

Data for Williamson-Goethals-Seidel construction of skew Hadamard matrices

Here we keep the data for this construction. Namely, it needs 4 circulant matrices with extra properties, as described in sage.combinat.matrices.hadamard_matrix.williamson_goethals_seidel_skew_hadamard_matrix() Matrices for $$n=36$$ and $$52$$ are given in [GS70s]. Matrices for $$n=92$$ are given in [Wall71].

INPUT:

• n – the order of the matrix
• existence – if true (default), only check that we can do the construction
• check – if true (default), check the result.

Return a size 324x324 Regular Symmetric Hadamard Matrix with Constant Diagonal.

We build the matrix $$M$$ for the case $$n=324$$, $$\epsilon=1$$ directly from JankoKharaghaniTonchevGraph and for the case $$\epsilon=-1$$ from the “twist” $$M'$$ of $$M$$, using Lemma 11 in [HX10]. Namely, it turns out that the matrix

$\begin{split}M'=\begin{pmatrix} M_{12} & M_{11}\\ M_{11}^\top & M_{21} \end{pmatrix}, \quad\text{where}\quad M=\begin{pmatrix} M_{11} & M_{12}\\ M_{21} & M_{22} \end{pmatrix},\end{split}$

and the $$M_{ij}$$ are 162x162-blocks, also RSHCD, its diagonal blocks having zero row sums, as needed by [loc.cit.]. Interestingly, the corresponding $$(324,152,70,72)$$-strongly regular graph has a vertex-transitive automorphism group of order 2592, twice the order of the (intransitive) automorphism group of the graph corresponding to $$M$$. Cf. [CP16].

INPUT:

• e – one of $$-1$$ or $$+1$$, equal to the value of $$\epsilon$$

REFERENCE:

 [CP16] (1, 2) N. Cohen, D. Pasechnik, Implementing Brouwer’s database of strongly regular graphs, Designs, Codes, and Cryptography, 2016 doi:10.1007/s10623-016-0264-x

Tries to construct a Hadamard matrix using a combination of Paley and Sylvester constructions.

INPUT:

• n (integer) – dimension of the matrix

• existence (boolean) – whether to build the matrix or merely query if a construction is available in Sage. When set to True, the function returns:

• True – meaning that Sage knows how to build the matrix
• Unknown – meaning that Sage does not know how to build the matrix, although the matrix may exist (see sage.misc.unknown).
• False – meaning that the matrix does not exist.
• check (boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.

EXAMPLES:

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 hadamard_matrix() returns a normalised Hadamard matrix (the entries in the first row and column are all +1)

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

INPUT:

• n – the matrix size
• normalize (boolean) – whether to normalize the result.

EXAMPLES:

We note that this method by default returns a normalised Hadamard matrix

[ 1  1  1  1]
[ 1 -1  1 -1]
[ 1 -1 -1  1]
[ 1  1 -1 -1]

Otherwise, it returns a skew Hadamard matrix $$H$$, i.e. $$H=S+I$$, with $$S=-S^ op$$

[ 1  1  1  1]
[-1  1  1 -1]
[-1 -1  1  1]
[-1  1 -1  1]
sage: S=M-identity_matrix(4); -S==S.T
True

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:

2985984
sage: 12^6
2985984

We note that the method returns a normalised Hadamard matrix

[ 1  1| 1  1| 1  1| 1  1| 1  1| 1  1]
[ 1 -1|-1  1|-1  1|-1  1|-1  1|-1  1]
[-----+-----+-----+-----+-----+-----]
[ 1 -1| 1 -1| 1  1|-1 -1|-1 -1| 1  1]
[ 1  1|-1 -1| 1 -1|-1  1|-1  1| 1 -1]
[-----+-----+-----+-----+-----+-----]
[ 1 -1| 1  1| 1 -1| 1  1|-1 -1|-1 -1]
[ 1  1| 1 -1|-1 -1| 1 -1|-1  1|-1  1]
[-----+-----+-----+-----+-----+-----]
[ 1 -1|-1 -1| 1  1| 1 -1| 1  1|-1 -1]
[ 1  1|-1  1| 1 -1|-1 -1| 1 -1|-1  1]
[-----+-----+-----+-----+-----+-----]
[ 1 -1|-1 -1|-1 -1| 1  1| 1 -1| 1  1]
[ 1  1|-1  1|-1  1| 1 -1|-1 -1| 1 -1]
[-----+-----+-----+-----+-----+-----]
[ 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:

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

Test if $$M$$ is a hadamard matrix.

INPUT:

• M – a matrix
• normalized (boolean) – whether to test if M is a normalized Hadamard matrix, i.e. has its first row/column filled with +1.
• skew (boolean) – whether to test if M is a skew Hadamard matrix, i.e. $$M=S+I$$ for $$-S=S^\top$$, and $$I$$ the identity matrix.
• verbose (boolean) – whether to be verbose when the matrix is not Hadamard.

EXAMPLES:

True
True
sage: h[0,0] = 2
The matrix does not only contain +1 and -1 entries, e.g. 2
False
sage: for i in range(12):
....:     h[i,2] = -h[i,2]
The matrix is not normalized
False

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:

True

Return a Regular Symmetric Hadamard Matrix with Constant Diagonal.

A Hadamard matrix is said to be regular if its rows all sum to the same value.

For $$\epsilon\in\{-1,+1\}$$, we say that $$M$$ is a $$(n,\epsilon)-RSHCD$$ if $$M$$ is a regular symmetric Hadamard matrix with constant diagonal $$\delta\in\{-1,+1\}$$ and row sums all equal to $$\delta \epsilon \sqrt(n)$$. For more information, see [HX10] or 10.5.1 in [BH12]. For the case $$n=324$$, see RSHCD_324() and [CP16].

INPUT:

• n (integer) – side of the matrix
• e – one of $$-1$$ or $$+1$$, equal to the value of $$\epsilon$$

EXAMPLES:

[ 1  1  1 -1]
[ 1  1 -1  1]
[ 1 -1  1  1]
[-1  1  1  1]
[ 1 -1 -1 -1]
[-1  1 -1 -1]
[-1 -1  1 -1]
[-1 -1 -1  1]

Other hardcoded values:

sage: for n,e in [(36,1),(36,-1),(100,1),(100,-1),(196, 1)]:  # long time
36 x 36 dense matrix over Integer Ring
36 x 36 dense matrix over Integer Ring
100 x 100 dense matrix over Integer Ring
100 x 100 dense matrix over Integer Ring
196 x 196 dense matrix over Integer Ring

sage: for n,e in [(324,1),(324,-1)]: # not tested - long time, tested in RSHCD_324
324 x 324 dense matrix over Integer Ring
324 x 324 dense matrix over Integer Ring

From two close prime powers:

64 x 64 dense matrix over Integer Ring (use the '.str()' method to see the entries)

From a prime power and a conference matrix:

676 x 676 dense matrix over Integer Ring (use the '.str()' method to see the entries)

Recursive construction:

144 x 144 dense matrix over Integer Ring (use the '.str()' method to see the entries)

REFERENCE:

 [BH12] (1, 2) A. Brouwer and W. Haemers, Spectra of graphs, Springer, 2012, http://homepages.cwi.nl/~aeb/math/ipm/ipm.pdf
 [HX10] (1, 2) W. Haemers and Q. Xiang, Strongly regular graphs with parameters $$(4m^4,2m^4+m^2,m^4+m^2,m^4+m^2)$$ exist for all $$m>1$$, European Journal of Combinatorics, Volume 31, Issue 6, August 2010, Pages 1553-1559, doi:10.1016/j.ejc.2009.07.009

Return a $$(n^2,1)$$-RSHCD when $$n-1$$ and $$n+1$$ are odd prime powers and $$n=0\pmod{4}$$.

The construction implemented here appears in Theorem 4.3 from [GS70].

Note that the authors of [SWW72] claim in Corollary 5.12 (page 342) to have proved the same result without the $$n=0\pmod{4}$$ restriction with a very similar construction. So far, however, I (Nathann Cohen) have not been able to make it work.

INPUT:

• n – an integer congruent to $$0\pmod{4}$$

EXAMPLES:

sage: rshcd_from_close_prime_powers(4)
[-1 -1  1 -1  1 -1 -1  1 -1  1 -1 -1  1 -1  1 -1]
[-1 -1  1  1 -1 -1 -1 -1 -1  1  1 -1 -1  1 -1  1]
[ 1  1 -1  1  1 -1 -1 -1 -1 -1  1 -1 -1 -1  1 -1]
[-1  1  1 -1  1  1 -1 -1 -1 -1 -1  1 -1 -1 -1  1]
[ 1 -1  1  1 -1  1  1 -1 -1 -1 -1 -1  1 -1 -1 -1]
[-1 -1 -1  1  1 -1  1  1 -1 -1 -1  1 -1  1 -1 -1]
[-1 -1 -1 -1  1  1 -1 -1  1 -1  1 -1  1  1 -1 -1]
[ 1 -1 -1 -1 -1  1 -1 -1 -1  1 -1  1 -1  1  1 -1]
[-1 -1 -1 -1 -1 -1  1 -1 -1 -1  1  1  1 -1  1  1]
[ 1  1 -1 -1 -1 -1 -1  1 -1 -1 -1 -1  1  1 -1  1]
[-1  1  1 -1 -1 -1  1 -1  1 -1 -1 -1 -1  1  1 -1]
[-1 -1 -1  1 -1  1 -1  1  1 -1 -1 -1 -1 -1  1  1]
[ 1 -1 -1 -1  1 -1  1 -1  1  1 -1 -1 -1 -1 -1  1]
[-1  1 -1 -1 -1  1  1  1 -1  1  1 -1 -1 -1 -1 -1]
[ 1 -1  1 -1 -1 -1 -1  1  1 -1  1  1 -1 -1 -1 -1]
[-1  1 -1  1 -1 -1 -1 -1  1  1 -1  1  1 -1 -1 -1]

REFERENCE:

 [SWW72] (1, 2, 3) A Street, W. Wallis, J. Wallis, Combinatorics: Room squares, sum-free sets, Hadamard matrices. Lecture notes in Mathematics 292 (1972).

Return a $$((n-1)^2,1)$$-RSHCD if $$n$$ is prime power, and symmetric $$(n-1)$$-conference matrix exists

The construction implemented here is Theorem 16 (and Corollary 17) from [WW72].

In [SWW72] this construction (Theorem 5.15 and Corollary 5.16) is reproduced with a typo. Note that [WW72] refers to [Sz69] for the construction, provided by szekeres_difference_set_pair(), of complementary difference sets, and the latter has a typo.

From a symmetric_conference_matrix(), we only need the Seidel adjacency matrix of the underlying strongly regular conference (i.e. Paley type) graph, which we construct directly.

INPUT:

• n – an integer

EXAMPLES:

A 36x36 example

sage: H = rshcd_from_prime_power_and_conference_matrix(7); H
36 x 36 dense matrix over Integer Ring (use the '.str()' method to see the entries)
sage: H==H.T and is_hadamard_matrix(H) and H.diagonal()==[1]*36 and list(sum(H))==[6]*36
True

Bigger examples, only provided by this construction

sage: H = rshcd_from_prime_power_and_conference_matrix(27)  # long time
sage: H == H.T and is_hadamard_matrix(H)                    # long time
True
sage: H.diagonal()==[1]*676 and list(sum(H))==[26]*676      # long time
True

In this example the conference matrix is not Paley, as 45 is not a prime power

sage: H = rshcd_from_prime_power_and_conference_matrix(47)  # not tested (long time)

REFERENCE:

 [WW72] (1, 2) J. Wallis and A.L. Whiteman, Some classes of Hadamard matrices with constant diagonal, Bull. Austral. Math. Soc. 7(1972), 233-249

Tries to construct a skew Hadamard matrix

A Hadamard matrix $$H$$ is called skew if $$H=S-I$$, for $$I$$ the identity matrix and $$-S=S^\top$$. Currently constructions from Section 14.1 of [Ha83] and few more exotic ones are implemented.

INPUT:

• n (integer) – dimension of the matrix

• existence (boolean) – whether to build the matrix or merely query if a construction is available in Sage. When set to True, the function returns:

• True – meaning that Sage knows how to build the matrix
• Unknown – meaning that Sage does not know how to build the matrix, but that the design may exist (see sage.misc.unknown).
• False – meaning that the matrix does not exist.
• skew_normalize (boolean) – whether to make the 1st row all-one, and adjust the 1st column accordingly. Set to True by default.

• check (boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.

EXAMPLES:

2985984
sage: 12^6
2985984
[1]
[ 1  1]
[-1  1]

REFERENCES:

 [Ha83] M. Hall, Combinatorial Theory, 2nd edition, Wiley, 1983

Tries to construct a symmetric conference matrix

A conference matrix is an $$n\times n$$ matrix $$C$$ with 0s on the main diagonal and 1s and -1s elsewhere, satisfying $$CC^\top=(n-1)I$$. If $$C=C^\top$$ then $$n \cong 2 \mod 4$$ and $$C$$ is Seidel adjacency matrix of a graph, whose descendent graphs are strongly regular graphs with parameters $$(n-1,(n-2)/2,(n-6)/4,(n-2)/4)$$, see Sec.10.4 of [BH12]. Thus we build $$C$$ from the Seidel adjacency matrix of the latter by adding row and column of 1s.

INPUT:

• n (integer) – dimension of the matrix
• check (boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.

EXAMPLES:

sage: C=symmetric_conference_matrix(10); C
[ 0  1  1  1  1  1  1  1  1  1]
[ 1  0 -1 -1  1 -1  1  1  1 -1]
[ 1 -1  0 -1  1  1 -1 -1  1  1]
[ 1 -1 -1  0 -1  1  1  1 -1  1]
[ 1  1  1 -1  0 -1 -1  1 -1  1]
[ 1 -1  1  1 -1  0 -1  1  1 -1]
[ 1  1 -1  1 -1 -1  0 -1  1  1]
[ 1  1 -1  1  1  1 -1  0 -1 -1]
[ 1  1  1 -1 -1  1  1 -1  0 -1]
[ 1 -1  1  1  1 -1  1 -1 -1  0]
sage: C^2==9*identity_matrix(10) and C==C.T
True

Construct Szekeres $$(2m+1,m,1)$$-cyclic difference family

Let $$4m+3$$ be a prime power. Theorem 3 in [Sz69] contains a construction of a pair of complementary difference sets $$A$$, $$B$$ in the subgroup $$G$$ of the quadratic residues in $$F_{4m+3}^*$$. Namely $$|A|=|B|=m$$, $$a\in A$$ whenever $$a-1\in G$$, $$b\in B$$ whenever $$b+1 \in G$$. See also Theorem 2.6 in [SWW72] (there the formula for $$B$$ is correct, as opposed to (4.2) in [Sz69], where the sign before $$1$$ is wrong.

In modern terminology, for $$m>1$$ the sets $$A$$ and $$B$$ form a difference family with parameters $$(2m+1,m,1)$$. I.e. each non-identity $$g \in G$$ can be expressed uniquely as $$xy^{-1}$$ for $$x,y \in A$$ or $$x,y \in B$$. Other, specific to this construction, properties of $$A$$ and $$B$$ are: for $$a$$ in $$A$$ one has $$a^{-1}$$ not in $$A$$, whereas for $$b$$ in $$B$$ one has $$b^{-1}$$ in $$B$$.

INPUT:

• m (integer) – dimension of the matrix
• check (default: True) – whether to check $$A$$ and $$B$$ for correctness

EXAMPLES:

sage: G,A,B=szekeres_difference_set_pair(6)
sage: G,A,B=szekeres_difference_set_pair(7)

REFERENCE:

 [Sz69] (1, 2, 3) G. Szekeres, Tournaments and Hadamard matrices, Enseignement Math. (2) 15(1969), 269-278

(1,-1)-incidence type I matrix of a difference set $$A$$ in $$G$$

Let $$A$$ be a difference set in a group $$G$$ of order $$n$$. Return $$n\times n$$ matrix $$M$$ with $$M_{ij}=1$$ if $$A_i A_j^{-1} \in A$$, and $$M_{ij}=-1$$ otherwise.

EXAMPLES:

sage: G,A,B=szekeres_difference_set_pair(2)
sage: typeI_matrix_difference_set(G,A)
[-1  1 -1 -1  1]
[-1 -1 -1  1  1]
[ 1  1 -1 -1 -1]
[ 1 -1  1 -1 -1]
[-1 -1  1  1 -1]

Williamson-Goethals-Seidel construction of a skew Hadamard matrix

Given $$n\times n$$ (anti)circulant matrices $$A$$, $$B$$, $$C$$, $$D$$ with 1,-1 entries, and satisfying $$A+A^\top = 2I$$, $$AA^\top + BB^\top + CC^\top + DD^\top = 4nI$$, one can construct a skew Hadamard matrix of order $$4n$$, cf. [GS70s].

INPUT:

• a – 1,-1 list specifying the 1st row of $$A$$
• b – 1,-1 list specifying the 1st row of $$B$$
• d – 1,-1 list specifying the 1st row of $$C$$
• c – 1,-1 list specifying the 1st row of $$D$$

EXAMPLES: