# Constructions of nXn skew-Hadamard matrices for n=4,8,12,...,96,100

## Circulant constructions of nXn skew-Hadamard matrices for n=4,8,12,20,24,32,44,48,60,68,72,80,84

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 = ++++++++
-+++-+--
--+++-+-
---+++-+
-+--+++-
--+--+++
-+-+--++
-++-+--+
```

## Doubling

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
```

```++++
-++-
--++
-+-+
```

m=3, 4m=12=32+12+12+12, one solution:

```      11-
1--
1--
111
```

```++-+--+--+++
-++--+--++++
+-+-+--+-+++
-++++-+++-++
++--+++++++-
+-++-+++++-+
-++---++-+--
++-----++--+
+-+---+-+-+-
---+---++++-
-----+++--++
----+-+-++-+
```

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

## Filling the missing spots

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

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.