restart:
Tuttepoly.mw by Thomas Britz, 310108
The procedure Tuttepoly below calculates the Tutte polynomial of a linear code over GF(p) where p is prime or p=4given by a generator matrix of the form A=[I|D] for some matrix r x k matrix D.
The procedure SDTuttepoly below may be used to halve the calculations when code is self-dual or is equivalent to its dual code.
### recurse ###
# Input: D, r, k where D is an r by k matrix
# Output: the Tutte polynomial of A=[I_r|D] (so A has r+k columns)
#
recurse := proc(DD,r,k)
local i,ii,j,jj,ncl,nl,nc,B,br,bk:
#print(evalm(DD),r,k);
# If D is a single row
if r = 1 then nl:=0: for j from 1 to k do if DD[1,j]=0 then nl := nl+1 fi:od:
return y^nl*(x+(y^(r+k-nl)-y)/(y-1)) fi:
# If D is a single column
if k = 1 then ncl:=0: for i from 1 to r do if DD[i,1]=0 then ncl := ncl+1 fi:od:
return x^ncl*(y+(x^(r+k-ncl)-x)/(x-1)) fi:
# Find the first column j with a 1-entry in row 1 of D
j:=1: while (j<=k and DD[1,j]=0) do j:=j+1: od:
br:= r-1:
bk:= k-1:
B:=DD[2..r,1..k]:
# If first column in A is a coloop
if j=k+1 then return x*recurse(B,br,k) fi:
# From here on, the first column in A is simple (i.e., there is a 1-entry in row 1)
# If j=k then j is a coloop of A\1
if j=k then return recurse(B,br,k)+x*recurse(DD[2..r,1..bk],br,bk) fi:
# Any 1-entries j+1..k in the 1st row of D?
nc:=true: for jj from j+1 to k do nc:=nc and evalb(DD[1,jj]=0) od:
# If jth column is a coloop of A\1
if nc=true then
if j=1 then return recurse(B,br,k)+x*recurse(DD[2..r,2..k],br,bk)
else return recurse(B,br,k)+x*recurse(DD[2..r,[1..(j-1),(j+1)..k]],br,bk) fi:fi:
for ii from 2 to r do
if DD[ii,j]=1 then
DD[ii,j]:=0: for jj from j+1 to k do DD[ii,jj] := DD[ii,jj] - DD[1,jj] mod 2 od:fi:od:
if j=1 then return recurse(B,br,k)+recurse(DD[[2..r,1],2..k],r,bk):
else return recurse(B,br,k)+recurse(DD[[2..r,1],[1..(j-1),(j+1)..k]],r,bk): fi:
end proc:
### recursep ###
# Input: D, r, k, p where D is an r by k matrix (mod p)
# Output: the Tutte polynomial of A=[I_r|D] (so A has r+k columns)
#
recursep := proc(DD,r,k,p)
local i,ii,j,jj,ncl,nl,nc,B,br,bk:
# If D is a single row
if r = 1 then nl:=0: for j from 1 to k do if DD[1,j]=0 then nl := nl+1 fi:od:
return y^nl*(x+(y^(r+k-nl)-y)/(y-1)) fi:
# If D is a single column
if k = 1 then ncl:=0: for i from 1 to r do if DD[i,1]=0 then ncl := ncl+1 fi:od:
return x^ncl*(y+(x^(r+k-ncl)-x)/(x-1)) fi:
# Find the first column j with a 1-entry in row 1 of D
j:=1: while (j<=k and DD[1,j]=0) do j:=j+1: od:
br:= r-1:
bk:= k-1:
B:=DD[2..r,1..k]:
# If first column in A is a coloop
if j=k+1 then return x*recursep(B,br,k,p) fi:
# From here on, the first column in A is simple (i.e., there is a 1-entry in row 1)
# If j=k then j is a coloop of A\1
if j=k then return recursep(B,br,k,p)+x*recursep(DD[2..r,1..bk],br,bk,p) fi:
# Any 1-entries j+1..k in the 1st row of D?
nc:=true: for jj from j+1 to k do nc:=nc and evalb(DD[1,jj]=0) od:
# If jth column is a coloop of A\1
if nc=true then
if j=1 then return recursep(B,br,k,p)+x*recursep(DD[2..r,2..k],br,bk,p)
else return recursep(B,br,k,p)+x*recursep(DD[2..r,[1..(j-1),(j+1)..k]],br,bk,p) fi:fi:
for ii from 2 to r do
if DD[ii,j]<>0 then
for jj from 1 to j-1 do DD[ii,jj] := DD[ii,jj]*DD[1,j] mod p od:
for jj from j+1 to k do DD[ii,jj] := DD[ii,jj]*DD[1,j] - DD[1,jj]*DD[ii,j] mod p od:
DD[ii,j]:=0: fi: od:
if j=1 then return recursep(B,br,k,p)+recursep(DD[[2..r,1],2..k],r,bk,p):
else return recursep(B,br,k,p)+recursep(DD[[2..r,1],[1..(j-1),(j+1)..k]],r,bk,p): fi:
end proc:
### recurseGF4 ###
# Input: D, r, k where D is an r by k matrix over GF(4)
# Output: the Tutte polynomial of A=[I_r|D] (so A has r+k columns)
#
recurseGF4 := proc(DD,r,k)
local i,ii,j,jj,ncl,nl,nc,B,br,bk:
# If D is a single row
if r = 1 then nl:=0: for j from 1 to k do if DD[1,j]=0 then nl := nl+1 fi:od:
return y^nl*(x+(y^(r+k-nl)-y)/(y-1)) fi:
# If D is a single column
if k = 1 then ncl:=0: for i from 1 to r do if DD[i,1]=0 then ncl := ncl+1 fi:od:
return x^ncl*(y+(x^(r+k-ncl)-x)/(x-1)) fi:
# Find the first column j with a 1-entry in row 1 of D
j:=1: while (j<=k and DD[1,j]=0) do j:=j+1: od:
br:= r-1:
bk:= k-1:
B:=DD[2..r,1..k]:
# If first column in A is a coloop
if j=k+1 then return x*recurseGF4(B,br,k) fi:
# From here on, the first column in A is simple (i.e., there is a 1-entry in row 1)
# If j=k then j is a coloop of A\1
if j=k then return recurseGF4(B,br,k)+x*recurseGF4(DD[2..r,1..bk],br,bk) fi:
# Any 1-entries j+1..k in the 1st row of D?
nc:=true: for jj from j+1 to k do nc:=nc and evalb(DD[1,jj]=0) od:
# If jth column is a coloop of A\1
if nc=true then
if j=1 then return recurseGF4(B,br,k)+x*recurseGF4(DD[2..r,2..k],br,bk)
else return recurseGF4(B,br,k)+x*recurseGF4(DD[2..r,[1..(j-1),(j+1)..k]],br,bk) fi:fi:
for ii from 2 to r do
if DD[ii,j]<>0 then
for jj from 1 to j-1 do DD[ii,jj] := ti[DD[ii,jj],DD[1,j]] od:
for jj from j+1 to k do DD[ii,jj] := mi[ti[DD[ii,jj],DD[1,j]],ti[DD[1,jj],DD[ii,j]]] od:
DD[ii,j]:=0: fi: od:
if j=1 then return recurseGF4(B,br,k)+recurseGF4(DD[[2..r,1],2..k],r,bk):
else return recurseGF4(B,br,k)+recurseGF4(DD[[2..r,1],[1..(j-1),(j+1)..k]],r,bk): fi:
end proc:
### Tuttepoly ###
# Input: D, r, k where D is an r by k matrix D over GF(p) where p is prime or p=4
# Output: the Tutte polynomial of A=[I_r|D]
#
Tuttepoly := proc(D,r,k,p)
global mi,mit,ti,tit: local i,j,t: t:=time():
if p=2 then return simplify(recurse(D[1..r,1..k],r,k)),time()-t;
elif p=4 then
mit := [[0,1,2,3],[1,0,3,2],[2,3,0,1],[3,2,1,0]]:
tit := [[0,0,0,0],[0,1,2,3],[0,2,3,1],[0,3,1,2]]:
for i from 0 to 3 do for j from 0 to 3 do mi[i,j] := mit[i+1,j+1]: ti[i,j] := tit[i+1,j+1]: od:od:
return simplify(recurseGF4(D[1..r,1..k],r,k)),time()-t;
else return simplify(recursep(D[1..r,1..k],r,k,p)),time()-t; fi:
end proc:
### SDTuttepoly ###
# Input: D, k, p where D is a k by k invertible matrix D over GF(p) where p is prime or p=4 such that D=(D^T)^(-1)
# Output: the Tutte polynomial of A=[I_r|D] (the code generated by A is selfdual)
#
SDTuttepoly := proc(D,k,p)
global mi,mit,ti,tit: local T,i,j,t: t:=time():
if p=2 then T := simplify(recurse(D[2..k,1..k],k-1,k)):
elif p=4 then
mit := [[0,1,2,3],[1,0,3,2],[2,3,0,1],[3,2,1,0]]:
tit := [[0,0,0,0],[0,1,2,3],[0,2,3,1],[0,3,1,2]]:
for i from 0 to 3 do for j from 0 to 3 do mi[i,j] := mit[i+1,j+1]: ti[i,j] := tit[i+1,j+1]: od:od:
T := simplify(recurseGF4(D[2..k,1..k],k-1,k)):
else T := simplify(recursep(D[2..k,1..k],k-1,k,p)) fi:
return T+subs({x=y,y=x},T),time()-t;
end proc:
C:=Matrix(
[[1,1,1,0,1,1],
[1,0,1,1,0,1],
[1,1,0,1,1,0],
[1,0,1,0,1,1],
[1,0,0,1,0,1],
[1,0,0,0,1,0]]):Tuttepoly(C,6,6,2);A:=Matrix(12,12,
[[1,1,1,0,1,1,1,0,0,0,1,0],
[1,0,1,1,0,1,1,1,0,0,0,1],
[1,1,0,1,1,0,1,1,1,0,0,0],
[1,0,1,0,1,1,0,1,1,1,0,0],
[1,0,0,1,0,1,1,0,1,1,1,0],
[1,0,0,0,1,0,1,1,0,1,1,1],
[1,1,0,0,0,1,0,1,1,0,1,1],
[1,1,1,0,0,0,1,0,1,1,0,1],
[1,1,1,1,0,0,0,1,0,1,1,0],
[1,0,1,1,1,0,0,0,1,0,1,1],
[1,1,0,1,1,1,0,0,0,1,0,1],
[0,1,1,1,1,1,1,1,1,1,1,1]]):
SDTuttepoly(A,12,2);Tuttepoly(A,12,12,3);A:= Matrix(9,9,
[[1,2,1,1,3,1,1,2,3],
[2,2,0,3,0,1,3,2,2],
[2,1,0,2,2,2,3,0,3],
[0,2,1,0,2,2,2,3,3],
[3,1,1,2,2,1,1,3,1],
[3,2,2,2,0,1,2,0,3],
[0,3,2,2,2,0,1,2,3],
[2,3,1,0,3,0,2,2,2],
[2,1,1,3,1,1,2,1,3]]):Tuttepoly(A,9,9,4);