MULTI-CIRCULANT CONFERENCE MATRICES © Nickolay Balonin and Jennifer Seberry, 1.05.2014 Multi-circulant conference matrix catalogue and on-line algorithms

N. A. Balonin, Jennifer Seberry A Review and New Symmetric Conference Matrices //Informatsionno-upravliaiushchie sistemy, 2014, № 4 (71), pp. 2–7.

Main matrix consists the blocks with circulant matrices. The two circulant structure – it's too universal. The set of symmetry A, D and some tied pair-sequences of (B, C) and (E, F), it has enough big quantity of invariants to describe conference matrices iff n–1 is prime. The private line of orders, it is oriented on the C_{66} . This matrix absence is a special question of theory. We observe a line of multi-circulant matrices with orders n =2·3·k , k – integer 1, 3, 5, 7, 9, 11, 13, 15.., it covers orders 6, 18, 34, 42, 54, (66!?), (70), 90, ...

// SEARCH PROCEDURE
// 18, 30, 42, 54, [66]
if (tick==0) {
n=30; q=n/6; m=(q-1)/2; Max=1000;
// PRECODES
a=one(m); d=one(m); a1=0; d1=1;
if ((n==30)||(n==54)) d1=-1;
if (n==42) { a=[-1,-1,1]; d=flip(a); }
if (n==54) { a=[1,-1,1,1]; d=[-1,-1,1,1]; }
// if (n==66) { a=[-1,-1,-1,1,1]; d=[1,-1,1,1,1]; }
a=[a1].concat(a).concat(flip(a));
d=[d1].concat(d).concat(flip(d));
}
p=100; // number of iterations
while (p>0) { p--;
// VERSIONS OF SEQUENCES
a=signm(rand(m));
a=[0].concat(a).concat(flip(a));
b=signm(rand(q));
// b=signm(rand(1)).concat(b).concat(flip(b));
if (n==54) { // b=[-1,-1,-1,-1,1,-1,-1,1,1];
c=flip(b); }else{ c=flip(minp(b)); }
// c=signm(rand(q));
// c=signm(rand(1)).concat(c).concat(flip(c));
d=signm(rand(m));
d=signm(rand(1)).concat(d).concat(flip(d));
e=signm(rand(q));
// e=signm(rand(1)).concat(e).concat(flip(e));
if (n==54) {
f=flip(e); }else{ f=flip(minp(e)); }
// f=signm(rand(q));
// f=signm(rand(1)).concat(f).concat(flip(f));
// if (n==54) { f=flip(e); }else{ f=flip(minp(e)); }
// SEQUENCES C30
// a=one(q); d=minp(a); a[0]=0; d[0]=1;
// b=legendre(q); b[0]=-1; c=flip(b); b=minp(b);
// e=legendre(q); e[0]=1;
// e=circshiftback(circshiftback(e)); f=flip(minp(e));
// a=[0,1,1,1,1]; b=[1,-1,1,1,-1]; c=[1,-1,-1,1,-1];
// d=[1,-1,-1,-1,-1]; e=[-1,-1,1,1,1]; f=[-1,-1,-1,1,1];
// a=one(q); d=minp(a); a[0]=0; d[0]=1; d=minp(d);
// b=legendre(q); b[0]=1; c=equal(b);
// e=equal(b); e[0]=1; e[0]=-1;
// e=flip(e); f=equal(e);
// c=circshift(c); c=circshift(minp(c));
// f=circshiftback(f); f=circshiftback(minp(e));
// a=[0,1,-1,-1,-1,-1,1]; b=[-1,-1,1,-1,-1,1,-1];
// c=[1,-1,1,1,-1,1,1]; d=[1,-1,1,-1,-1,1,-1];
// e=[-1,-1,-1,-1,1,1,-1]; f=[1,-1,-1,1,1,1,1];
// a=[0,1,1,1,1]; b=[1,1,-1,-1,1]; c=[1,-1,-1,-1,1];
// d=[-1,1,1,1,1]; e=[1,-1,-1,1,-1]; f=[1,1,-1,1,-1];
// a=[0,1,1]; b=[-1,1,1]; c=flip(b);
// d=[-1,-1,-1]; e=[1,1,-1]; f=flip(e);
matrixH(); M=maxabslsm(H);
if (M<Max) { Max=M; mesh(H);
if (Max==0) p=-100;
}
}
puts("n="+n+" tick="+tick+" M="+Max);
if (p!=-100) { restart(0); }else{
puts("a=["+a+"];"); puts("b=["+b+"];"); puts("c=["+c+"];");
puts("d=["+d+"];"); puts("e=["+e+"];"); puts("f=["+f+"];");
{{X=H'*H}} putm(X); mesh(H);
}
function matrixH() {
A=circul(a); B=circul(b); C=circul(c);
D=circul(d); Eu=circul(e); F=circul(f);
S=toeplitz3(A,B,C); G=toeplitz3(D,Eu,F);
H=square(S,G,tr(G),minp(S));
}
function toeplitz3(A,B,C) {
var T1,T2,T3,TB,TC; TB=tr(B); TC=tr(C);
T1=tr(colline(A,B,C));
T2=tr(colline(TB,A,B));
T3=tr(colline(TC,TB,A));
return tr(colline(T1,T2,T3));
}

// GALOIS FIELD PROCEDURE
// 18, 30, 42, 54, [66]
if (tick==0) {
n=30; q=n/6; m=(q-1)/2; Max=1000; gfinit(q);
}
p=100; // number of iterations
while (p>0) { p--;
// VERSIONS OF SEQUENCES
x=gfrand(); L1=randint(q);
P=randint(q); P1=randint(q); P2=randint(q);
EX0=gfexp(x,q,L1,P);
EX1=gfexp(x,q,L1,P1); A=EX0.concat(EX1); a=ds2a(q,A);
EX2=gfexp(x,q,L1,P2); B=EX0.concat(EX2); b=ds2a(q,B);
c=flip(b);
x=gfrand(); L2=L1; // randint(q);
// P=randint(q); P1=randint(q); P2=randint(q);
EX0=gfexp(x,q,L2,P);
EX1=gfexp(x,q,L2,P1); A=EX0.concat(EX1); d=ds2a(q,A);
EX2=gfexp(x,q,L2,P2); B=EX0.concat(EX2); e=ds2a(q,B);
f=flip(e); a[0]=0;
matrixH(); M=maxabslsm(H);
if (M<Max) { Max=M; mesh(H);
if (Max==0) p=-100;
}
}
puts("n="+n+" q="+q+" tick="+tick+" M="+Max);
if (p!=-100) { restart(0); }else{
puts("L1="+L1+" L2="+L2+" P="+P+" P1="+P1+" P2="+P2);
puts("a=["+a+"];"); puts("b=["+b+"];"); puts("c=["+c+"];");
puts("d=["+d+"];"); puts("e=["+e+"];"); puts("f=["+f+"];");
{{X=H'*H}} putm(X); mesh(H);
}
function matrixH() {
A=circul(a); B=circul(b); C=circul(c);
D=circul(d); Eu=circul(e); F=circul(f);
S=toeplitz3(A,B,C); G=toeplitz3(D,Eu,F);
H=square(S,G,tr(G),minp(S));
}
function toeplitz3(A,B,C) {
var T1,T2,T3,TB,TC; TB=tr(B); TC=tr(C);
T1=tr(colline(A,B,C));
T2=tr(colline(TB,A,B));
T3=tr(colline(TC,TB,A));
return tr(colline(T1,T2,T3));
}

// SEARCH PROCEDURE
// 18, 30, 42, 54, [66]
if (tick==0) {
n=30; q=n/6; m=(q-1)/2; Max=1000;
}
p=100; // number of iterations
while (p>0) { p--;
// VERSIONS OF SEQUENCES
a=signm(rand(m));
a=[0].concat(a).concat(flip(a));
b=signm(rand(q));
d=signm(rand(m));
d=signm(rand(1)).concat(d).concat(flip(d));
e=signm(rand(q));
matrixH(); M=maxabslsm(H);
if (M<Max) { Max=M; mesh(H);
if (Max==0) p=-100;
}
}
puts("n="+n+" tick="+tick+" M="+Max);
if (p!=-100) { restart(0); }else{
puts("a=["+a+"];"); puts("b=["+b+"];"); //puts("c=["+c+"];");
puts("d=["+d+"];"); puts("e=["+e+"];"); //puts("f=["+f+"];");
{{X=H'*H}} putm(X); mesh(H);
}
function matrixH() {
A=circul(a); B=circul(b); // C=circul(c);
D=circul(d); Eu=circul(e); // F=circul(f);
S=toeplitz3(A,B); G=toeplitz3(D,Eu);
H=square(S,G,tr(G),minp(S));
}
function toeplitz3(A,B) {
var T1,T2,T3,TB,TC; TB=tr(B); //TC=tr(C);
T1=tr(colline(A,B,TB));
T2=tr(colline(TB,A,B));
T3=tr(colline(B,TB,A));
return tr(colline(T1,T2,T3));
}

THE SAMPLES OF CONFERENCE MATRICES

The solution has the pair-sequences (B, C=flip(±B)) and (E, F=flip(±E)). It leads to the following samples of multi-circulant matrices:

Circulant matrices C_{6} and C_{18} Circulant matrices C_{30} and C_{42} Circulant matrices C_{54}

{{C="C18FL.xml"}}
mesh(C); putm(C); // {{I=C'*C}} putm(I);

THE SAMPLES OF CONFERENCE MATRICES

The solution has the pair-sequences, C-secuence is shifted accordingly B to the left in (B, C) and F-secuence is shifted accordingly E to the right in (E, F). It could be any shifts to any sides, need they were different. Matrix C_{54} looks like non reachable.

Circulant matrix C_{6} Circulant matrices C_{18} and C_{30} Circulant matrices C_{42} (3 shifts) and C_{42} (4 shifts)

{{C="C18SH.xml"}}
mesh(C); putm(C); // {{I=C'*C}} putm(I);

GET MORE COLOURS

// SEARCH PROCEDURE
// 18, 30, 42, 54, [66]
if (tick==0) {
n=30; q=n/6; f=q; // f=2*q-1;
m=(q-1)/2; Max=1000; Lambda=2; P=0;
if (f==27) { gfinit(3,3); }else{ gfinit(f); }
}
p=100; x=gfadd(GFe,GFe); // number of iterations
while (p>0) {
// VERSIONS OF SEQUENCES
if (p<100) x=gfrand(); p--;
Q=gfexp(x,q,Lambda,P); // putm("Q="+Q);
A=gfadd(GFe,Q); // putm("Q+1="+A);
B=gfsub(GFe,Q); // putm("Q-1="+B);
a=minp(gfeq(A,Q)); d=minp(gfeq(B,Q)); a[0]=0; // d[0]=-1;
// a=signm(rand(m));
// a=[0].concat(a).concat(flip(a));
b=signm(rand(q));
// b=signm(rand(1)).concat(b).concat(flip(b));
if (n==54) {
c=flip(b); }else{ c=flip(minp(b)); }
// c=signm(rand(q));
// c=signm(rand(1)).concat(c).concat(flip(c));
// d=signm(rand(m));
// d=signm(rand(1)).concat(d).concat(flip(d));
e=signm(rand(q));
// e=signm(rand(1)).concat(e).concat(flip(e));
if (n==54) {
f=flip(e); }else{ f=flip(minp(e)); }
// f=signm(rand(q));
matrixH(); M=maxabslsm(H);
if (M<Max) { Max=M; mesh(H);
if (Max==0) p=-100;
}
}
puts("n="+n+" tick="+tick+" M="+Max);
if (p!=-100) { restart(0); }else{
puts("a=["+a+"];"); puts("b=["+b+"];"); puts("c=["+c+"];");
puts("d=["+d+"];"); puts("e=["+e+"];"); puts("f=["+f+"];");
{{X=H'*H}} putm(X); mesh(H);
}
function matrixH() {
A=circul(a); B=circul(b); C=circul(c);
D=circul(d); Eu=circul(e); F=circul(f);
S=toeplitz3(A,B,C); G=toeplitz3(D,Eu,F);
H=square(S,G,tr(G),minp(S));
}
function toeplitz3(A,B,C) {
var T1,T2,T3,TB,TC; TB=tr(B); TC=tr(C);
T1=tr(colline(A,B,C));
T2=tr(colline(TB,A,B));
T3=tr(colline(TC,TB,A));
return tr(colline(T1,T2,T3));
}

TWO-CIRCULANT MATRICES