SKEW-HADAMARD MATRICES © Nickolay Balonin and Jennifer Seberry, 1.09.2014 Skew-Hadamard matrix catalogue and on-line algorithms

Definition. The Hadamard matrix H is n xn ±1-matrix H'H=n I. For p =n–1 is prime, in the cases n =4, 8, 12, 24, 32, 44, 48, 60, 68, 72, 80, 84 ..., there is one border one circulant construction with Legendre symbols. There are also two- and four-circulant constructions.

For even order 16 we use a two circulant version: H is a skew Hadamard matrix while A is a symmetric Hadamard matrix (i.e. A^{T} =A). We use some non symmetry blocks of a fractal construction, based on an idea of chains, especially for orders n =2^{t} , t is integer, 2, 4, 8, 32, 64, 128, 512, .. presented below.

TWO BORDER TWO CIRCULANT SKEW-HADAMARD MATRICES

// BY ORTHOGONAL EULER SEQUENCES
if (tick==0) { n=3*6; w=100;
m=2*w; v=n/2; z=(v-1)/2; e=zero(z); Q=one(m); F=true; }
// Генерируем массив из 1000 последовательностей
R=signm(rands(matrix(w,(v-1)/2))); P=fliplr(R);
M=square(R,P,R,minp(P));
M=colline(Q,M); //mesh(M);
s=absm(sums(M)); K1=0; K2=0;
// Перебираем пары (a,b) с учетом сумм элементов
for (i=0;i<m;i++) if (F) if (s[i]==1) { a=M[i]; K1++;
for (ii=1;ii<z;ii++) { ss=2;
for (jj=0;jj<v;jj++) { d=jj-ii; if (d<0) d+=v;
if (a[d]>0) { if (a[jj]>0) { ss++; }else{ ss--; }}else{
if (a[jj]>0) { ss--; }else{ ss++; }}} e[ii]=ss; }
for (j=i;j<m;j++) if (F) if (s[j]==1) { b=M[j]; K2++;
// if (0) { m=maxabslsm(circ(a),circ(b),-2); F=m>0; }else{
// тест на ортогональность с прерыванием по флагу
for (ii=1;ii<z;ii++) if (F) { ss=e[ii];
for (jj=0;jj<v;jj++) { d=jj-ii; if (d<0) d+=v;
if (b[d]>0) { if (b[jj]>0) { ss++; }else{ ss--; }}else{
if (b[jj]>0) { ss--; }else{ ss++; }}} F=ss==0; } F=!F; }}
puts("n="+n+" tick="+tick+" pairs="+K1+"/"+K2);
if (F) { restart(0);}else{
putm("a=["+a+"];"); putm("b=["+b+"];");
A=circ(a); B=circ(b); I=eye(B); {{B=B-I}}
H=twocircul(B,A,-1);
H=border(H,0,-1,1); H[0]=minp(H[0]);
H=border(H,0,1,-1);
plots(H,"X"); {{I=H'*H}} putm(I);
// sound("5th.wav");
}

FOUR CIRCULANT SKEW-HADAMARD MATRICES

The skew-Hadamard matrix H can be calculated by Williamson-type A, B, C, D matrices, called good matrices, where AA^{T} +BB^{T} +CC^{T} +DD^{T} =4m I, A is skew-circulant and B, C, D are symmetric circulant matrices that are placed in the Seberry-Williamson array as back-circulant matrices, symmetric about the back diagonal. Skew Hadamard matrices are known to exist for for all n <188 with n divisible by 4 (look Warren D. Smith, August 2006), below placed matrices found by Christos Koukouvinos (mostly).

{{H="H44SK.xml"}} // 4, 12, 20, 28, .. , 92, 100!
mesh(H); // puts(H); // {{I=H'*H}} putm(I);

Matrices H_{4} and H_{12} Matrices H_{20} and H_{28} Matrices H_{36} and H_{44} Matrices H_{52} and H_{60} Matrices H_{68} and H_{76} Matrices H_{84} and H_{92} Matrices H_{100} ! THE FIRST COMPUTER RESEARHES: 1961

The pleasure to find new matrix: Hadamard 92 moment 1961

From left to right, Solomon Golomb (Assistant Chief of the Communications Systems Research Section), Leonard Baumert (a postdoc student at Caltech), and Marshall Hall, Jr. (Caltech mathematics professor) hold a framed representation of the matrix. In 1961, mathematicians from NASA’s Jet Propulsion Laboratory and Caltech worked together to construct a Hadamard Matrix containing 92 rows and columns, with combinations of positive and negative signs. In a Hadamard Matrix, if you placed all the potential rows or columns next to each other, half of the adjacent cells would be the same sign, and half would be the opposite sign. This mathematical problem had been studied since about 1893, but the solution to the 92 by 92 matrix was unproven until 1961 because it required extensive computation. The team used JPL’s IBM 7090 computer, programmed by Baumert, to perform the computations.

A=circul([1,1,-1,-1,-1,1,-1,-1,-1,1,-1,1,1,-1,1,-1,-1,-1,1,-1,-1,-1,1]);
B=circul([1,-1,1,1,-1,1,1,-1,-1,1,1,1,1,1,1,-1,-1,1,1,-1,1,1,-1]);
C=circul([1,1,1,-1,-1,-1,1,1,-1,1,-1,1,1,-1,1,-1,1,1,-1,-1,-1,1,1]);
D=circul([1,1,1,-1,1,1,1,-1,1,-1,-1,-1,-1,-1,-1,1,-1,1,1,1,-1,1,1]);
{{A=-A; B=-B; C=-C; D=-D}} // the photo version
// Hadamard matrix of Williamson-type
W1=colline(A,B,C,D);
W2=colline(minp(B),A,minp(D),C);
W3=colline(minp(C),D,A,minp(B));
W4=colline(minp(D),minp(C),B,A);
H=tr(colline(tr(W1),tr(W2),tr(W3),tr(W4)));
mesh(H); {{X=H'*H}} puts(X);

THE FIRST COMPUTER RESEARCHES: 1971

There is a skew-Hadamard matrix of order 92 (Jennifer Seberry, 1971). Previously the smallest order for which a skew-Hadamard matrix was not known was 92. The existence of any Hadamard matrix of order 92 was unknown until 1962 (see photo with Williamson matrix, order 92).

A=circul([1,-1,-1,-1,-1,-1,-1,-1,1,1,-1,1,-1,1,-1,-1,1,1,1,1,1,1,1]);
B=circul([1,1,-1,-1,1,-1,-1,1,1,1,1,-1,-1,1,1,1,1,-1,-1,1,-1,-1,1]);
C=circul([1,1,-1,-1,-1,1,-1,1,-1,1,-1,1,1,-1,1,-1,1,-1,1,-1,-1,-1,1]);
D=circul([1,-1,-1,-1,-1,1,-1,-1,1,-1,-1,1,1,-1,-1,1,-1,-1,1,-1,-1,-1,-1]);
B=flip(B); C=flip(C); D=flip(D);
// skew-Hadamard matrix of Williamson-type
W1=colline(A,B,C,D);
W2=colline(minp(B),A,D,minp(C));
W3=colline(minp(C),minp(D),A,B);
W4=colline(minp(D),C,minp(B),A);
H=tr(colline(tr(W1),tr(W2),tr(W3),tr(W4)));
mesh(H);
// this way gives also C92
// I=eye(H); {{C=H-I}} {{X=C'*C}} puts(X);

ON LINE ALGORITHM. A SAMPLE OF H_{44}

A=circul([1,1,1,-1,1,-1,1,-1,1,-1,-1]);
B=circul([1,-1,-1,-1,-1,-1,-1,-1,-1,1,1]);
C=circul([1,1,-1,-1,1,1,-1,-1,1,1,1]);
D=circul([-1,1,1,-1,1,1,-1,1,1,-1,1]);
B=flip(B); C=flip(C); D=flip(D);
// skew-Hadamard matrix of Williamson-type
W1=colline(A,B,C,D);
W2=colline(minp(B),A,D,minp(C));
W3=colline(minp(C),minp(D),A,B);
W4=colline(minp(D),C,minp(B),A);
H=tr(colline(tr(W1),tr(W2),tr(W3),tr(W4)));
mesh(H);
// this way gives also C44
// I=eye(H); {{C=H-I}} {{X=C'*C}} puts(X);

GET MORE COLOURS 44x44

Jennifer Seberry Wallis, A skew-Hadamard matrix of order 92, Bulletin of the Australian Mathematical Society, 5, (1971), 203-204. 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:
++++++++ ++++++++
-+++-+-- +--+-+++
--+++-+- +-+-+++-
---+++-+ ++-+++--
-+--+++- +-+++--+
--+--+++ ++++--+-
-+-+--++ +++--+-+
-++-+--+ ++--+-++
-------- ++++++++
-++-+--- -+++-+--
-+-+---+ --+++-+-
--+---++ ---+++-+
-+---++- -+--+++-
----++-+ --+--+++
---++-+- -+-+--++
--++-+-- -++-+--+
Yamada-Williamson constructions of nXn skew-Hadamard matrices for n=4,12,20,28,36,44,52,60,68,76,84,92,100
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].
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.

CATALOGUE | SKEW PROPUS-HADAMARD MATRICES