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
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:
\(|det(H)|=n^{n/2}\) or
\(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 [SloaHada].
AUTHORS:
David Joyner (2009-05-17): initial version
REFERENCES:
- sage.combinat.matrices.hadamard_matrix.GS_skew_hadamard_smallcases(n, existence=False, check=True)#
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].Additional data is obtained from skew supplementary difference sets contained in
sage.combinat.designs.difference_family.skew_supplementary_difference_set()
, using the construction described in [Djo1992].INPUT:
n
– the order of the matrixexistence
– if true (default), only check that we can do the constructioncheck
– if true (default), check the result.
- sage.combinat.matrices.hadamard_matrix.RSHCD_324(e)#
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 [HX2010]. 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. [CP2016].
INPUT:
e
– one of \(-1\) or \(+1\), equal to the value of \(\epsilon\)
REFERENCE:
- sage.combinat.matrices.hadamard_matrix.construction_four_symbol_delta_code_I(X, Y, Z, W)#
Construct 4-symbol \(\delta\) code of length \(2n+1\).
The 4-symbol \(\delta\) code is constructed from sequences \(X, Y, Z, W\) of length \(n+1\), \(n+1\), \(n\), \(n\) satisfying for all \(s > 0\):
\[N_X(s) + N_Y(s) + N_Z(s) + N_W(s) = 0\]where \(N_A(s)\) is the nonperiodic correlation function:
\[N_A(s) = \sum_{i=1}^{n-s}a_ia_{i+s}\]The construction (detailed in [Tur1974]) is as follows:
\[\begin{split}\begin{aligned} T_1 &= X;Z \\ T_2 &= X;-Z \\ T_3 &= Y;W \\ T_4 &= Y;-W \end{aligned}\end{split}\]INPUT:
X
– a list, representing the first sequence (length \(n+1\)).Y
– a list, representing the second sequence (length \(n+1\)).Z
– a list, representing the third sequence (length \(n\)).W
– a list, representing the fourth sequence (length \(n\)).
- OUTPUT:
A tuple containing the 4-symbol \(\delta\) code of length \(2n+1\).
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import construction_four_symbol_delta_code_I sage: construction_four_symbol_delta_code_I([1, 1], [1, -1], [1], [1]) ([1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1])
- sage.combinat.matrices.hadamard_matrix.construction_four_symbol_delta_code_II(X, Y, Z, W)#
Construct 4-symbol \(\delta\) code of length \(4n+3\).
The 4-symbol \(\delta\) code is constructed from sequences \(X, Y, Z, W\) of length \(n+1\), \(n+1\), \(n\), \(n\) satisfying for all \(s > 0\):
\[N_X(s) + N_Y(s) + N_Z(s) + N_W(s) = 0\]where \(N_A(s)\) is the nonperiodic correlation function:
\[N_A(s) = \sum_{i=1}^{n-s}a_ia_{i+s}\]The construction (detailed in [Tur1974]) is as follows (writing \(A/B\) to mean \(A\) alternated with \(B\)):
\[\begin{split}\begin{aligned} T_1 &= X/Z;Y/W;1 \\ T_2 &= X/Z;Y/-W;-1 \\ T_3 &= X/Z;-Y/-W;1 \\ T_4 &= X/Z;-Y/W;-1 \end{aligned}\end{split}\]INPUT:
X
– a list, representing the first sequence (length \(n+1\)).Y
– a list, representing the second sequence (length \(n+1\)).Z
– a list, representing the third sequence (length \(n\)).W
– a list, representing the fourth sequence (length \(n\)).
- OUTPUT:
A tuple containing the four 4-symbol \(\delta\) code of length \(4n+3\).
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import construction_four_symbol_delta_code_II sage: construction_four_symbol_delta_code_II([1, 1], [1, -1], [1], [1]) ([1, 1, 1, 1, 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.four_symbol_delta_code_smallcases(n, existence=False)#
Return the 4-symobl \(\delta\) code of length \(n\) if available.
The 4-symbol \(\delta\) codes are constructed using
construction_four_symbol_delta_code_I()
orconstruction_four_symbol_delta_code_II()
. The base sequences used are taken from [Tur1974].INPUT:
n
– integer, the length of the desired 4-symbol \(\delta\) code.existence
– boolean, if true only check if the sequences are available.
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import four_symbol_delta_code_smallcases sage: four_symbol_delta_code_smallcases(3) ([1, -1, 1], [1, -1, -1], [1, 1, 1], [1, 1, -1]) sage: four_symbol_delta_code_smallcases(3, existence=True) True
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix(n, existence=False, check=True)#
This function is available as hadamard_matrix(…) and matrix.hadamard(…).
Tries to construct a Hadamard matrix using the available methods.
INPUT:
n
(integer) – dimension of the matrixexistence
(boolean) – whether to build the matrix or merely query if a construction is available in Sage. When set toTrue
, the function returns:True
– meaning that Sage knows how to build the matrixUnknown
– meaning that Sage does not know how to build the matrix, although the matrix may exist (seesage.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 toTrue
by default.
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) # random [ 1 1 1 1 1 1 1 1] [ 1 -1 1 -1 1 -1 1 -1] [ 1 1 -1 -1 1 1 -1 -1] [ 1 -1 -1 1 1 -1 -1 1] [ 1 1 1 1 -1 -1 -1 -1] [ 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
hadamard_matrix()
returns a normalised Hadamard matrix (the entries in the first row and column are all +1)sage: hadamard_matrix(12) # random [ 1 1| 1 1| 1 1| 1 1| 1 1| 1 1] [ 1 -1|-1 1|-1 1|-1 1|-1 1|-1 1] [-----+-----+-----+-----+-----+-----] [ 1 -1| 1 -1| 1 1|-1 -1|-1 -1| 1 1] [ 1 1|-1 -1| 1 -1|-1 1|-1 1| 1 -1] [-----+-----+-----+-----+-----+-----] [ 1 -1| 1 1| 1 -1| 1 1|-1 -1|-1 -1] [ 1 1| 1 -1|-1 -1| 1 -1|-1 1|-1 1] [-----+-----+-----+-----+-----+-----] [ 1 -1|-1 -1| 1 1| 1 -1| 1 1|-1 -1] [ 1 1|-1 1| 1 -1|-1 -1| 1 -1|-1 1] [-----+-----+-----+-----+-----+-----] [ 1 -1|-1 -1|-1 -1| 1 1| 1 -1| 1 1] [ 1 1|-1 1|-1 1| 1 -1|-1 -1| 1 -1] [-----+-----+-----+-----+-----+-----] [ 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_156()#
Construct an Hadamard matrix of order 156.
The matrix is created using the construction detailed in [BH1965]. This uses four circulant matrices of size \(13\times 13\), which are composed into a \(156\times 156\) block matrix.
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix_cooper_wallis_construction(x1, x2, x3, x4, A, B, C, D, check=True)#
Create an Hadamard matrix using the contruction detailed in [CW1972].
Given four circulant matrices \(X_1\), X_2, X_3, X_4` of order \(n\) with entries (0, 1, -1) such that the entrywise product of two distinct matrices is always equal to \(0\) and that \(\sum_{i=1}^{4}X_iX_i^\top = nI_n\) holds, and four matrices \(A, B, C, D\) of order \(m\) with elements (1, -1) such that \(MN^\top = NM^\top\) for all distinct \(M\), \(N\) and \(AA^\top + BB^\top + CC^\top + DD^\top = 4mI_n\) holds, we construct an Hadamard matrix of order \(4nm\).
INPUT:
x1
– a list or vector, representing the first row of the circulant matrix \(X_1\).x2
– a list or vector, representing the first row of the circulant matrix \(X_2\).x3
– a list or vector, representing the first row of the circulant matrix \(X_3\).x4
– a list or vector, representing the first row of the circulant matrix \(X_4\).A
– the matrix described above.B
– the matrix described above.C
– the matrix described above.D
– the matrix described above.check
– a boolean, if true (default) check that the resulting matrix is Hadamard before returing it.
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import hadamard_matrix_cooper_wallis_construction sage: from sage.combinat.t_sequences import T_sequences_smallcases sage: seqs = T_sequences_smallcases(19) sage: hadamard_matrix_cooper_wallis_construction(seqs[0], seqs[1], seqs[2], seqs[3], matrix([1]), matrix([1]), matrix([1]), matrix([1])) 76 x 76 dense matrix over Integer Ring...
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix_cooper_wallis_smallcases(n, check=True, existence=False)#
Construct Hadamard matrices using the Cooper-Wallis construction for some small values of \(n\).
This function calls the function
hadamard_matrix_cooper_wallis_construction()
with the appropriate arguments. It constructs the matrices \(X_1\), \(X_2\), \(X_3\), \(X_4\) using either T-matrices or the T-sequences fromsage.combinat.t_sequences.T_sequences_smallcases()
. The matrices \(A\), \(B\), \(C\), \(D\) are taken fromwilliamson_type_quadruples_smallcases()
.Data for T-matrices of order 67 is taken from [Saw1985].
INPUT:
n
– integer, the order of the matrix to be constructed.check
– boolean: if True (default), check the the matrix is an Hadamard matrix before returning.existence
– boolean (default False): if True, only check if matrix exists.
OUTPUT:
If
existence
is false, returns the Hadamard matrix of order \(n\). It raises an error if no data is available to construct the matrix of the given order. Ifexistence
is true, returns a boolean representing whether the matrix can be constructed or not.EXAMPLES:
By default The function returns the Hadamard matrix
sage: from sage.combinat.matrices.hadamard_matrix import hadamard_matrix_cooper_wallis_smallcases sage: hadamard_matrix_cooper_wallis_smallcases(28) 28 x 28 dense matrix over Integer Ring...
If
existence
is set to True, the function returns a booleansage: hadamard_matrix_cooper_wallis_smallcases(20, existence=True) True
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyI(n, normalize=True)#
Implement the Paley type I construction.
The Paley type I case corresponds to the case \(p=n-1 \cong 3 \mod{4}\) for a prime power \(p\) (see [Hora]).
INPUT:
n
– the matrix sizenormalize
(boolean) – whether to normalize the result.
EXAMPLES:
We note that this method by default returns a normalised Hadamard matrix
sage: from sage.combinat.matrices.hadamard_matrix import hadamard_matrix_paleyI sage: hadamard_matrix_paleyI(4) [ 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^\top\)
sage: M = hadamard_matrix_paleyI(4, normalize=False); M [ 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
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix_paleyII(n)#
Implement the Paley type II construction.
The Paley type II case corresponds to the case \(p=n/2-1 \cong 1 \mod{4}\) for a prime power \(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_spence_construction(n, existence=False, check=True)#
Create an Hadamard matrix of order \(n\) using Spence construction.
This construction (detailed in [Spe1975]), uses supplementary difference sets implemented in
sage.combinat.designs.difference_family.supplementary_difference_set()
to create the desired matrix.INPUT:
n
– integer, the order of the matrix to be constructed.existence
– boolean (default False): if True, only check if matrix exists.check
– bolean: if True (default), check the the matrix is an Hadamard matrix before returning.
OUTPUT:
If
existence
is true, returns a boolean representing whether the Hadamard matrix can be constructed. Otherwise, returns the Hadamard matrix, or raises an error if it cannot be constructed.EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import hadamard_matrix_spence_construction sage: hadamard_matrix_spence_construction(36) 36 x 36 dense matrix over Integer Ring...
If
existence
isTrue
, the function returns a booleansage: hadamard_matrix_spence_construction(52, existence=True) True
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix_turyn_type(a, b, c, d, e1, e2, e3, e4, check=True)#
Construction of Turyn type Hadamard matrix.
Given \(n\times n\) circulant matrices \(A\), \(B\), \(C\), \(D\) with 1,-1 entries, satisfying \(AA^\top + BB^\top + CC^\top + DD^\top = 4nI\), and a set of Baumert-Hall units of order \(4t\), one can construct a Hadamard matrix of order \(4tn\) as detailed by Turyn in [Tur1974].
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\).e1
– Matrix representing the first Baumert-Hall unit.e2
– Matrix representing the second Baumert-Hall unit.e3
– Matrix representing the third Baumert-Hall unit.e4
– Matrix representing the fourth Baumert-Hall unit.check
– Whether to check that the output is an Hadamard matrix before returning it.
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import hadamard_matrix_turyn_type, _get_baumert_hall_units sage: A, B, C, D = _get_baumert_hall_units(28) sage: hadamard_matrix_turyn_type([1], [1], [1], [1], A, B, C, D) 28 x 28 dense matrix over Integer Ring...
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix_williamson_type(a, b, c, d, check=True)#
Construction of Williamson type Hadamard matrix.
Given \(n\times n\) circulant matrices \(A\), \(B\), \(C\), \(D\) with 1,-1 entries, and satisfying \(AA^\top + BB^\top + CC^\top + DD^\top = 4nI\), one can construct a Hadamard matrix of order \(4n\), cf. [Ha83].
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\).check
(boolean) – Whether to check that the output is an Hadamard matrix before returning it.
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import hadamard_matrix_williamson_type sage: a = [ 1, 1, 1] sage: b = [ 1, -1, -1] sage: c = [ 1, -1, -1] sage: d = [ 1, -1, -1] sage: M = hadamard_matrix_williamson_type(a,b,c,d,check=True)
- sage.combinat.matrices.hadamard_matrix.hadamard_matrix_www(url_file, comments=False)#
Pull file from Sloane’s database and return 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.is_hadamard_matrix(M, normalized=False, skew=False, verbose=False)#
Test if \(M\) is a Hadamard matrix.
INPUT:
M
– a matrixnormalized
(boolean) – whether to test ifM
is a normalized Hadamard matrix, i.e. has its first row/column filled with +1.skew
(boolean) – whether to test ifM
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:
sage: from sage.combinat.matrices.hadamard_matrix import is_hadamard_matrix sage: h = matrix.hadamard(12) sage: is_hadamard_matrix(h) True sage: from sage.combinat.matrices.hadamard_matrix import skew_hadamard_matrix sage: h = skew_hadamard_matrix(12) sage: is_hadamard_matrix(h, skew=True) True sage: h = matrix.hadamard(12) sage: h[0,0] = 2 sage: is_hadamard_matrix(h,verbose=True) The matrix does not only contain +1 and -1 entries, e.g. 2 False sage: h = matrix.hadamard(12) sage: for i in range(12): ....: h[i,2] = -h[i,2] sage: is_hadamard_matrix(h,verbose=True,normalized=True) The matrix is not normalized False
- 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: from sage.combinat.matrices.hadamard_matrix import normalise_hadamard sage: H = normalise_hadamard(hadamard_matrix(4)) sage: H == hadamard_matrix(4) True
- sage.combinat.matrices.hadamard_matrix.regular_symmetric_hadamard_matrix_with_constant_diagonal(n, e, existence=False)#
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 [HX2010] or 10.5.1 in [BH2012]. For the case \(n=324\), see
RSHCD_324()
and [CP2016].INPUT:
n
(integer) – side of the matrixe
– one of \(-1\) or \(+1\), equal to the value of \(\epsilon\)
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import regular_symmetric_hadamard_matrix_with_constant_diagonal sage: regular_symmetric_hadamard_matrix_with_constant_diagonal(4,1) [ 1 1 1 -1] [ 1 1 -1 1] [ 1 -1 1 1] [-1 1 1 1] sage: regular_symmetric_hadamard_matrix_with_constant_diagonal(4,-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 ....: print(repr(regular_symmetric_hadamard_matrix_with_constant_diagonal(n,e))) 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 ....: print(repr(regular_symmetric_hadamard_matrix_with_constant_diagonal(n,e))) 324 x 324 dense matrix over Integer Ring 324 x 324 dense matrix over Integer Ring
From two close prime powers:
sage: regular_symmetric_hadamard_matrix_with_constant_diagonal(64,-1) 64 x 64 dense matrix over Integer Ring (use the '.str()' method to see the entries)
From a prime power and a conference matrix:
sage: regular_symmetric_hadamard_matrix_with_constant_diagonal(676,1) # long time 676 x 676 dense matrix over Integer Ring (use the '.str()' method to see the entries)
Recursive construction:
sage: regular_symmetric_hadamard_matrix_with_constant_diagonal(144,-1) 144 x 144 dense matrix over Integer Ring (use the '.str()' method to see the entries)
REFERENCE:
- sage.combinat.matrices.hadamard_matrix.rshcd_from_close_prime_powers(n)#
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 [GS1970].
Note that the authors of [SWW1972] 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: from sage.combinat.matrices.hadamard_matrix import rshcd_from_close_prime_powers 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:
- sage.combinat.matrices.hadamard_matrix.rshcd_from_prime_power_and_conference_matrix(n)#
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 [WW1972].
In [SWW1972] this construction (Theorem 5.15 and Corollary 5.16) is reproduced with a typo. Note that [WW1972] refers to [Sz1969] 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: from sage.combinat.matrices.hadamard_matrix import rshcd_from_prime_power_and_conference_matrix sage: from sage.combinat.matrices.hadamard_matrix import is_hadamard_matrix 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:
- sage.combinat.matrices.hadamard_matrix.skew_hadamard_matrix(n, existence=False, skew_normalize=True, check=True)#
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 matrixexistence
(boolean) – whether to build the matrix or merely query if a construction is available in Sage. When set toTrue
, the function returns:True
– meaning that Sage knows how to build the matrixUnknown
– meaning that Sage does not know how to build the matrix, but that the design may exist (seesage.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 toTrue
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 toTrue
by default.
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import skew_hadamard_matrix sage: skew_hadamard_matrix(12).det() 2985984 sage: 12^6 2985984 sage: skew_hadamard_matrix(1) [1] sage: skew_hadamard_matrix(2) [ 1 1] [-1 1]
REFERENCES:
- sage.combinat.matrices.hadamard_matrix.symmetric_conference_matrix(n, check=True)#
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 [BH2012]. 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 matrixcheck
(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 toTrue
by default.
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import symmetric_conference_matrix 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
- sage.combinat.matrices.hadamard_matrix.szekeres_difference_set_pair(m, check=True)#
Construct Szekeres \((2m+1,m,1)\)-cyclic difference family
Let \(4m+3\) be a prime power. Theorem 3 in [Sz1969] 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 [SWW1972] (there the formula for \(B\) is correct, as opposed to (4.2) in [Sz1969], 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 matrixcheck
(default:True
) – whether to check \(A\) and \(B\) for correctness
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import szekeres_difference_set_pair sage: G,A,B=szekeres_difference_set_pair(6) sage: G,A,B=szekeres_difference_set_pair(7)
REFERENCE:
- sage.combinat.matrices.hadamard_matrix.turyn_type_hadamard_matrix_smallcases(n, existence=False, check=True)#
Construct an Hadamard matrix of order \(n\) from available 4-symbol \(\delta\) codes and Williamson quadruples.
The function looks for Baumert-Hall units and Williamson type matrices from
four_symbol_delta_code_smallcases()
andwilliamson_type_quadruples_smallcases()
and use them to construct an Hadamard matrix with the Turyn construction defined inhadamard_matrix_turyn_type()
.INPUT:
n
– integer, the order of the matrix to be constructed.existence
– boolean (default False): if True, only check if matrix exists.check
– bolean: if True (default), check the the matrix is an Hadamard matrix before returning.
EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import turyn_type_hadamard_matrix_smallcases sage: turyn_type_hadamard_matrix_smallcases(28, existence=True) True sage: turyn_type_hadamard_matrix_smallcases(28) 28 x 28 dense matrix over Integer Ring...
- sage.combinat.matrices.hadamard_matrix.typeI_matrix_difference_set(G, A)#
(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: from sage.combinat.matrices.hadamard_matrix import szekeres_difference_set_pair sage: from sage.combinat.matrices.hadamard_matrix import typeI_matrix_difference_set 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]
- sage.combinat.matrices.hadamard_matrix.williamson_goethals_seidel_skew_hadamard_matrix(a, b, c, d, check=True)#
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:
sage: from sage.combinat.matrices.hadamard_matrix import williamson_goethals_seidel_skew_hadamard_matrix as WGS sage: a = [ 1, 1, 1, -1, 1, -1, 1, -1, -1] sage: b = [ 1, -1, 1, 1, -1, -1, 1, 1, -1] sage: c = [-1, -1]+[1]*6+[-1] sage: d = [ 1, 1, 1, -1, 1, 1, -1, 1, 1] sage: M = WGS(a,b,c,d,check=True)
REFERENCES:
- sage.combinat.matrices.hadamard_matrix.williamson_hadamard_matrix_smallcases(n, existence=False, check=True)#
Construct Williamson type Hadamard matrices for some small values of n.
This function uses the data contained in
sage.combinat.matrices.hadamard_matrix.williamson_type_quadruples_smallcases()
to create Hadamard matrices of the Williamson type, using the construction fromsage.combinat.matrices.hadamard_matrix.hadamard_matrix_williamson_type()
.INPUT:
n
– the order of the matrix.existence
– if true, only check that we can do the construction (default false).check
– if true (default), check the result.
- sage.combinat.matrices.hadamard_matrix.williamson_type_quadruples_smallcases(n, existence=False)#
Quadruples of matrices that can be used to construct Williamson type Hadamard matrices.
This function contains for some values of n, four \(n\times n\) matrices used in the Williamson construction of Hadamard matrices. Namely, the function returns the first row of 4 \(n\times n\) circulant matrices with the properties described in
sage.combinat.matrices.hadamard_matrix.hadamard_matrix_williamson_type()
. The matrices for n=29 and n=43 are given in [Ha83].INPUT:
n
– the order of the matrices to be returnedexistence
– if true, only check that we have the quadruple (default false).
OUTPUT:
If
existence
is false, returns a tuple containing four vectors, each being the first line of one of the four matrices. It raises an error if no such matrices are available. Ifexistence
is true, returns a boolean representing whether the matrices are available or not.EXAMPLES:
sage: from sage.combinat.matrices.hadamard_matrix import williamson_type_quadruples_smallcases sage: williamson_type_quadruples_smallcases(29) ((1, 1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, -1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, 1), (1, -1, 1, -1, -1, -1, 1, 1, -1, -1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, -1, 1, -1), (1, 1, 1, 1, -1, 1, 1, -1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, 1, 1, 1), (1, 1, -1, -1, 1, -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: williamson_type_quadruples_smallcases(43, existence=True) True