Double and bo de ed α-ci culan sel -dual codes o e ini e
commu a i e chain ings
Michael Kie maie and Al ed Wasse mann
ABSTRACT. In his pape we in es iga e codes o e ini e commu a i e ings R, whose gene a-
o ma ices a e buil om α-ci culan ma ices. Fo a non- i ial ideal I < R we gi e a me hod
o li such codes o e R/I o codes o e R, such ha some isomo phic copies a e a oided.
Fo he case whe e Iis he minimal ideal o a ini e chain ing we e ine his li ing me hod:
We impose he addi ional es ic ion ha li ing p ese es sel -duali y. I will be shown ha his
can be achie ed by sol ing a linea sys em o equa ions o e a ini e ield.
Finally we apply his echnique o Z4-linea double nega-ci culan and bo de ed ci culan
sel -dual codes. We de e mine he bes minimum Lee dis ance o hese codes up o leng h 64.
1. α-ci culan ma ices
In his sec ion, we gi e some basic ac s on α-ci culan ma ices, compa e wi h [4, chap e 16],
whe e some heo y o ci culan ma ices is gi en, and wi h [1, page 84], whe e α-ci culan
ma ices a e called {k}-ci culan .
DEFINITION 1.1. Le Rbe a commu a i e ing, ka na u al numbe and α∈R. A (k×k)-
ma ix Ais called α-ci culan , i Ahas he o m






a0a1a2. . . ak−2ak−1
αak−1a0a1. . . ak−3ak−2
αak−2αak−1a0. . . ak−4ak−3
.
.
..
.
..
.
..
.
..
.
.
αa1αa2αa3. . . αak−1a0






wi h ai∈R o i∈ {0, . . . , k −1}. Fo α= 1,Ais called ci culan , o α=−1,Ais called
nega-ci culan o skew-ci culan , and o α= 0,Ais called semi-ci culan .
An α-ci culan ma ix Ais comple ely de e mined by i s i s ow = (a0, a1, . . . , ak−1)∈Rk.
We deno e Aby ci cα( )and say ha Ais he α-ci culan ma ix gene a ed by .
In he ollowing, αusually will be a uni o e en α2= 1.
We de ine Tα= ci cα(0,1,0,...,0), ha is
Tα=






1
1
...
1
α






Key wo ds and ph ases. linea code o e ings, sel -dual code, ci culan ma ix, ini e chain ing.
1
Using Tα, he e is ano he cha ac e iza ion o an α-ci culan ma ix: A ma ix A∈Rk×kis
α-ci culan i ATα=TαA. This is seen di ec ly by compa ing he componen s o he wo
ma ix p oduc s.
In he ollowing i will be use ul o iden i y he gene a ing ec o s (a0, a1, . . . , ak−1)∈Rn
wi h he polynomials Pk−1
i=0 aixi∈R[x]o deg ee a mos k−1, which again can be seen as
a se o ep esen a i es o he R-algeb a R[x]/(xk−α). Thus, we ge an injec i e mapping
ci cα:R[x]/(xk−α)→Rk×k.
Ob iously ci cα(1) = Ik, which deno es he (k×k)-uni ma ix, ci cα(λ ) = λci cα( )and
ci cα( +g) = ci cα( ) + ci cα(g) o all scala s λ∈Rand all and gin R[x]/(xk−α).
Fu he mo e, i holds ci cα(ei) = ci cα(xi) = Ti
α o all i∈ {0, . . . , k −1}and ci cα(xk) =
ci cα(α) = αIk=Tk
α, whe e eideno es he i h1uni ec o . So we ha e ci cα(xixj) =
ci cα(xi) ci cα(xj) o all {i, j} ⊂ N. By linea ex ension i ollows ha ci cαis a monomo -
phism o R-algeb as. Hence he image o ci cα, which is he se o he α-ci culan (k×k)-
ma ices o e R, o ms a commu a i e subalgeb a o he R-algeb a Rk×kand i is isomo phic
o he R-algeb a R[x]/(xk−α). Especially, we ge ci cα(a0, . . . , ak−1) = Pk−1
i=0 aiTi
α.
2. Double α-ci culan and bo de ed α-ci culan codes
DEFINITION 2.1. Le Rbe a commu a i e ing and α∈R. Le Abe an α-ci culan ma ix. A
code gene a ed by a gene a o ma ix
(Ik|A)
is called double α-ci culan code. A code gene a ed by a gene a o ma ix




