Indecomposability
In order to minimize the number of orbits that must be enumerated
or represented, and following Slepian again, we can restrict
attention to indecomposable linear (n,k)-codes. Let
C_{1} be a linear (n_{1},k_{1})-code over
GF(q) with generator matrix Γ_{1} and let
C_{2} be a linear (n_{2},k_{2})-code over
GF(q) with generator matrix Γ_{2}, then the code C
with generator matrix
is called the direct sum of the codes C_{1} and
C_{2}, and it will be denoted by C=C_{1} ⊕
C_{2}. A code C is called decomposable, if and
only if it is equivalent to a code which is the direct sum of two
or more linear codes. Otherwise it is called
indecomposable.
In [13] Slepian proves that every
decomposable linear (n,k)-code is equivalent to a direct sum of
indecomposable codes, and that this decomposition is unique up to
equivalence and order of the summands. Slepian used a generating
function scheme for computing the numbers R_{nk2} and
R_{nk2}.
However after constructing these codes the authors realized that in
some situations this formula doesn't work correctly. For that
reason we are giving another formula to determine the numbers
R_{nkq} and R_{nkq}. For the rest
of this section let n≥ 2.
Theorem The number R_{nkq} is equal
to
S_{nkq}- ^{.}_{.} |
∑ a |
^{.}_{.} |
∑ b |
^{.}_{.} |
n-1
∏ j=1
a_{j} ≠ 0 |
( ^{.}_{.} |
∑ c=(c_{1},...,c_{aj})∈
ℕ^{aj}
j≥ c_{1}≥ ...≥
c_{aj}≥ 1, ∑c_{i}=b_{j} |
U(j,a,c)),^{.}_{.} |
where
U(j,a,c)=^{.}_{.} |
j
∏ i=1 |
Z(
S_{ν(i,aj,c)}) |
_{xℓ=Rjiq},
ν(i,a_{j},c)=|{1≤ l≤ a_{j} |
c_{l}=i}|,^{.}_{.} |
and where the first sum is taken over the cycle types
a=(a_{1},...,a_{n-1}) of n, (which means that
a_{i}∈ ℕ_{0} and ∑ia_{i}=n) such that ∑a_{i}≤ k, while the second sum is over
the (n-1)-tuples b =(b_{1},...,b_{n-1})∈
ℕ^{n-1}_{0}, for which a_{i}≤
b_{i}≤ i a_{i}, and ∑b_{i}=k. In the same way the R_{nkq} can be computed
from the S_{nkq}. The numerical
results show that for fixed q and n the sequence of R_{nkq}
is unimodal and symmetric. (It is easy to prove that this sequence
must be symmetric, but the proof of the unimodality is still open.)
Proof: In order to evaluate the values R_{nkq}
the number of all classes of decomposable linear (n,k)-codes must
be subtracted from S_{nkq}. In other words one has to find
all possibilities of decomposing a linear (n,k)-code into a direct
sum of indecomposable linear (n_{i},k_{i})-codes
such that
^{.}_{.} |
l
∑ i=1 |
n_{i}=n,
^{.}_{.} |
l
∑ i=1 |
k_{i}=k,
1≤ k_{i}≤ n_{i},
2≤ l≤ k. ^{.}_{.} |
According to Slepians theorem the
(n_{i},k_{i})-codes can be arranged such that
n_{1}≥ n_{2}≥ ...≥ n_{l} and in
the case that n_{i}=n_{i+1} the inequality
k_{i}≥ k_{i+1} holds. At first all partitions of
n into at least two parts and into at most k parts must be found.
Let n=n_{1}+n_{2}+...+n_{l} be such a
partition with n_{i}≥ 1 and 2≤ l≤ k. Then the
cycle type of λ is
(a_{1},a_{2},...,a_{n-1}), where
a_{i}=|{1≤ j≤ l | n_{j}=i}|. Two
decomposable codes which determine two different partitions of n
are not equivalent. In the second step to each partition of n one
has to find all sequences (k_{1},...,k_{l}) such
that (*) is fulfilled, and such that codes
belonging to different sequences are not equivalent. In order to do
this we start with such a sequence
(k_{1},...,k_{l}) and define
b_{i} := ^{.}_{.} |
∑ j:
n_{j}=i |
k_{j},^{.}_{.} |
then
^{.}_{.} |
n-1
∑ i=1 |
b_{i}=^{.}_{.} |
l
∑ i=1 |
k_{i}=k and
a_{i}≤ b_{i}≤ ia_{i}.^{.}_{.} |
Two decomposable codes which on the one hand belong to one
partition of n but on the other hand define two different vectors b
and b' are not in the same equivalence class. Now the other way
round we start with a sequence (b_{1},...,b_{n-1})
and try to determine all sequences
(k_{1},...,k_{l}) which define non equivalent codes
such that b_{i}=∑_{j:
nj=i}k_{j}. Again by Slepian's theorem we
must find all partitions of b_{j} ≠ 0 (this implies
a_{j} ≠ 0) into exacyly a_{j} parts of the form
b_{j}=^{.}_{.} |
a_{j}
∑ i=1 |
c_{i},
j≥ c_{1}≥ ...≥
c_{aj}≥ 1.^{.}_{.} |
In the last step U(j,a,c) must be evaluated. This is the the number
of classes of linear (j⋅ a_{j},b_{j})-codes,
which have a decomposition into a direct sum of indecomposable
(j,c_{i})-codes for 1≤ i≤ a_{j} to a given
partition c of b_{j} into exactly a_{j} parts. We
already know that there are R_{j,ci,q} classes
of indecomposable linear (j,c_{i})-codes. In the case that
all the c_{i} are distinct, this number is given by
^{.}_{.} |
a_{j}
∏ i=1 |
R_{j,ci,q}.^{.}_{.} |
Otherwise there exist i,l such that i<l and
c_{i}=c_{l}. Then
c_{i}=c_{i+1}=...=c_{l} and permuting the
corresponding summands in the direct sum may lead to equivalent
codes. For 1≤ i≤ j let ν(i)=ν(i,a_{j},c) be the
cardinality of {t | c_{t}=i}. Now there is a bijection
between the classes of codes, which are a direct sum of ν(i)
(j,i)-codes and the orbits of the symmetric group
S_{ν(i)} on the set of all mappings from ν(i) into a
set of R_{jiq} elements, where the action of
S_{ν(i)} is given by:
S_{ν(i)} ×
R_{jiq}^{ν(i)}→R_{jiq}^{ν(i)},
(π,f) ↦ f o π^{-1}.^{.}_{.} |
By Pólyas theorem [12] one has
to compute the cycle index S_{ν(i)} and each variable
must be substituted by R_{jiq}. Doing this for all possible
values of i we get
U(j,a,c)=^{.}_{.} |
j
∏ i=1 |
Z(S_{ν(i)})|_{xℓ=Rjiq}.^{.}_{.} |
Using the computer algebra system SYMMETRICA, among many other
ones the tables of numbers of indecomposable codes which are shown
below were computed.
harald.fripertinger "at" uni-graz.at, May 10,
2016