Indecomposability

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₁ be a linear (n₁,k₁)-code over GF(q) with generator matrix G₁ and let C₂ be a linear (n₂,k₂)-code over GF(q) with generator matrix G₂, then the code C with generator matrix

G:=(
G_1 0

0 G_2
)

is called the direct sum of the codes C₁ and C₂, and it will be denoted by C=C₁ ÅC₂. 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 bar (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 bar (R)_nkq. For the rest of this section let n³2.

Theorem The number R_nkq is equal to

S_nkq- å_a å_b Õ_{j=1 a_j¹0}^n-1( å_{c=(c₁,...,c_{a_j})Î N^a_j j³c₁³...³c_{a_j}³1, åc_i=b_j} U(j,a,c)),

where
U(j,a,c)=Õ_i=1^j Z( S_{n(i,a_j,c)}) | _{x_l=R_jiq}, n(i,a_j,c)=|{1£l£a_j | c_l=i} |,
and where the first sum is taken over the cycle types a=(a₁,...,a_n-1) of n, (which means that a_iÎN₀ and åia_i=n) such that åa_i£k, while the second sum is over the (n-1)-tuples b =(b₁,...,b_n-1)ÎN^n-1₀, for which a_i£b_i£i a_i, and åb_i=k. In the same way the bar (R)_nkq can be computed from the bar (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

å_i=1^ln_i=n, å_i=1^lk_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₁³n₂³...³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₁+n₂+...+n_l be such a partition with n_i³1 and 2£l£k. Then the cycle type of l is (a₁,a₂,...,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₁,...,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₁,...,k_l) and define

b_i:=å_{j:n_j=i}k_j,

then

å_i=1^n-1b_i=å_i=1^lk_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₁,...,b_n-1) and try to determine all sequences (k₁,...,k_l) which define non equivalent codes such that b_i=å_{j:n_j=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=å_i=1^a_jc_i, j³c₁³...³c_{a_j}³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,c_i,q} classes of indecomposable linear (j,c_i)-codes. In the case that all the c_i are distinct, this number is given by

Õ_i=1^a_jR_{j,c_i,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 n(i)=n(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 n(i) (j,i)-codes and the orbits of the symmetric group S_n(i) on the set of all mappings from n(i) into a set of R_jiq elements, where the action of S_n(i) is given by:

S_n(i)´R_jiqⁿ⁽ⁱ⁾ -> R_jiqⁿ⁽ⁱ⁾, (p,f) -> f o p^-1.

By Pólyas theorem [12] one has to compute the cycle index S_n(i) and each variable must be substituted by R_jiq. Doing this for all possible values of i we get

U(j,a,c)=Õ_i=1^jZ(S_n(i)) | _{x_l=R_jiq}.

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@kfunigraz.ac.at,
last changed: January 23, 2001

Indecomposability