Ik
β γ · · · γ
δ
.
.
.
δ
A




wi h {β, γ, δ} ⊂ R}is called bo de ed α-ci culan code. The numbe o ows o such a
gene a o ma ix is deno ed by k, and he numbe o columns is deno ed by n= 2k.
As usual, wo codes C1and C2a e called equi alen o isomo phic, i he e is a monomial
ans o ma ion ha maps C1 o C2.
DEFINITION 2.2. Le Rbe a commu a i e ing and k∈N. The symme ic g oup o e he se
{0, . . . , k −1}is deno ed by Sk. Fo a pe mu a ion σ∈Sk he pe mu a ion ma ix S(σ)is
de ined as Sij =δi,σ(j), whe e δis he K onecke del a. An in e ible ma ix M∈GL(k, R)is
called monomial, i M=S(σ)D o a pe mu a ion σ∈Skand an in e ible diagonal ma ix
D. The decomposi ion o a monomial ma ix in o he pe mu a ional and he diagonal ma ix
pa is unique.
Le M=M(k, R, α)be he se o all pai s (N, M)o monomial (k×k)-ma ices Mand No e
R, such ha o each α-ci culan ma ix A∈Rk×k, he ma ix N−1AM is again α-ci culan .
An elemen (N, M)o Mcan be in e p e ed as a mapping Rk×k→Rk×k,A7→ N−1AM.
The composi ion o mappings implies a g oup s uc u e on M, and Mope a es on he se o all
α-ci culan ma ices.
Now le (N, M)∈M. The codes gene a ed by (I|A)and by (I|N−1AM)a e equi alen ,
since
N−1(I|A)N0
0M= (I|N−1AM)
1Th oughou his a icle, coun ing s a s a 0. Acco dingly, N={0,1,2, . . .}
2
and he ma ix N0
0Mis monomial. Thus, Malso ope a es on he se o all double α-
ci culan gene a o ma ices.
In gene al M-equi alence is weake han he code equi alence: Fo example he ec o s =
(1111101011011010) ∈Z16
2and w= (1110010011100000) ∈Z16
2gene a e wo equi alen
bina y double ci culan sel -dual [32,16]-codes. Bu since he numbe o ze os in and wis
di e en , he wo ci culan ma ices gene a ed by and wcanno be in he same M-o bi .
3. Monomial ans o ma ions o α-ci culan ma ices
Le Rbe a commu a i e ing, k∈Nand α∈Ra uni . In his sec ion we gi e some elemen s
(N, M)o he g oup M=M(R, k, α)de ined in he las sec ion. In pa hey can be deduced
om [4, chap e 16, §6, p oblem 7].
Qui e ob ious elemen s o Ma e (Ik, Tα),(Tα, Ik),(Ik, D)and (D, Ik), whe e Ddeno es an
in e ible scala ma ix.
Fo ce ain α u he elemen s o Ma e gi en by he ollowing lemma, which is checked by a
calcula ion:
LEMMA 3.1. Le α∈Rwi h α2= 1 and s∈ {0, . . . , k −1}wi h gcd(s, k) = 1. Le
σ= (i7→ si mod k)∈Sk. We de ine Das he diagonal ma ix which has α(s+1)i+bsi/kcas
i- h diagonal en y, and we de ine he monomial ma ix M=S(σ)D. Then
(M, M)∈M
Mo e speci ically: Le ∈R[x]/(xk−α). I holds:
M−1ci cα( )M= ci cα( ((αx)s))
Finally, he e is an in e ible ans o ma ion A7→ M−1AM ha con e s an α-ci culan ma ix
in o a β-ci culan ma ix o ce ain pai s (α, β):
LEMMA 3.2. Le Rbe a commu a i e ing, α∈Ra uni and {i, j} ⊂ N. Le Abe an
αi-ci culan (k×k)-ma ix o e Rand M he diagonal ma ix wi h he diagonal ec o
(1, αj, α2j, . . . , α(k−1)j). Then M−1AM is an αi−kj-ci culan ma ix. Fo α2= 1 he ma-
ix Mis o hogonal.
4. The li o an α-ci culan ma ix
I we wan o cons uc all equi alence classes o double α-ci culan codes o e a commu a i e
ing R, i is enough o conside o bi ep esen a i es o he g oup ac ion o Mon he se o all
double α-ci culan gene a o ma ices, o equi alen ly, on he se o all α-ci culan ma ices.
Fu he mo e, we can bene i om non- i ial ideals o R: Le Ibe an ideal o Rwi h {0} 6=
I6=R, and¯ : R→R/I he canonical p ojec ion o Ron o R/I. We se M=M(k, R, α)and
¯
M={(¯
N, ¯
M):(N, M)∈M}. I holds ¯
M⊆M(k, R/I, ¯α). Le e:R/I →Rbe a mapping
ha maps each elemen +Io R/I o a ep esen a i e elemen ∈R.
DEFINITION 4.1. Le A= ci c¯α( )be an ¯α-ci culan ma ix wi h gene a ing ec o ∈R/I.
An α-ci culan ma ix Bo e Ris called li o A, i ¯
B=A. In his case we also say ha he
code gene a ed by (Ik|B)is a li o he code gene a ed by (Ik|A). The li s o Aa e exac ly
he ma ices o he o m ci cα(e( ))+ci cα(w)wi h w∈Ik.2The ec o wis called li ec o .
2To a oid con usion, we poin ou ha Ikdeno es he k- old Ca esian p oduc I×. . . ×Ihe e.
3
To ind all double α-ci culan codes o e R, we can un o e all li s o all double ¯α-ci culan
codes o e R/I. The c ucial poin now is ha o inding a leas one ep esen a i e all equi -
alence classes o double α-ci culan codes o e R, i is enough o un o e he li s o a se o
ep esen a i es o he g oup ac ion o ¯
Mon he se o all ¯α-ci culan codes o e R/I:
LEMMA 4.1. Le Aand Bbe wo ¯α-ci culan ma ices o e R/I which a e in he same ¯
M-
o bi . Then o each li o A he e is a li o Bwhich is in he same M-o bi .
PROOF. Because Aand Ba e in he same ¯
M-o bi , he e is a pai o monomial ma ices
(N, M)∈Msuch ha ¯
N−1A¯
M=B. Le a∈(R/I)kbe he gene a ing ec o o Aand
b∈(R/I)k he gene a ing ec o o B. Since ci cα(e(a)) = Aand ci cα(e(b)) = Bi holds
N−1ci cα(e(a))M= ci cα(e(b)) + K, whe e K∈Ik×k.ci cα(e(b)) is o cou se α-ci culan ,
and N−1ci cα(e(a))Mis α-ci culan because o (N, M)∈M. Thus, also Kis α-ci culan
and he e o e he e is a z∈Ikwi h ci cα(z) = K.
Now, le w∈Ikbe some li ec o . N−1ci cα(w)M∈Ik×kis α-ci culan and gene a ed by a
li ec o w0∈Ik. Then N−1(ci cα(e(a)) + ci cα(w))M= ci cα(e(b)) + ci cα(z+w0), and
z+w0∈Ik. The e o e, he li o Aby he li ec o wand he li o Bby he li ec o
z+w0a e in he same M-o bi . 
I is no ha d o adap his app oach o bo de ed α-ci culan codes. One di e ence is an addi-
ional es ic ion on he appea ing monomial ma ices: I s diagonal pa mus be a scala ma ix.
The eason o his is ha o he wise he monomial ans o ma ions would des oy he bo de
ec o s (γ . . . γ)and (δ . . . δ) .
Ci culan ma ices a e o en used o cons uc sel -dual codes. Thus we a e in e es ed in a as
way o gene a e he li s ha lead o sel -dual codes. The nex sec ion gi es such an algo i hm
o he case ha Ris a ini e chain ing and Iis i s minimal ideal.
5. Sel -dual double α-ci culan codes o e ini e commu a i e chain ings
We wan o in es iga e sel -dual double α-ci culan codes. He e we need α2= 1. This is
seen by deno ing he ows o a gene a o ma ix Go such a code by w0. . . wk−1, and by
compa ing he scala p oduc s hw0, w1iand hw1, w2i, which mus be bo h ze o. Fu he mo e,
gi en α2= 1, we see ha hw0, wii=hwj, wi+ji, whe e i+ja e aken modulo k. Thus G
gene a es a sel -dual code i hw0, w0i= 1 and o all j∈ {1,...,bk/2c} he scala p oduc s
hw0, wjia e equal o 0.
DEFINITION 5.1. A ing Ris called chain ing, i i s le ideals a e linea ily o de ed by inclu-
sion.
Fo he heo y o ini e chain ings and linea codes o e ini e chain ings see [2].
In his sec ion Rwill be a ini e commu a i e chain ing, which is no a ini e ield, and αan
elemen o Rwi h α2= 1. The e is a ing elemen θ∈Rwhich gene a es he maximal ideal Rθ
o R. The numbe qis de ined by R/Rθ ∼
=Fq, and mis de ined by |R|=qm. Because Ris no
a ield, we ha e m≥2. The minimal ideal o Ris Rθm−1.Mis de ined as in sec ion 2, wi h
wi h he di e ence ha all monomial ma ices Mshould be o hogonal, ha is MM =Ik.
Thus each M-image o a gene a o ma ix o a sel -dual code again gene a es a sel -dual code.
Now le I=Rθm−1be he minimal ideal o R. As in sec ion 4 le e:R/I →Rbe a mapping
ha assignes each elemen o R/I o a ep esen a i e in R, now wi h he addi ional condi ion
e(¯α) = α.
4
We men ion ha i (Ik|B)gene a es a double α-ci culan sel -dual code o e R, hen (Ik|¯
B)
gene a es a double ¯α-ci culan sel -dual code o e R/I. So Bis among he li s o all ¯α-
ci culan ma ices Ao e R/I such ha (Ik|A)gene a es a sel -dual double ¯α-ci culan code.
Le A= ci c¯α(a)be an ¯α-ci culan ma ix o e R/I such ha (Ik|A)gene a es a sel -dual
code. So AA =−Ik, and he e o e
c0:= 1 +
k−1
X
i=0
e(ai)2∈Iand
cj:=
j−1
X
i=0
αe(ai)e(ak−j+i) +
k−1
X
i=j
e(ai)e(ai−j)∈I o all j∈ {1,...,bk/2c}
We wan o ind all li s B= ci cα(e(a)) + ci cα(w)o Awi h w∈Iksuch ha BB =−Ik.
As we ha e seen, his is equi alen o
0 = 1 +
k−1
X
i=0
(e(ai) + wi)2and
0 =
j−1
X
i=0
(e(ai) + wi)(αe(ak−j+i) + wk−j+i) +
k−1
X
i=j
(e(ai) + wi)(e(ai−j) + wi−j)
whe e he second equa ion holds o all j∈ {1,...,bk/2c}. Using I·I= 0, we ge
0 = c0+ 2
k−1
X
i=0
e(ai)wiand
0 = cj+
j−1
X
i=0
(e(ai)wk−j+i+αe(ak−j+i)wi) +
k−1
X
i=j
(e(ai)wi−j+e(ai−j)wi)
This is a R-linea sys em o equa ions o he componen s wi∈Io he li ec o . Using he
ac ha he R-modules R/(Rθ)and Ia e isomo phic, and R/(Rθ)∼
=Fq, his can be e o mu-
la ed as a linea sys em o equa ions o e he ini e ield Fq, which can be sol ed e icien ly.
Since R/I is again a commu a i e chain ing, he li ing s ep can be applied epea edly. Thus,
s a ing wi h he codes o e Fq, he codes o e Rcan be cons uc ed by m−1nes ed li ing
s eps.
Again, his me hod can be adap ed o bo de ed α-ci culan ma ices o e commu a i e ini e
chain ings.
6. Applica ion: Sel -dual codes o e Z4
Fo a ixed leng h nwe wan o ind he highes minimum Lee dis ance dLee o double nega-
ci culan and bo de ed ci culan sel -dual codes o e Z4. In [5] codes o he bo de ed ci culan
ype o leng h up o 32 we e in es iga ed.
Fi s we no ice ha he leng h nmus be a mul iple o 8: Le Cbe a bo de ed ci culan o
a double nega-ci culan code o leng h nand ca codewo d o C. We ha e 0 = hc, ci=
Pn−1
i=0 c2
i∈Z4. The las exp ession equals he numbe o uni s in cmodulo 4, so he numbe
o uni s o each codewo d is a mul iple o 4. I ollows ha he image ¯
Co Co e Z2is a
doubly-e en sel -dual code o leng h n, which can only exis o leng hs ndi isible by 8.
Fu he mo e, i holds
dLee(C)≤2dHam(¯
C)(1)
5

