Skew-Hadamard matrices of orders 188 and 388 exist
SKEW-HADAMARD MATRICES OF ORDERS 188 AND
388 EXIST
DRAGOMIR Ž. D– OKOVIĆ
Abstract. We construct several difference families on cyclic groups
of orders 47 and 97, and use them to construct skew-Hadamard
matrices of orders 188 and 388. Such difference families and ma-
trices are constructed here for the first time. The matrices are
constructed by using the Goethals–Seidel array.
2000 Mathematics Subject Classification 05B20, 05B30
1. Introduction
Recall that a Hadamard matrix A of orderm is a {±1}-matrix of size
m×m such that AAT = mIm, where T denotes the transpose and Im
the identity matrix. A skew-Hadamard matrix is a Hadamard matrix
A such that A − Im is a skew-symmetric matrix. We refer the reader
to [1] for the survey of known results about skew-Hadamard matrices.
The construction of skew-Hadamard matrices is lagging considerably
behind that for arbitrary Hadamard matrices. Our previous four notes,
written more than 13 years ago, were motivated by the desire to im-
prove this situation. We constructed skew-Hadamard matrices of order
m = 4n for the following 24 odd integers n:
[2]: 37, 43;
[3]: 67, 113, 127, 157, 163, 181, 241;
[4]: 39, 49, 65, 93, 121, 129, 133, 217, 219, 267;
[6]: 81, 103, 151, 169, 463.
At the time of publication, such matrices of these orders were not
known to exist. Due to the manifold increase in computing power
since that time, one can now make further progress.
In [6], we listed 45 odd integers n < 300 for which no skew-Hadamard
matrix of order 4n was known at that time. (In the first edition of [1],
Table 24.31 was incomplete.) The smallest of these n’s was 47. The
next one, 59, has been removed recently by Fletcher, Koukouvinos and
The author was supported by an NSERC Discovery Grant.
http://arxiv.org/abs/0704.0640v2
2 D.Ž. D– OKOVIĆ
Seberry [7]. In this note we shall remove the integers 47 and 97 from the
mentioned list by constructing examples of skew-Hadamard matrices
of orders 4 · 47 = 188 and 4 · 97 = 388. (We have constructed a bunch
of examples but we have saved and will present only a few of them.)
Consequently, the revised list now consists of the 42 integers:
69, 89, 101, 107, 109, 119, 145, 149, 153, 167, 177, 179, 191, 193,
201, 205, 209, 213, 223, 225, 229, 233, 235, 239, 245, 247, 249, 251,
253, 257, 259, 261, 265, 269, 275, 277, 283, 285, 287, 289, 295, 299.
We construct our examples of skew-Hadamard matrices of orders
188 and 388 by constructing first suitable supplementary difference
sets, and then we use these sets to build four circulant blocks, which
one should plug into the Goethals–Seidel array. The procedure used to
find these supplementary difference sets is not new. I have used it in
several papers during the last 15 years. It is described in my note [5].
2. The case n = 47
We denote the additive group of integers modulo n by Zn. In this
section we set n = 47. In the literature on Hadamard matrices it is
customary to refer to difference families (DF) as supplementary differ-
ence sets (SDS) and to employ more elaborate and more informative
notation by listing the order v of the underlying abelian group, the
number of sets in the family as well as their cardinals, and also the
parameter λ.
We have constructed four suitable difference families in Zn. The first
two are the following.
SKEW-HADAMARD MATRICES 3
Proposition 2.1. Define six subsets of Z47:
X1 = {2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 17, 18, 19, 20, 21, 22, 25, 27, 30,
31, 33, 35, 37, 38, 39, 40, 42, 43, 44},
X2 = {1, 3, 6, 7, 8, 11, 13, 14, 15, 19, 20, 21, 24, 27, 30, 33, 39, 41, 43,
44, 45, 46},
X3 = {3, 6, 8, 10, 11, 12, 14, 20, 21, 23, 24, 25, 26, 27, 30, 31, 32, 34, 35,
41, 42, 45},
Y1 = {1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 23, 24, 25, 27,
28, 29, 30, 31, 35, 38, 41, 43, 44, 46},
Y2 = {3, 6, 7, 8, 10, 11, 12, 16, 22, 25, 26, 31, 32, 33, 34, 37, 39, 41, 42,
43, 44, 46},
Y3 = {3, 7, 12, 13, 15, 16, 18, 20, 21, 23, 25, 26, 27, 28, 32, 35, 38, 39, 42,
44, 45, 46}.
The triples {X1, X2, X3} and {Y1, Y2, Y3} are difference families, i.e.,
they are 3 − (47; 30, 22, 22; 39) supplementary difference sets in Z47.
The two families are not equivalent.
Proof. Use the computer to verify the claims. Note that the cardinals
nk = |Xk| = |Yk| are indeed n1 = 30 and n2 = n3 = 22. The parameter
λ is 39, i.e., each nonzero integer in Zn occurs 39 times in the list of
differences created from the sets Xk and also from the Yk.
The second claim can be verified in several ways. We used the fol-
lowing ad hoc method. We compare the list of differences generated
by the sets X1 and Y1. Each nonzero integer i ∈ Zn occurs in one of
these lists say µi times. The µi’s take only three values: 18, 19 or 20.
But the number of µi’s equal to 18, 19 and 20 is 12, 26 and 8 for X1
and 14, 22 and 10 for Y1. Hence X1 and Y1 are not equivalent under
translations and automorphisms of the additive group Zn. �
For any subset X ⊆ Zn let
aX = (a0, a1, . . . , an−1)
be the {±1}-row vector such that ai = −1 iff i ∈ X . We denote by AX
the n× n circulant matrix having aX as its first row.
Let X0 ⊆ Zn be the Paley difference set (the set of nonzero squares
in the finite field Zn). Recall that X0 is of skew type, i.e., for nonzero
i ∈ Zn we have i ∈ X0 iff −i /∈ X0. Its cardinal is n0 = |X0| = 23.
For simplicity, write Ak instead of AXk for k = 0, 1, 2, 3. We can now
plug our matrices Ak into the Goethals–Seidel template to construct a
4 D.Ž. D– OKOVIĆ
skew-Hadamard matrix of order 188:
A0 A1R A2R A3R
−A1R A0 −A
−A2R A
R A0 −A
−A3R −A
As usual, R denotes the matrix having ones on the back-diagonal and
all other entries zero.
Clearly, we can use the second difference family to construct another
skew-Hadamard matrix of order 188. Both solutions have the same
associated decomposition of 4n as sum of four squares:
4n = 188 = 132 + 32 + 32 + 12
(n− 2nk)
The remaining two difference families have different parameters from
the first two.
Proposition 2.2. Define six subsets of Z47:
P1 = {0, 2, 4, 5, 9, 10, 12, 16, 17, 19, 21, 22, 23, 25, 27, 28, 35, 36, 37,
43, 46},
P2 = {0, 1, 2, 6, 8, 9, 11, 15, 16, 19, 25, 32, 33, 35, 36, 37, 38, 40, 44},
P3 = {1, 2, 3, 4, 5, 6, 7, 10, 11, 16, 18, 22, 24, 28, 31, 35, 38, 40, 43},
Q1 = {4, 5, 6, 8, 11, 12, 15, 20, 21, 23, 25, 26, 28, 29, 30, 31, 32, 36,
39, 41, 43},
Q2 = {1, 2, 5, 7, 13, 14, 21, 22, 24, 26, 31, 32, 35, 36, 37, 39, 40, 42, 46},
Q3 = {1, 2, 3, 4, 5, 9, 12, 18, 20, 21, 24, 25, 32, 34, 38, 39, 43, 44, 46}.
The triples {P1, P2, P3} and {Q1, Q2, Q3} are difference families, i.e.,
they are 3 − (47; 21, 19, 19; 24) supplementary difference sets in Z47.
These two families are not equivalent to each other or the ones above.
Just as the first two families, {P1, P2, P3} and {Q1, Q2, Q3} can be
used to construct two more skew-Hadamard matrices of order 188. The
associated decomposition into sum of four squares is now different:
188 = 92 + 92 + 52 + 12.
3. The case n = 97
For the remainder of this note we set n = 97. Let G be the multi-
plicative group of the nonzero elements of Zn, a cyclic group of order
n − 1 = 96, and let H = 〈35〉 = {1, 35, 61} be its subgroup of order
SKEW-HADAMARD MATRICES 5
3. We use the same enumeration of the 32 cosets αi, 0 ≤ i ≤ 31, of H
in G as in our computer program. Thus we impose the condition that
α2i+1 = −1 · α2i for 0 ≤ i ≤ 15. For even indices we have
α0 = H, α2 = 2H, α4 = 3H, α6 = 4H, α8 = 5H,
α10 = 6H, α12 = 7H, α14 = 9H, α16 = 10H, α18 = 12H,
α20 = 13H, α22 = 15H, α24 = 18H, α26 = 20H, α28 = 23H,
α30 = 26H.
Next define four index sets:
J0 = {1, 2, 4, 6, 9, 11, 13, 14, 17, 18, 21, 23, 25, 27, 29, 30},
J1 = {1, 2, 6, 7, 8, 9, 10, 11, 12, 13, 23, 27, 29},
J2 = {0, 1, 2, 5, 6, 12, 13, 15, 16, 20, 24, 25, 26, 29, 30, 31},
J3 = {0, 2, 3, 4, 7, 8, 9, 11, 12, 13, 15, 16, 17, 18, 23, 28, 29}
and introduce the following four subsets of Zn:
αi, k = 0, 1, 2, 3.
Their cardinals nk = |Uk| = 3|Jk| are:
n0 = n2 = 48, n1 = 39, n3 = 51
and we set
λ = n0 + n1 + n2 + n3 − n = 89.
Observe that U0 is of skew type, i.e., we have
U0 ∩ (−U0) = ∅, U0 ∪ (−U0) = Zn \ {0}.
Proposition 3.1. The four subsets U0, U1, U2, U3 ⊂ Zn form a dif-
ference family, i.e., they are 4 − (97; 48, 39, 48, 51; 89) supplementary
difference sets in Z97.
Proof. For r ∈ {1, 2, . . . , 96} let λk(r) denote the number of solutions
of the congruence i − j ≡ r (mod 97) with {i, j} ⊆ Uk. It is easy to
verify (by using a computer) that
λ1(r) + λ2(r) + λ3(r) + λ4(r) = λ
is valid for all such r. Hence the sets U1, U2, U3, U4 form a difference
family in Zn. �
Let Ak now denote the n × n circulant matrices AYk . The SDS-
property implies that the {±1}-matrices A0, . . . , A3 satisfy the identity
= 4nIn.
6 D.Ž. D– OKOVIĆ
One can now plug the matrices Ak into the Goethals–Seidel template
to obtain a Hadamard matrix A of order 4n = 388. Since U1 is of skew
type, A is also skew-Hadamard.
Our second example, B, is constructed in the same way by using the
index sets:
K0 = {0, 3, 4, 7, 9, 11, 12, 14, 17, 19, 20, 22, 24, 27, 28, 30},
K1 = {4, 7, 8, 10, 12, 13, 14, 15, 17, 18, 20, 26, 27},
K2 = {0, 1, 2, 3, 6, 7, 8, 11, 12, 14, 20, 23, 24, 25, 28, 31},
K3 = {1, 2, 4, 7, 8, 9, 10, 12, 13, 19, 21, 23, 24, 25, 26, 27, 31},
with the corresponding subsets of Zn:
αi, k = 0, 1, 2, 3,
with V0 of skew type.
Proposition 3.2. The four subsets V0, V1, V2, V3 ⊂ Zn form a dif-
ference family, i.e., they are 4 − (97; 48, 39, 48, 51; 89) supplementary
difference sets in Z97.
The two SDS’s that we used to construct A and B are not equivalent.
For instance, the sets U1 and V1 are not equivalent under translations
and group automorphisms of Zn.
Since the two SDS’s have the same parameters, they share the same
decomposition of 4n into sum of four squares:
4n = 388 = 192 + 52 + 12 + 12
(n− 2nk)
References
[1] C.J. Colbourn and J.H. Dinitz, Handbook of Combinatorial Designs, 2nd Edi-
tion, CRC Press, New York, 2006.
[2] D.Ž.D– oković, Skew Hadamard matrices of order 4×37 and 4×43, J. Combinat.
Theory, Series A, 61 (1992), 319–321.
[3] , Construction of some new Hadamard matrices, Bull. Austral. Math.
Soc. 45 (1992), 327–332.
[4] , Ten new orders for Hadamard matrices of skew type, Univ. Beograd,
Publ. Elektrotehn. Fak. Ser. Mat. 3 (1992), 47–59.
[5] , Good matrices of orders 33, 35 and 127 exist, J. Comb. Math. Comb.
Comp. 14 (1993), 145–152.
[6] , Five new orders for Hadamard matrices of skew type, Australasian J.
Comb. 10 (1994), 259–264.
SKEW-HADAMARD MATRICES 7
[7] R.J. Fletcher, C. Koukouvinos and J. Seberry, New skew-Hadamard matrices
of order 4 · 59 and new D-optimal designs of order 2 · 59, Discrete Math. 286
(2004), 251–253.
Department of Pure Mathematics, University of Waterloo, Water-
loo, Ontario, N2L 3G1, Canada
E-mail address : djokovic@uwaterloo.ca
	1. Introduction
	2. The case n=47
	3. The case n=97
	References
