FOUR CIRCULANT HADAMARD MATRICES © Nickolay Balonin and Jennifer Seberry, 1.05.2014 Hadamard matrix catalogue and on-line algorithms

There is Ryser's conjecture (see [1], page 134): is the inexistence of matrices of order n > 4 that are circulant and Hadamard matrices simultaneously. Now we are interesting in symmetric four- or fifth-circulant Hadamard matrices of rich structure (circulant and back-circulant blocks).

if (tick==0) {
// 16, 24, 32, 40, 48, 56, 64
// s=5; n=pow(2,s); n=n+0*4;
s=3; n=32; v=n; hf=1.01; hf2=4*hf;
hmin=100; sn=sqrt(n);
F4=true; // FOUR CIRCULANT FORM
F2=true; // TWO CIRCULANT FORM
FB=false; // BORDER FLAG
FR=true; // REVERS FLAG
FS1=true; // SYMMETRY
FS2=true; // TWO SYMMETRY
if (F4) { n2=n; n=n/2; }
if (F2) v=n/2; if (FB) v=v-1;
if (FR) { if (FB) { v2=(v-1)/2; }else{ v2=v/2-1; } }
}
// INSTANCE 1: CHOOSE PRETENDENT H
// MATRIX ORDER 20, 32, 40, 68, 100, ...
H=initmatrix(n,1000,4); // plots(H);
if (F4) n=n2;
// INSTANCE 2: DETERMINANT OPTIMISATION
H=norms(H); m=maxabs(H);
u=line(n); p=0.5; q=50; q2=5; // iterations
while(q>1) { q=q-1; p=0.995*p+0.005;
// SORT COLUMS
ix=maxabsix(H); u=sort(u,ix); H=sort(H,ix);
H=sat(H,m*p); H=orth(H); m=maxabs(H); h=m*sn;
if (h<hf) { q=0; tick=-tick; }else{
if (h<hmin) hmin=h; if (q>q2) if (h>hf2) q=0; }
}
puts('n='+n+' s='+s+' h/hmin='+format(h,1000)+'/'+format(hmin,1000)+' max='+minx+' tick='+abs(tick));
if (tick>=0) {
// HYSTOGRAM AND RESTART
// G=sort(absm(colline(H))); mesh(G);
restart(0);
}else{
// RESULT
H=resort(H,u); H=divp(H,m); if (h<hf) H=roundm(H);
if (F4) n=n/2; // analysis();
{{I=H'*H}} putm(I); putm(H);
plots(H,"XR");
sound("../../music/5th.wav");
}
function getAB() {
function resp(y,x,q) {
var i,k,ks,s,p,z,a; s=rows(y);
{{a=x; a=(a+1)/2; y=(y+1)/2;}}
for (k=s;k<q;k++) { z=0; ks=k-s;
for (i=0;i<s;i++) z+=y[i]*a[ks+i]; a[k]=z%2;}
{{a=2*a-1}}
return a;
}
if (FR) {
y1=randseq(s); x1=randseq(s); a1=resp(y1,x1,v2);
if (FS1) { b1=flip(a1); }else{
b1=resp(randseq(s),randseq(s),v2); }
// a1=randseq(v2); // b1=randseq(v2); //
if (!FB) {
a=[1].concat(a1).concat(randseq(1)).concat(b1);
}else{ // a=[1].concat(a1).concat(minp(b1));
a=[1].concat(a1).concat(b1); }
}else{
y1=randseq(s); x1=randseq(s); a=resp(y1,x1,v); // a[0]=0;
}
// a=ab2a(a);
A=circul(a);
if (F2) {
if (FR) {
if (0) { a2=a1; }else{
y2=randseq(s); x2=randseq(s); a2=resp(y2,x2,v2); }
if (FS2) { b2=flip(a2); }else{
y2=randseq(s); x2=randseq(s); b2=resp(y2,x2,v2); }
// y2=randseq(v2); // x2=randseq(v2); //
if (!FB) {
b=[1].concat(a2).concat(randseq(1)).concat(b2);
// b=[1].concat(a2).concat(randseq(1)).concat(minp(b2));
// b=[-1].concat(a2).concat(minp(b2)).concat(randseq(1));
}else{ // b=[-1].concat(b2).concat(minp(b2));
b=[-1].concat(a2).concat(b2); }
}else{
y2=randseq(s); x2=randseq(s); b=resp(y2,x2,v);
// x2=randseq(s); b=resp(y1,x2,v);
// b=resp(y1,x1,v);
}
B=circul(b);
}}
function initmatrix(n,q,min) {
function getH() {
var H; getAB();
if (F2) { H=twocircul(A,B);
if (FB) { H=border(H,1,1,-1); H=border(H,-1);}
}else{if (FB) { H=border(A,-1,1); }else{ H=equal(A);}}
if (F4) { getAB();
if (F2) { H2=twocircul(A,B);
if (FB) { H2=border(H2,1,1,-1); H2=border(H2,-1);}
}else{if (FB) { H2=border(A,-1,1); }else{ H2=equal(A);}}
H=twocircul(H,H2);
}
return H;
}
minx=1000; H=getH();
while (q>0) { q=q-1; H2=getH();
maxx=maxabslsm(H2);
if (maxx<minx) { minx=maxx; H=equal(H2);
if (minx<=min) q=0;
}
}
return H;
}
function analysis() {
// MATRIX ANALYSIS
function getis(a) {
// get index of symmetry
var i,v,F,IS; v=rows(a); F=true; IS=1;
for (i=1;i<=v/2;i++) if (F) { IS=i; F=a[i]==a[v-i]; }
return IS;
}
function setmaxis(x) {
// set maximal index of symmetry
var i,v,a,b,F,IS,ISM;
a=equal(x); b=equal(x); ISM=getis(a); v=rows(a);
for (i=1;i<v;i++) { a=circshift(a); IS=getis(a);
if (IS>ISM) { b=equal(a); ISM=IS;}}
return b;
}
function getish(a) {
// get index of hamming symmetry
var i,v,IS; v=rows(a); IS=1;
for (i=1;i<v/2;i++) if (a[i]==a[v-i]) IS++;
return IS;
}
function setmaxish(x) {
// set maximal index of hamming symmetry
var i,v,a,b,IS,ISM;
a=equal(x); b=equal(x); ISM=getish(a); v=rows(a);
for (i=1;i<v;i++) { a=circshift(a); IS=getish(a);
if (IS>ISM) { b=equal(a); ISM=IS;}}
return b;
}
if (F2) {
if (FB) {
a=tr(rowcol(H,2,2,2,v+1)); b=tr(rowcol(H,2,2,2+v,n-1));
}else{
a=tr(rowcol(H,0,0,0,v-1)); b=tr(rowcol(H,0,0,v,n-1));
}}else{
if (FB) {
a=tr(rowcol(H,1,1,1,n-1)); }else{ a=tr(rowcol(H,0,0,0,n-1));
}}
if (F4) { H=rowcol(H,0,n-1,n,n2-1);
if (F2) {
if (FB) {
c=tr(rowcol(H,2,2,2,v+1)); d=tr(rowcol(H,2,2,2+v,n-1));
}else{
c=tr(rowcol(H,0,0,0,v-1)); d=tr(rowcol(H,0,0,v,n-1));
}}else{
if (FB) {
c=tr(rowcol(H,1,1,1,n-1)); }else{ d=tr(rowcol(H,0,0,0,n-1));
}}
}
if (0) {
// OPTIMISATION OF A,B
a=setmaxis(a);
if (sum(a)<0) a=minp(a); IS1=getis(a);
if (F2) {
b=setmaxis(b);
if (sum(b)<0) b=minp(b); IS2=getis(b);
puts('IS='+IS1+','+IS2); }else{ puts('IS='+IS1); }
}
putm("a=["+a+"];"); if (F2) putm("b=["+b+"];");
if (F2) { H=twocircul(circ(a),circ(b));
if (FB) { H=border(H,1,1,-1); H=border(H,-1);}
}else{ H=circ(a); if (FB) H=border(H,-1,1); }
if (F4) {
putm("c=["+c+"];"); if (F2) putm("d=["+d+"];");
if (F2) { H2=twocircul(circ(c),circ(d));
if (FB) { H2=border(H2,1,1,-1); H2=border(H2,-1);}
}else{if (FB) { H2=border(A,-1,1); }else{ H2=equal(A);}}
H=twocircul(H,H2);
}
plots(H,"XR");
}

// HADAMARD MATRICES
{{H="H16RF.xml"}}
mesh(H); putm(H); // {{I=H'*H}} putm(I);

Two four circulant matrices H_{8} Two four-circulant matrices H_{12} Two four-circulant matrices H_{16} Four-circulant matrix H_{20} and H_{24} Four-circulant matrices H_{28} Four-circulant matrices H_{32} and H_{36} Fifth-circulant matrix H_{40} and H_{48} Four-circulant matrix H_{52} Four-circulant matrices H_{60} and H_{64} Note: matrices H_{24} , H_{40} have 5 different cells (!)

1. H. J. Ryser, Combinatorial mathematics. The Carus Mathematical Monographs, No. 14, Published by The Mathematical Association of America; distributed by John Wiley and Sons, Inc., New York 1963.

WILLIAMSON MATRICES | TWO-CIRCULANT HADAMARD MATRICES | C-MATRICES