by Warren D. Smith Aug 2006.
An nXn matrix H is "Hadamard" if all its entries are ±1 and HTH=HHT=nIn, i.e. all its rows are orthogonal. It is "skew-Hadamard" if, in addition, H+HT=2In. The simplest example is the 2x2 matrix
+- ++It is a very old and famous (but still unproven) conjecture that Hadamard, indeed skew Hadamard, matrices exist for every n divisible by 4. (As of August 2006: Skew Hadamard matrices are known to exist for for all n<188 with n divisible by 4; non-skew Hadamards are known to exist for for all n<668 with n divisible by 4.)
P=n-1 is prime in the cases n=4,8,12,24,32,44,48,60,68,72,80,84... Then the PxP matrix M with entries Mij=+1 if j-i is a square mod P (otherwise use -1), can be augmented with an all + top-row and all - (except for the diagonal entry) left-column to get a skew-Hadamard matrix. For example, take n=8=1+7 (and the squares mod 7 are 0,1,2,4) to get this 8x8 skew-Hadamard matrix (where - stands for -1 and + for +1):
H8 = ++++++++
-+++-+--
--+++-+-
---+++-+
-+--+++-
--+--+++
-+-+--++
-++-+--+
If H is an nXn skew Hadamard matrix while A is an nXn symmetric Hadamard matrix (i.e. AT=A), then here is a 2nX2n skew Hadamard matrix:
H A -A H.
All the skew-Hadamard H-constructions above are (if we discard the first row and column) (n-1)X(n-1) circulant anti-symmetric. Therefore, if each of their (n-1)-long rows is reverse-ordered, they then become (n-1)X(n-1) back-circulant (and symmetric, since back-circulant matrices are always symmetric). If we then border them with an all - row and an all - column, we get a symmetric Hadamard A. We can then use this H and A in the doubling construction. That yields sizes n=8,16,24,40,48,64,88,96.
For a specific example, use the H8 we gave above, and
A8 = ++++++++
+--+-+++
+-+-+++-
++-+++--
+-+++--+
++++--+-
+++--+-+
++--+-++
to get this 16x16 skew Hadamard:
++++++++ ++++++++ -+++-+-- +--+-+++ --+++-+- +-+-+++- ---+++-+ ++-+++-- -+--+++- +-+++--+ --+--+++ ++++--+- -+-+--++ +++--+-+ -++-+--+ ++--+-++ -------- ++++++++ -++-+--- -+++-+-- -+-+---+ --+++-+- --+---++ ---+++-+ -+---++- -+--+++- ----++-+ --+--+++ ---++-+- -+-+--++ --++-+-- -++-+--+
This section by Dr. Christos Koukouvinos [ckoukouv(AT)cc.uoa.gr] Nov 1999.
This list contains the so-called good matrices of order m, i.e. one circulant and three back circulant (1,-1) matrices A,B,C,D of order m where A is circulant and skew-type (i.e. A+AT=Im) while B,C,D are symmetric (i.e. B=BT) back-circulant and they all satisfy the matrix equation
AAT + BBT + CCT + DDT = 4m Im
Then using A,B,C,D, where A is circulant and B,C,D are backcirculant, in the following Williamson array, we can construct the skew Hadamard matrix H of order n=4m:
A B C D
H = -B A D -C
-C -D A B
-D C -B A
In the following list, - stands for -1 and n=4m. We only give the first rows of
A,B,C,D since the rest of them follow from cyclic shifting to the right
in the case of A and to the left in the cases of B,C,D.
m=1, 4m=4=12+12+12+12, one solution:
1
1
1
1
That leads to this 4x4 skew Hadamard:
++++ -++- --++ -+-+
m=3, 4m=12=32+12+12+12, one solution:
11-
1--
1--
111
That leads to this 12x12 skew Hadamard:
++-+--+--+++ -++--+--++++ +-+-+--+-+++ -++++-+++-++ ++--+++++++- +-++-+++++-+ -++---++-+-- ++-----++--+ +-+---+-+-+- ---+---++++- -----+++--++ ----+-+-++-+
m=5, 4m=20=32+32+12+12, one solution:
111--
1-11-
1----
1----
m=7, 4m=28=52+12+12+12, one solution:
1111---
1-1--1-
1--11--
1------
m=7, 4m=28=32+32+32+12, two solutions:
111-1--
111--11
11-11-1
1-1111-
1111---
11-11-1
11-11-1
1-1111-
m=9, 4m=36=52+32+12+12, one solution:
1111-1---
11-1--1-1
1---11---
111-11-11
m=11, 4m=44=52+32+32+12, three solutions:
11-1--11-1-
1111----111
1-111--111-
1---1--1---
11--1-1-11-
111--11--11
11-1-11-1-1
11--------1
11----1111-
111--11--11
1-1-1111-1-
1--1----1--
m=13, 4m=52=72+12+12+12, two solutions:
11-1---111-1-
1---111111---
11-1--11--1-1
1----1--1----
11--1-1-1-11-
1--111--111--
111-1----1-11
1-----11-----
m=13, 4m=52=52+52+12+12, four solutions:
11----1-1111-
11-11----11-1
1-1111--1111-
1-111-11-111-
11----1-1111-
11-1-1--1-1-1
111--1111--11
111-11--11-11
11111--11----
1-11--11--11-
1111-1--1-111
11-1-1111-1-1
11-----11111-
1--111--111--
111-1-11-1-11
1-111-11-111-
From now on we cease giving all solutions and only give one.
m=15, 4m=60=52+52+32+12, four solutions:
111111--11----- 1-11--1111--11- 1----1-11-1---- 1-1---1--1---1-
m=17, 4m=68=72+32+32+12, two solutions:
11--11-1-1-1--11- 11--1--------1--1 111----1--1----11 11---1-1--1-1---1
m=19, 4m=76=72+52+12+12, five solutions:
1-1-----11--11111-1 11-11111----11111-1 1-1----11--11----1- 1--1-1-11--11-1-1--
m=21, 4m=84=92+12+12+12, four solutions:
11--1111111-------11- 111--1111-11-1111--11 1--11-1-1-11-1-1-11-- 1---111-1-11-1-111---
m=23, 4m=92=92+32+12+12, six solutions:
111-1-------1111111-1-- 11----1--1----1--1----1 11-1--11---11---11--1-1 1--11-1-1-1111-1-1-11--
m=25, 4m=100=92+32+32+12, three solutions:
11-----1-1---111-1-11111- 11-1111-1-11--11-1-1111-1 1---1--1111----1111--1--- 1--1-111--1----1--111-1--
Koukouvinos indeed has a larger list giving at least one solution for each odd m≤35, and every solution for each odd m≤31; and in [S.Georgiou, C.Koukouvinos, S.Stylianou: On good matrices, skew Hadamard matrices and optimal designs, Comput. Statist. Data Anal. 41,1 (2002) 171-184] that was extended to give every solution with m≤39. Also for m=37 and m=43 see [D.Z.Dokovic: Skew Hadamard Matrices of orders 4x37 and 4x43, J. Combinatorial Theory A 61,2 (1992) 319-321].
The only size below 100 not covered by the above constructions is 56. For that, the doubling construction would work if we had a symmetric 28x28 Hadamard to use as input, and here is one (from N.J.A.Sloane)
++++++++++++++-+++++++++++++ +++-++----++-++-+-++----++-+ ++++-++----++-++-+-++----++- +-+++-++----+++-+-+-++----++ ++-+++-++----+++-+-+-++----+ +++-+++-++----+++-+-+-++---- +-++-+++-++---+-++-+-+-++--- +--++-+++-++--+--++-+-+-++-- +---++-+++-++-+---++-+-+-++- +----++-+++-+++----++-+-+-++ ++----++-+++-+++----++-+-+-+ +++----++-+++-+++----++-+-+- +-++----++-++++-++----++-+-+ ++-++----++-++++-++----++-+- -+++++++++++++-------------- +-+-++----++-+---+--++++--+- ++-+-++----++-----+--++++--+ +-+-+-++----++-+---+--++++-- ++-+-+-++----+--+---+--++++- +++-+-+-++-------+---+--++++ +-++-+-+-++----+--+---+--+++ +--++-+-+-++---++--+---+--++ +---++-+-+-++--+++--+---+--+ +----++-+-+-++-++++--+---+-- ++----++-+-+-+--++++--+---+- +++----++-+-+----++++--+---+ +-++----++-+-+-+--++++--+--- ++-++----++-+---+--++++--+--
We have now constructed a skew Hadamard nXn matrix for every n divisible by 4 with n≤100. The number of equivalence classes of 4mX4m skew Hadamard matrices is exactly known for m=1-7: it is 1, 1, 1, 2, 2, 16, 54. [Edward Spence: Classification of Hadamard matrices of order 24 and 28, Discrete Math. 140, 1-3 (1995) 185-243]. Indeed, Spence just emailed me a file containing all of them.
More known info is surveyed in
J.Seberry & M.Yamada:
Hadamard matrices, sequences, and block designs, pp. 431-560 in
Contemporary Design Theory, a collection of surveys
(J.H.Dinitz & D.R.Stinson eds.), Wiley 1992, and
S.Georgiou, C.Koukouvinos, J.Seberry:
Hadamard matrices, orthogonal designs and construction algorithms,
pp. 133-205 in
DESIGNS 2002: Further computational and constructive design theory,
Kluwer 2003.