As a esul , we only need o conside he li s o codes ¯
Cwhich ha e a su icien ly high mini-
mum Hamming dis ance.
We explain he algo i hm o he case o he nega-ci culan codes: In a i s s ep, o a gi en
leng h nwe gene a e all doubly-e en double ci culan sel -dual codes o e Z2. This is done
by enume a ing Lyndon wo ds o leng h nwhich se e as gene a ing ec o s o he ci culan
ma ix. Nex , we il e ou all duplica es wi h espec o he g oup ac ion o M, whe e Mis
he g oup gene a ed by he elemen s gi en in sec ion 3 which consis o pai s o o hogonal
monomial ma ices.
A a iable dwill keep he bes minimum Lee dis ance we al eady ound. We ini ialize dwi h
0. Now we loop o e all bina y codes CZ2in ou lis , om he highe o he lowe minimum
Hamming dis ance o CZ2: I 2dHam(CZ2)≤dwe a e inished because o (1). O he wise, as
explained in sec ion 5, we sol e a sys em o linea equa ions o e Z2and ge all sel -dual li s
o CZ2. Fo hese li s we compu e he minimum Lee dis ance and upda e dacco dingly.
Mos o he compu a ion ime is spen on he compu a ion o he minimum Lee dis ances. Thus
i was a c ucial poin o w i e a specialized algo i hm o his pu pose. I is desc ibed in [3].
The esul s o ou sea ch a e displayed in he ollowing able. Fo gi en leng h n, i lis s he
highes minimum Lee dis ance o a sel -dual code o he espec i e ype:
n8 16 24 32 40 48 56 64
double nega-ci culan 6 8 12 14 14 18 16 20
bo de ed ci culan 6 8 12 14 14 18 18 20
We see ha he esul s a e iden ical o he wo classes o codes, excep o leng h 56. Using
(1) he e is a simple eason ha o his leng h no double ci culan sel -dual code o e Z4wi h
minimum Lee dis ance g ea e han 16 exis s: The bes doubly-e en double ci culan sel -dual
bina y code has only minimum Hamming dis ance 8.
Acknowledgmen
This esea ch was suppo ed in pa by Deu sche Fo schungsgemeinscha WA 1666/4-1.
Re e ences
[1] Philip J. Da is. Ci culan Ma ices. Chelesa publishing, New Yo k, second edi ion, 1994.
[2] Thomas Honold and I an Landje . Linea codes o e ini e chain ings. Elec . J. Comb., 7, 2000.
[3] Michael Kie maie and Al ed Wasse mann. On he Minimum Lee Dis ance o Quad a ic Residue Codes o e
Z4. In P oceedings o he In e na ional Symposium on In o ma ion Theo y (ISIT), 2008. o appea .
[4] F. J. MacWilliams and N. J. A. Sloane. The Theo y o E o -Co ec ing Codes. No h-Holland, Ams e dam,
1977.
[5] Masaaki Ha ada T. Aa on Gulli e . Ex emal double ci culan Type II codes o e Z4and cons uc ion o
5-(24, 10, 36) designs. Disc e e Ma hema ics, 194:129–137, 1999.
MICHAEL KIERMAIER, MATHEMATICAL DEPARTMENT, UNIVERSITY OF BAYREUTH, D-95440 BAYREUTH,
GERMANY
E-mail add ess:[email p o ec ed]
URL:h p://www.ma he2.uni-bay eu h.de/michaelk/
ALFRED WASSERMANN, MATHEMATICAL DEPARTMENT, UNIVERSITY OF BAYREUTH, D-95440 BAYREUTH,
GERMANY
E-mail add ess:[email p o ec ed]
URL:h p://did.ma .uni-bay eu h.de/~al ed/home/index.h ml
6