arXiv:1711.10671v1 [] 29 Nov 2017

Fq [G]-modules and G-invariant codes
E. J. Garcia-Claro∗and H. Tapia-Recillas
Department of Mathematics
Universidad Autónoma Metropolitana-Iztapalapa, Mexico city, Mexico
eliasjaviergarcia@gmail.com
htr@xanum.uam.mx

November 30, 2017

Abstract
If Fq is a finite field and G is a subgroup of the linear automorphisms of Fnq , a solution to the problem of finding all the G-invariant
linear codes C of Fnq (i.e. such that g(C) = C for all g ∈ G) is offered. This will be referred as the invariance problem. When n = |G|t,
we determine conditions for the existance of an isomorphism of Fq [G]modules between Fnq and Fq [G] × · · · × Fq [G] (t-times), that preserves
the Hamming weight, this reduce the invariance problem, to determine
the Fq [G]-submodules of Fq [G] × · · · × Fq [G] (t-times). The concept
of Gaussian binomial coefficient for semisimple Fq [G]-modules which
is useful for counting G-invariant codes is introduced, and a systematic way to compute all the G-invariant linear codes C ≤ Fnq , when
(|G|, q) = 1 is provided.

Keywords. G-invariant codes, semisimple group algebras, Gaussian
binomial coefficient, semisimple Fq [G]-modules.

1

Introduction

Throughout this work Fq denotes a finite field with q elements, and Fq [G]
denotes the group algebra of a finite group G over Fq .
One of the most well-known and useful classes of linear codes is the one of
∗

Research partially supported by CONACyT (Consejo Nacional de Ciencia y Tecnología, Mexico) Grant 401846.

1

cyclic codes. Cyclic codes and some of their generalizations, such as constacyclic codes and quasi-cyclic codes, respond to the question of finding the
invariant codes under certain automorphisms of Fnq . For instance, cyclic
codes are the invariant codes under the cyclic shift σ(a0 , a1 , ..., an−1 ) :=
(an−1 , a0 , ..., an−2 ); quasi-cyclic codes are the invariant codes under σ k ,
where k is a divisor of n; and consta-cyclic codes are those which are invariant under the mapping ρ(a0 , a1 , ..., an−1 ) := (can−1 , a0 , ..., an−2 ) with
c ∈ F∗q . All of these families of codes have in common that are invariant
under the groups hσi, hσ k i, and hρi respectively.
In general, given a subgroup G of the linear automorphisms of Fnq , one
might ask which are the linear codes C ≤ Fnq such that g(C) = C for all
g ∈ G? Offering an answer to this question is the first aim of this work.
In the previous situation, Fnq becomes a Fq [G]-module with the operation
P



P

n
g∈G λg g(v) for all v ∈ Fq , so the G-invariant codes of
g∈G λg g · v :=
Fnq are precisely its Fq [G]-submodules.From here on, every modules will be
consider a left module.
When a linear code C ≤ Fnq is invariant under certain subgroup G of the
Fq -linear automorphism group of Fnq , AutFq (Fnq ), then {g ↾C | g ∈ G} ≤
AutFq (C), so the invariance problem is related with finding codes which
have a non-trivial pemutation (monomial) group automorphism. Some authors have worked in relation to this question. For example, in [6] Kumar and Sundar studied codes closed under an arbitrary abelian group of
permutations. In [5] Knapp and Schmidt consider [n, k]-codes C ≤ Fnq
such that "the permutation part of their monomial automorphism" given
by M AutP r (C) := {f ∈ Sn | df ∈ M Aut(C)} (where d is represented by a
diagonal invertible matrix on the canonical basis, and M Aut(C) the monomial automorphism group of C) contains An , Sn , or the Mathieu group.
Their work was in some sense a classification of these codes. In contrast,
G-invariant codes are not classified here, the main result of our work consists
of a method to compute G-invariant codes. The work done in this paper applies for arbitrary groups without concern if they are permutation groups1 ,
abelian, or even on their size. However most of the time |G| and q will be
required to be relative primes.
In this work different questions related to the invariance problem are addressed. It is organized as follows. In section 2, some preliminaries about
semisimple modules are given. Then, in section 3, we address the question
1

Actually these groups might have elements that do not preserve the Hamming distance, but for some applications of the results to coding theory, these can be regarded as
groups of permutations or monomial transformations.

2

of determining when Fnq , with structure of Fq [G]-module as above, is isomorphic, with an isomorphism that preserves the Hamming weight, to a direct
sum of copies of Fq [G]. A clear particular answer to this but not unique
occurs when G is the group generated by the cyclic shift of Fnq . Throughout
sections 4 and 5, we introduce and study the concepts of Unique decomposition, multiplicity-free, and Gaussian binomial coefficient for finitely generated semisimple Fq [G]-modules, which are useful to study G-invariant codes.
In section 6, an algorithm to efficiently compute all the possible sums of a
collection of simple isomorphic Fq [G]-modules of a given finitely generated
Fq [G]-module is presented, and this algorithm is used in section 7 to provide
a method to determine all the G-invariant codes of Fnq when (|G|, q) = 1.
Finally, in sections 8 and 9, we propose a theoretically possible solution to
solve the invariance problem when our method could not be applied and
give some examples illustrating the main results.

2

Preliminaries

Throughout this work all rings will have unity, every algebra will be considered a finite dimensional algebra over a field, and each module will be
a left module, unless stated otherwise. We will also work with semisimple
modules, except in the next section where the main result is independent of
assuming semisimplicity. For reviewing properties about semisimple modules and rings see [2] section 3B and [1] section 25.
Let A be a ring. An A-module M is called semisimple if for any Asubmodule N of M there exists a direct complement, i.e., there exists a
submodule U of M such that M = N ⊕ U .
A ring A is called semisimple, if every A-module is semisimple; two elements x, y ∈ A are called orthogonal if xy = yx = 0.
Let A be a ring, an element e ∈ A is called idempotent if e2 = e, and it
is primitive if e = f + g where f, g ∈ A are orthogonal idempotents, then
f = 0 or g = 0.
Let M and N be A-modules. If there exists an A-module U such that
M∼
= N ⊕ U , it is said that N divides M , and denoted by N | M .
Let M be a semisimple finitely generated A-module and S a simple A-module
(with no proper submodules different from 0), such that S | M . The multiplicity n of S in M is defined as the greatest natural number such that
nS = S
⊕ ·{z
· · ⊕ S} | M .
|
n times

Let M be a finitely generated A-module over a semisimple ring. If {Af1 , ...,

3

Afr } is a collection of minimal ideals of A such that Afj | M for all
j ∈ {1, ..., r}, and for any simple A-submodule N of M there exists a unique
j ∈ {1, ..., r} such that N ∼
= Afj , then it will be said to be {Af1 , ..., Afr } is
a basic set of ideals for M . A collection of idempotents {e1 , ..., er } ⊂ A
such that {Ae1 , ..., Aer } is a basic set of ideals for M will be called
a basic set of idempotents for M . If N is a simple A-submodule of
M , the homogenous component H of M of type N is the A-module
P
U ≤M ∧U ∼
=N U . Let e ∈ A be a primitive idempotent, and H a homogeneous component of M . If Ae divides H, then it will be said that e (Ae) is
associated to H, or H is associated to e (Ae).
The following lemma is just a slight modification of [9] Theorem 4.3, part 1.
Lemma 2.1 Let A be a semisimple ring, e ∈ A a primitive idempotent,
I = Ae the minimal ideal (not containing proper ideals different from 0)
generated by e, and M an A-module. If ηe : HomA (Ae, M ) 7→ eM is given
by ηe (ϕ) = ϕ(e), then ηe is an isomorphism of abelian groups. Moreover, if
A is a k-algebra, ηe is an isomorphism of k-spaces, and if e is central ηe , is
an isomorphism of A-modules.
Proof. It is clear that ηe is additive and injective. If x ∈ eM , fx :
Ae → M given by ae 7→ (ae)x defines a morphism of A-modules such that
ηe (fx ) = ex = x, so η is surjective. Moreover, if A is a k-algebra, then eM
is a k-subspace of M ; if e is central, then eM is an A-submodule of M . In
both cases ηe preserves the structure of eM .
Lemma 2.2 Let A be a semisimple k-algebra, e, f ∈ A primitive idempotents, with f 6= 0 6= e. Then eAf 6= 0 if and only if the ideals Ae and Af
are isomorphic A-modules.
Proof. It follows from taking M = Af in lemma 2.1 and applying
Schur’s lemma.

3

Isomorphism of Fnq with Fq [G] × · · · × Fq [G]

Let Cn denote the cyclic group of order n generated by the cyclic shift σ
· · ◦ σ}(a0 , a1 , ..., an−1 )
which acts naturally on Fnq as σ i ·(a0 , a1 , ..., an−1 ) = |σ ◦ ·{z
i times

for all i = 1, ..., n, endowing Fnq with structure of Fq [Cn ]-module. Another
natural Fq [Cn ]-module is Fq [Cn ] itself. A classic way of determining the
cyclic linear codes of Fnq is by using the isomorphism of Fq [Cn ]-modules,
φ : Fnq → Fq [Cn ] given by, (a0 , a1 , ..., an−1 ) 7→ a0 + a1 σ + ... + an−1 σ n−1 , this
4

provides a bijection between the ideals of the group algebra Fq [Cn ] and the
invariant codes of Fnq under the cyclic shift σ. In addition, this φ preserves
the Hamming weight, i. e., for all v ∈ Fnq , wt(v) = wt′ (φ(v)) (the Hamming
weight in a finite group algebra Fq [G] is given as the cardinality of the support of an element respect to the basis G). Let us take that situation to a
more general context. If G ≤ AutFq (Fnq ) and n = t|G| one may ask, whether
there exists an isomorphism of Fq [G]-modules between Fnq and ⊕ti=1 Fq [G]
preserving Hamming weight. The following result will help to answer this
question.
Let G be a finite group. If M is an Fq [G]-module, there is a representation induced by left multiplication by elements of G in M , given by
ρ : G → AutFq (M ), where g 7→ ρ(g), and ρ(g)(v) = gv for all v ∈ M .
If R = ⊕ti=1 Fq [G] = Fq [G] × · · · × Fq [G] (t-times) is an external direct sum
of Fq [G] (i.e. with pointwise addition and pointwise left multiplication by
elements of Fq [G]), the Hamming weight is defined on R as wt′′ ((i1 , ..., it )) =
Pt
′
′
j=1 wt (ij ) for all (i1 , ..., it ) ∈ R where wt (ij ) is the Hamming weight of
ij in Fq [G].
Theorem 3.1 Let G ≤ AutFq (Fnq ) with n = |G| · t. Let πj : R → Fq [G] be
given by (i1 , ..., it ) 7→ ij for all j = 1, ..., t, where R = Fq [G] × · · · × Fq [G]
(t-times); µ be the canonical basis of Fnq , and η = ∪tj=1 Gj where Gj =
{v ∈ R | πj (v) ∈ G and πi (v) = 0, f or i 6= j}. Let ρ : G → AutFq (Fnq ),
ρ′ : G → AutFq (R) be the representations induced by the Fq [G]-modules
structure of Fnq (given by evaluation) and R (given by left multiplication)
respectively. Let g ∈ G, [ρ(g)]µ be the matrix of ρ(g) with respect to the
basis µ, and [ρ′ (g)]η the matrix of ρ′ (g) with respect to the basis η. Let
S = {s1 , ..., sk } be a generating set for G, and M ≤ GL(n, q) the group
of monomial matrices. Then, there is a bijection φ from H := {A ∈ M |
[ρ(si )]µ = A−1 [ρ′ (si )]η A, i = 1, ..., k} to the set L of the Fq [G]-isomorphisms
from Fnq to R that preserve the Hamming weight, given by, A 7→ fA with
[fA (v)]η := A[v]µ for all v ∈ Fnq .
Proof. Let wt and wt′′ denote the Hamming weight on Fnq and R reP
spectively. By definition wt′′ (r) := tj=1 wt′ (πj (r)) where wt′ is the usual
Hamming weight on Fq [G]. Let h : L → H be given by f 7→η [f ]µ , for all
f ∈ L.
First, we show that φ has, in fact, L as its codomain. Let A ∈ H, then
A[ρ(si )]µ = [ρ′ (si )]η A for all i = 1, ..., k. Let f : Fnq → R be the linear transformation given by [f (v)]η := A[v]µ , then η [f ]µ = A, so f (ρ(si )) = ρ′ (si )(f )
for all i = 1, ..., k, and φ(A) = f is an isomorphism of Fq [G]-modules. Now
5

we observe that f preserves the Hamming weight. For v ∈ Fnq , [f (v)]η =
A[v]µ , thus wt(v) = wt(A[v]µ ) because A is a monomial matrix, hence
P
P
wt([f (v)]η ) = tj=1 wt([πj (f (v))]G ) = tj=1 wt′ (πj (f (v))) = wt′′ (f (v)) by
definition of wt′′ , thus wt(v) = wt′′ (f (v)).
Next, it is shown that H is, in fact, the codomain of h. Let f ∈ L and g ∈ G,
then f (ρ(g)) = ρ′ (g)(f ), thus η [f ◦ ρ(g)]µ =η [ρ′ (g) ◦ f ]µ . Let A :=η [f ]µ ,
then [ρ(g)]µ = A−1 [ρ′ (g)]η A. It remains to show that A is a monomial matrix. Let ei be the i-th canonical vector of µ, thenwt(Aei ) = wt(A[ei ]µ ) =
wt([f (ei )]η ) = wt′′ (f (ei )) = wt(ei ) = 1 where the penultimate equality follows from the fact that f preserves the Hamming weight, so Aei = ci eji with
ji ∈ {1, ..., n}, hence the i-th column of A is ci eji . Furthermore, A is invertible, so if k, l ∈ {1, ..., n} and k 6= l, then jk 6= jl , thus Aei = ci eτ (i) where
τ ∈ Sn . As φ and g are clearly mutually inverse the proof is complete.
Example 3.2 Let α be the automorphism of F43 given by α(a0 , a1 , a2 , a3 ) :=
(a1 , a0 , a3 , a2 ), and G := hαi = {1, α}. G has order 2, thus one may
ask if F43 and R = F3 [G] × F3 [G] are isomorphic as F3 [G]-modules with
an isomorphism that preserves Hamming weight. Let ρ : G → AutF3 (F43 )
be the inclusion, and ρ′ : G → AutF3 (R) given by α 7→ lα where lα is
the left multiplication by α. Let µ denote the canonical basis of F43 and
η = {(1, 0), (α, 0), (0, 1), (0, α)}. If we consider the monomial matrix


1
0

C := 
0
0

0
0
0
1

0
1
0
0



0
0


1
0

then C[ρ(α)]µ = [ρ′ (α)]η C. Hence, according to theorem 3.1, f : F43 → R
given by [f (v)]η := C[v]µ is an isomorphism of F3 [G]-modules that preserves
the Hamming weight. Consequently, C ≤ F43 is G-invariant if and only if
f (C) is a F3 [G]-submodule (2-quasi-cyclic code) of R which is isomorphic
to C as F3 [G]-module and as metric space, i.e., the G-invariant codes in F43
are equivalent to the 2-quasi-cyclic codes.

4

Unique decomposition and multiplicity-free for
semisimple modules

A finitely generated A-module M (over a semisimple ring A), by KrullSchmidt Theorem, can be expressed as a direct sum of simple A-submodules,
and this decomposition is unique up to isomorphism and permutation of its
6

summands. However, this is not unique in the sense that there could be two
decompositions of M having different summands. When this do not occur
it will be said that M has unique decomposition.
Theorem 4.1 Let M be a semisimple finitely generated A-module. Then,
the following conditions are equivalent:
1. M = ⊕N ≤M,
2. V = ⊕N ≤V,

N simple N .

N simple N ,

for all V ≤ M .

3. for all V ≤ M , there exists a unique U ≤ M such that M = V ⊕ U .
4. M has unique decomposition.
5. if M = ⊕rj=1 Nj , with Nj simple for all j = 1, ..., r, then M has exactly
2r A-submodules.
Proof.
P
(1) implies (2): if there exists V ≤ M such that V = N ≤V, N simple N 6=
⊕
N , then exists T ≤ V simple, such that T is subset of
P
PN ≤V, N simple
N ≤M, N 6=T simple N , contradicting
N ≤V, N 6=T simple N which is subset of
(1) .
(2) implies (3): if there exists an A-submodule T of M without a unique
direct complement, then M = T ⊕ U0 = T ⊕ U1 for some U0 , U1 ≤ M
and U0 6= U1 , so there exists a simple A-submodule S of U0 that is not
contained in U1 . For that reason, if ⊕i Ti = T ⊕ U1 is a decomposition of
T ⊕ U1 into simple modules, then S does not appear as a summand in that
decomposition, implying that T ⊕ U1 = M is not a direct sum of all its
simple A-submodules, which contradicts that every submodule of M is a
direct sum of all its simple A-submodules.
(3) implies (4): suppose that every A-submodule of M has a unique
direct complement in M , and proceed by induction on the length n of M . If
n = 2, and M has not unique decomposition, then M = M1 ⊕ M2 = N1 ⊕ N2
where Mi , Ni are simple A submodules of M for all i = 1, 2. Without loss
of generality, M1 6= N1 , M1 6= N2 , and M1 ∼
= N2 , then M = N1 ⊕ M1 , but
the direct complements are unique, so M1 = N2 , which is a contradiction;
hence M has unique decomposition. Let us assume that the statement is
true for n = k where k is a positive integer. Let n = k + 1, if J ≤ M
is a maximal A-submodule, then the length of J is k, so by the inductive
hypothesis, J has unique decomposition J = ⊕ki=1 Ji . As direct complements
in M are unique, there exists a unique simple A-submodule K ≤ M such
7

that M = J ⊕ K. In case M would has not unique decomposition, then
would exist a collection {N1 , ..., Nk+1 } of simple A-submodules of M such
k
that M = ⊕k+1
i=1 Ni = J ⊕ K = ⊕i=1 Ji ⊕ K, and there exists t ∈ {1, ..., k + 1}
such that Nt 6= Ji for all i = 1, ..., k and Nt 6= K. On the other hand, Nt * J,
otherwise Nt is part of a decomposition into simple A-submodules of J, so J
has at least two decompositions, contradicting the unique decomposition of
J, thus Nt ⊕ J = M , but J has as unique complement K, therefore Nt = K
which is a contradiction. Hence M must has unique decomposition.
(4) implies (5): if M = ⊕rj=1 Nj , with Nj simple for all j = 1, ..., r, it is
clear that M has at least 2r submodules (all the possible sums of its simple
direct sumands). Let us suppose that M has more than 2r submodules,
then there exists V ≤ M such that V is not a sum of the Nj -th. Thus there
exists S ≤ V simple with S 6= Nj for all j ∈ {1, ..., r}, hence M is not a
direct sum of all its simple A-submodules.
(5) implies (1): suppose that M = ⊕rj=1 Nj with Nj simple A-submodule
of M for all j = 1, ..., r, then M must has exactly 2r submodules. If M is
not the direct sum of all its simple A-submodules, then {Ni }ri=1 is not the
collection of all the simple A-submodules of M . Therefore, there exists a
simple A-submodule S of M such that S ∈
/ {Ni }ri=1 , but this implies that
r
M has more than 2 submodules, which is a contradiction.
Definition 4.2 If M is a semisimple A-module such that any two distinct
simple A-submodules of M are not isomorphic, then it will be said that M
is multiplicity-free.
It follows from the previous definition that two submodules of a multiplicityfree semisimple module are isomorphic if and only if they are equal.
Lemma 4.3 Let M be a semisimple finitely generated A-module. If M is
multiplicity-free, then M has unique decomposition.
Proof. Let M = ⊕ti=1 Ni = ⊕ti=1 Ui be two decompositions of M as
direct sum of simple A-submodules. Then by the uniqueness up to isomorphism of the decomposition, there exists a permutation γ of {1, ..., t} such
that Ni ∼
= Uγ(i) for all i ∈ {1, ..., t}, but M is multiplicity-free, so Ni = Uγ(i)
for all i ∈ {1, ..., t}.
Lemma 4.4 Let A be a semisimple ring, and e, f ∈ A central primitive
idempotents (i.e. primitive idempotents that belong to the center of A). If
Ae ∼
= Af , then e = f .
8

Proof. If Ae ∼
= Af , then 0 6= HomA (Ae, Af ) ∼
= eAf by lemma 2.1, so
as e, f are central elements, 0 = eAf = Aef = Af e. Thus 0 6= ef = f e ∈
Af ∩ Ae, hence Ae = Af . However, Ae (respectively Af ) is a ring with
unity e (respectively f ), therefore e = f .
Corollary 4.5 If A is a semisimple commutative ring, then A is a multiplicityfree A-module.
Proof. It follows from the fact that every primitive idempotent is
central in A and lemma 4.4.
Lemma 4.6 Let A be a semisimple ring, I ≤ A be a minimal ideal such
that I has multiplicity 1 in A, and n ∈ Z+ . If N 6= 0 is a cyclic A-submodule
of nI, then N is simple and N ∼
= I.
Proof. Let N 6= 0 be a cyclic A-submodule of nI. Then there exists
0 6= x ∈ nI such that N = Ax, thus N is isomorphic to A/ann(x) (where
ann(x) is the annihilator of x), and this is isomorphic to a direct complement
S of ann(x) in A, which there exists because A is semisimple, so N ∼
= S. On
the other hand, the unique simple A-submodule (up to isomorphism) that
divides nI is I, thus the unique simple A-submodule (up to isomorphism)
that divides N is I. Consequently, there exists k ∈ Z+ with k ≤ n such
∼N ∼
that kI =
= S ≤ A and as the multiplicity of I in A is 1, then k = 1, so
∼
I = N.
Lemma 4.7 Let A, I be as in lemma 4.6, and 1 < n ∈ Z. Then nI has not
unique decomposition.
Proof. Let πj be the j-th proyection of I| ⊕ ·{z
· · ⊕ I} = nI, for all j =
n times

1, ..., n, and 0 6= x ∈ nI such that x is not in Lj = {v ∈ nI | πi (v) =
0, f or i 6= j} for all j = 1, ..., n (such an element x there exists because
n > 1). The cyclic A-module Ax is simple isomorphic to I (by lemma 4.6).
As x is not in Lj for all j = 1, ..., n, Ax 6= Lj for all j = 1, ..., n, meaning that
Ax is a simple A-submodule of nI = ⊕ni Lj that does not appear as a direct
sumand, by theorem 4.1 (part 1) nI does not have unique decomposition.
Corollary 4.8 Let A be a semisimple commutative ring, with a minimal
ideal I ≤ A, and 1 < n ∈ Z. Then nI has not unique decomposition.
Proof. It follows from corollary 4.5 and lemma 4.7 .
9

Theorem 4.9 Let A be a commutative semisimple ring, and M a finitely
generated A-module. Then the following statements are equivalent:
1. M is multiplicity-free.
2. M has unique decomposition.
3. M is isomorphic to an ideal of A.
Proof.
(1) implies (2): follows from lemma 4.3.
(2) implies (3): suppose that M has unique decomposition and is not
isomorphic to an ideal of A, i.e., there exists I ≤ A minimal ideal such that
I divides M with multiplicity n > 1. Therefore, there exists an A-module
U such that M ∼
= nI ⊕ U . On the other hand, by lemma 4.8, nI has not
unique decomposition, thus by theorem 4.1, part 2, M neither, which is a
contradiction.
(3) implies (1): let M be isomorphic to an ideal of A. As A is multiplicityfree (by corollary 4.5), every ideal of A is multiplicity-free as is M.
Theorem 4.9 shows that finitely generated modules over a semisimple
commutative ring, having unique decomposition, are not too large, in the
sense that these must be embedded in their base ring. In that case any ideal
of the algebra has unique decomposition, but in general, this is not true. For
example, the ideals of a semisimple non-commutative group algebra might
not have unique decomposition, as can be seen in the following example.
Example 4.10 Let S3 = ha, b | a3 = b2 = 1, bab = a2 i = {1, a, a2 , b, ba, ba2 }
and A = F5 [S3 ]. Then {e1 = 1+a+a2 +b+ba+ba2 , e2 = 1+a+a2 +4b+4ba+
4ba2 , e3 = 2+3a2 +2b+3ba2 , e4 = 2+3a+3b+2ba2 } is a complete set of primitive orthogonal idempotents of A 2 . In addition, by lemma 2.2, Ae1 ≇ Ae2
because e1 Ae2 = e1 F5 e2 = F5 e1 e2 = 0, and Ae3 ∼
= Ae4 because y = 1 + 2a + b
is a unity in A such that ye3 y −1 = e4 . Therefore, H1 = Ae1 , H2 = Ae2
and H3 = Ae3 ⊕ Ae4 are the homogeneous components of A. Furthermore,
(1 + a) is a unity in A, so w := (1 + a)e3 (1 + a)−1 = 2 + 3a2 + 3ba + 2ba2
is a primitive idempotent. On the other hand, we3 6= w and we4 6= w, thus
Aw is a simple A-submodule of H3 that is different from Ae3 , Ae4 ; hence by
theorem 4.1 part 1, H3 has not unique decomposition, and by theorem 4.1
part 2, neither does A.
2

This idempotents were computed using Theorem 3.3 [3] and doing some computations
in Sage.

10

5

The Gaussian binomial coefficient for semisimple Fq [G]-modules

In this section a Gaussian binomial coefficient for semisimple Fq [G]-modules
is introduced and some of its properties are studied. This coefficient will be
useful for counting G-invariant codes.
Definition 5.1 (Gaussian binomial Coefficient) Let N and M be finitely
generated semisimple Fq [G]-modules. The Gaussian binomial coefficient of
M in N is defined as
M
N

!

:= |{U ≤ M | U ∼
= N }|.
q

Lemma 5.2 Let A = Fq [G], (|G|, q) = 1, M , N and T be finitely generated
A-modules, and I ≤ A a minimal ideal such that I | M . Then the following
statements hold:
1.

M
N q

6= 0 if and only if N | M .

2. If N | M , then

N
I q

≤

M
I q.

3. If U is an A-module such that
4. If HomA (T, N ) = 0, then
5. If HomA (T, N ) = 0, then
Proof.

kI 
I q

M ⊕N 
T
q

M 
T ⊕N q

≤

=

=

U
I q,

then kI ֒→ U .

M
T q.

M M
T q N q.

1. N | M if and only if N is embedded into M , if and only if
2. It is clear.

M
N

6= 0.

3. If X
is a set of simple A-modules of U isomorphic to I such that
P
kI 
≤
|X|, then x∈X x ∼
= rI for some r ∈ Z+ , thus kI
I q ≤ |X| ≤
I q
rI 
I q,

implying that k ≤ r, so kI ֒→ rI ֒→ U .

4. HomA (T, N ) = 0 if and only if T and N have no simple common
direct sum
divisors. Let M ′ ∼
= N such thatthe internal
= M and N ′ ∼
M ′
M ⊕N
′
′
M ⊕ N = M ⊕ N . As M | M ⊕ N then M
=
≤
=
T q
T q
T
q
11

M ′ ⊕N ′ 
.
T
q

If the equality does not hold, would exist L ≤ M ′ ⊕ N ′
with L ∼
= T and L  M ′ , thus exists a simple A-module S ≤ L such
that S ∩ M ′ = 0. Hence S | N , however S | T which contradicts
HomA (T, N ) = 0.
5. Consider the function f : {L ≤ M | L ∼
= T ⊕ N } −→ {U ≤ M | U ∼
=
∼
T } × {Z ≤ M | Z = N } given by f (L) = (L1 , L2 ) where L = L1 ⊕ L2 ,
L1 ∼
= T , and L2 ∼
= N . f is well defined, otherwise there exists L in
its domain such that L = L1 ⊕ L2 = X1 ⊕ X2 where L1 ∼
= X1 ∼
= T,
L2 ∼
= X2 ∼
= N , and L1 6= X1 or L2 6= X2 . Without loss of generality,
L1 6= X1 and there exists a simple A-submodule S of L1 that is not
contained in X1 , then its multiplicity in S ⊕ X1 ≤ L is greater than
its multiplicity in T . However, this contradicts HomA (T, N ) = 0. If
HomA (T, N ) = 0, thenf is invertible with inverse f −1 (A, B) = A⊕B,
M
M
therefore T M
⊕N q = T q N q .

Corollary 5.3 Let A = Fq [G] and (|G|, q) = 1. Let M ∼
= ⊕tj=1 nj Ij be an
A-module, where Ij ≤ A is a minimal ideal and nj its multiplicity in M for
all j = 1, ..., t. Let N ≤ M , if N ∼
= ⊕l∈J kl Il where J ⊆ {1, ..., t}, then
M
N

!

Y

=

l∈J

q

nl Il
kl Il

!

.
q

Proof. Let J ⊆ {1, ..., t} be such that N ∼
= ⊕l∈J kl Il . As N ≤ M ,
kl ≤ nl for all j ∈ J, thus
M
N

!

=
q

=

⊕tj=1 nj Ij
⊕l∈J kl Il
Y

l∈J

=

Y

l∈J

!

q
!
t
⊕j=1 nj Ij

kl Il

nl Il
kl Il

!

by lemma 5.2 part 5
q

by lemma 5.2 part 4.

q

Definition 5.4 Let A be an arbitrary ring, M a finitely generated semisimple A-module and let SS(M ) be defined as the collection of all simple Asubmodules of M .
P
If X ⊆ SS(M ) is such that x∈X x = M , then it will be said that X generates M or that X is a generating set by simple A-submodules of M .
12

P

If Y ⊆ SS(M ) is such that y∈Y y = ⊕y∈Y y, then it will be said that Y is
independent, or Y is an independent set of simple A-submodules of M .
If X ⊆ SS(M ) is independent and generates M , it will be said that X is a
basis for M or, X is a basis by simple A-submodules of M .
Lemma 5.5 Let A be an arbitrary ring, and M a finitely generated semisimple A-module.
1. If X ⊆ SS(M ) and X generates M , then X contains a basis.
2. If X ⊆ SS(M ), X is independent and X has the cardinality of a basis
for M , then X is a basis.
Proof.
P

P

1. Let X ⊆ SS(M ) be such that x∈X x = M . If x∈X x 6= ⊕x∈X x
(i.e. X is not independent), there exists x0 ∈ X such that x0 ⊆
P
x∈X−{x0 } x = M . If X0 = X − {x0 } is independent, the proof
concludes, otherwise the same reasoning can be applied to X0 and
this process can be repeated until obtaining a subset of X that is
independent and generates M .
P

2. Let X, Y ⊆ SS(M ) be such that x∈X x = ⊕x∈X x, M = ⊕y∈Y y
and |X| = |Y |. As ⊕x∈X x ⊂ M = ⊕y∈Y y, ⊕x∈X x ∼
= ⊕y∈J y with
J ⊆ Y , so by Krull-Schmidt theorem |J| = |X| = |Y |, implying that
⊕x∈X x = ⊕y∈Y y = M .
Lemma 5.6 Let A = Fq [G] and (|G|, q) = 1. If I ≤ A is a minimal ideal,
and k, n ∈ Z+ with
k ≤ n, then i h
h 2 ≤ ih
i
nI
nI
nI
−(2I
−1
−((k−1)I
··· (nI
(
)
)
(
)
)
(
)
)

I
I
I
I
I
I
q
q
q
q
q
q
nI
ih
h
i h
i.
kI q = kI
( I )q (kII )q −1 (kII )q −(2II )q ··· (kII )q −((k−1)I
)
I
q
Proof. Let X = {N ≤ nI | N ∼
= kI}, and Y = {A ⊆ SS(nI) |
|A| = k ∧ A independent}. If R is the relation on Y given by aRb if
and only if a generates the same A-module as b, for all a, b ∈ Y , then
R is an equivalence relation. If Y /R is the quotient set determined by
P
R, then the function f : Y /R −→ X given by [x] 7→ m∈[x] m is a bi
jection, so |Y /R| = |X| = nI
kI q . On the other hand, every equivalence
class on Y /R has the same cardinality which is the number of basis by
|Y |
for some x0 ∈ Y , hence
simple A-submodules of kI. Thus |Y /R| = |[x
0 ]|
13

nI 
kI q

=

# of l. i. sets of simple A-submodules of nI having cardinality k
.
# of basis by simple A-submodules of kI

For building a independent set of simple A-submodules of nI having
cardinality k (i.e. an element of Y ), we should start by taking a simple Amodule S1 , and for that, we have nI
I q possible choices. For taking another
simple A-module
S2 such
that the collection {S1 , S2 } remains independent,
h 
i
nI
I
we have I q − I q possible choices. To take a simple A-module S3 such
h

 i



2I
that the collection {S1 , S2 , S3 } remains independent, we have nI
I q− I q
possible elections, and, in general, to chose a simple A-module Sk such that
the
h collection L i= {S1 , S2 , S3 , ..., Sk−1 , Sk } remains independent, we have
(k−1)I
nI
possibilities. Therefore, at the end of this process, we
I q−
I
q
will construct a independent set of simple A-submodules of nI having size
k. We did the choices of the A-modules Si without worrying about the
order, and depending
on that,
, so we have
h
ih the same
i hset L can be obtained
i
nI
I
nI
2I
nI
(k−1)I
nI
−
−
−
···
( I )q ( I )q (I )q ( I )q ( I )q
( I )q ( I )q

that |Y | =
, where II q = 1.
k!
For building a basis by simple A-submodules of kI the same reasoning as
before could be used, taking into account that a independent set of simple
A-submodule of kI that has cardinality k is, in fact, a basis for kI (by lemma
5.5 part 2), thus we obtain

|[x0 ]| =

kI 
I q

h

kI 
I q

−

I
I q

ih

kI 
I q

−
k!

2I 
I q

i

···

h

kI 
I q

−

(k−1)I 
I
q

i

,

concluding the proof.
Lemma 5.7 Let A = Fq [G] be a semisimple group algebra, I ≤ A a minimal
ideal such that its multiplicity in A is 1, and n ∈ Z+ . If U ∗ := U − {0} for
all U ≤ nI, then X := {U ∗ | U ≤ nI ∧ U ∼
= I} is a partition of (nI)∗ .
Proof. If n = 1, the assertion is true. Otherwise, if V, W ∈ X and
W 6= V , then exit U and T different simple A-submodules of nI such that
V = U ∗ and W = T ∗ , as U ∩ T = {0}, ∅ = U ∗ ∩ T ∗ = V ∩ W . If x ∈ (nI)∗ ,
the cyclic module Ax is contained in nI, so Ax is simple isomorphic to I
(by lemma 4.6), and x ∈ Ax − {0} ∈ X.
Corollary 5.8 Let A, I, and n be as in lemma 5.7. If dimFq (I) = k, then
nI 
I q

=

q nk −1
.
q k −1

14

Proof. Let X be as in lemma 5.7, then (nI)∗ = ⊔V ∈X V , so |(nI)∗ | =
|X| · |I ∗ |, hence
nI
I

!

q

= |X| =

|(nI)∗ |
|nI| − 1
q nk − 1
=
=
.
|I ∗ |
|I| − 1
qk − 1

Observe that corollary 5.3 offers a formula to compute the Gaussian binomial coefficient, this is presented as an indexed product of simpler Gaussian
binomial coefficients. Lemma 5.6 gives another formula to calculate the factors that appear in the first one, but this last depends on other simpler
terms that are finally calculated in corollary 5.8, when the minimal ideals
that appear in those terms have multiplicity 1 in their group algebra. By
corollary 4.5, every semisimple commutative ring A is multiplicity-free, i.e.,
every minimal I of A appears with multiplicity 1 in A. Consequently, we
can compute explicitly any binomial Gaussian coefficient when working with
finite semisimple commutative group algebra.
Let A = Fq [G] be a commutative semisimple group algebra and M a
finitely generated A-module. If M has unique decomposition, then M is
multiplicity-free (by theorem 4.9 and corollary 4.5). However, in the noncommutative case, it is not known if having unique decomposition implies
being multiplicity-free. Consequently, we state the following obvious result.
Lemma 5.9 Let A = Fq [G] semisimple, I ≤ A minimal
ideal, and n ∈ N.

Then nI has unique decomposition if and only if nI
=
n.
I q
Proof. It follows from theorem 4.1 part 1.

5.1

Counting all the G-invariant codes

The following result plays an important role in the solution of the invariance
problem.
Lemma 5.10 Let G ≤ AutFq (Fnq ) with A = Fq [G] semisimple. Let {Ij |
j = 1, ..., r} be a basic set of ideals for Fnq , and Hj ∼
= nj Ij be the homogeneous
n
component of Fq associated to Ij for all j = 1, ..., r. Let S(M ) := {C ≤
M | C is a G − invariant code} for all G-invariant code M ≤ Fnq . Let
Q
D(B) := j∈B {1, ..., nj } for all B ∈ T := 2{1,...,r} − {∅}. Then,
Q

1. |S(Fnq )| = rj=1 |S(Hj )|. In addition, S(Fnq ) = {⊕ri=1 Mi | Mi is a A−
submodule of Hi , f or all i = 1, ..., r}.

15

2.

|S(Fnq )|
Qr

j=1

=


P

B∈T


P nj

P

(tj )j ∈D(B)

nj I j 
tj =1 tj Ij q



+1 .


Q

nj I j 
j∈B tj Ij
q



+1 and

Qr

j=1 |S(Hj )|

=

Proof.
Q

1. Let f : S(Fnq ) −→ rj=1 S(Hj ) be given by N 7→ (Nj )rj=1 such that
Nj is the homogeneous component of N associated to Ij if Ij | N and
Nj = 0 otherwise for all j = 1, ..., r. Then f is invertible with inverse
Q
g given by (Aj )rj=1 7→ ⊕rj=1 Aj , so |S(Fnq )| = rj=1 |S(Hj )|. It is clear
that S(Fnq ) = {⊕ri=1 Mi | Mi is a A − submodule of Hi , f or all i =
1, ..., r} ( S(Fnq ).
2. Observe that


S(Fnq ) = 
thus |S(Fnq )| =
5.3).

[

[

B∈T (tj )j ∈D(B)



P

B∈T

P

Note that |S(Hj )| = 1+
for all j = 1, ..., r, thus

5.2



{C ≤ Fnq | C ∼
= ⊕j∈B tj Ij }

(tj )j ∈D(B)


Q

nj I j 
j∈B tj Ij
q





nj I j 
+ n2Ij Ijj +· · ·+ nnjj IIjj
Ij q
q
q

Qr

j=1 |S(Hj )| =

Qr

j=1


P nj

[

{0},

+ 1 (by corollary

=

P nj

nj I j 
tj =1 tj Ij q +1

nj I j 
tj =1 tj Ij q



+1 .

Counting 1-generator G-invariant codes

Let G ≤ AutFq (Fnq ). If 0 6= C ≤ Fnq is G-invariant such that it is a cyclic
Fq [G]-module, it will be said that C is a 1-generator G-invariant linear
code. In this subsection we give an application of the Gaussian binomial
coefficient to the problem of counting 1-generator G-invariant linear codes
in Fnq . In [11] Séguin discussed the enumeration of 1-generator quasi-cyclic
codes in the special case when the prime factorization of xm −1 is the same in
Fqn [x] as in Fq [x]; later in [10], J. Pei and X. Zhang offered a more general
approach to the same question. As 1-generator quasi-cyclic codes are a
particular case of 1-generator G-invariant codes, a more general approach
to that question is offered here.
Lemma 5.11 Let G ≤ AutFq (Fnq ) be such that A = Fq [G] is a semisimple
group algebra. Let {Ij | j = 1, ..., r} be a basic set of ideals for Fnq , let nj
16

and kj be the multiplicity of Ij in Fnq and A respectively, for all j = 1, ..., r.
Let lj = min{nj , kj } and hj = dimFq (Ij ) for all j = 1, ..., r, Y = ⊕rj=1 lj Ij ,
X = {C ≤ Fnq | C is a 1-generator G − invariant code}, and D(B) =
Q
{1,...,r} − {∅}. Then,
j∈B {1, ..., lj } for all B ∈ T := 2
1. C ∈ X if and only if C | Y and C 6= 0.
2. |X| =
1.

P

B∈T

P

(tj )j ∈D(B)


Q

nj I j 
j∈B tj Ij
q



=



3. If lj = 1 for all j = 1, ..., r, then |X| =

Qr

j=1

|X| =

Proof.



P

nj I j 
Ij q

B∈T



+1


Q

Qr


Plj

P


Q

nj I j 
j∈B Ij
q



− 1.

j=1

B∈T

nj I j 
tj =1 tj Ij q



+1


=

− 1. Moreover, if kj = 1 for all j = 1, ..., r, then

q nj hj −1
j∈B q hj −1



=



Qr

j=1



q nj hj −1
q hj −1

+1

1. C ∈ X if and only if C is a cyclic A-module (different from 0), and as
A is a semisimple ring this occurs, if and only if C is isomorphic to a
non-zero ideal of Fq [G], if and only if C | Y and C 6= 0.
2. By part 1, X =

S

|X| =

S

(tj )j ∈D(B) {C

B∈T

X

X

X

X

X

X

≤ Fnq | C ∼
= ⊕j∈B tj Ij }, thus

|{C ≤ Fnq | C ∼
= ⊕j∈B tj Ij }|

B∈T (tj )j ∈D(B)

=

B∈T (tj )j

=



Fnq

⊕j∈B tj Ij
∈D(B)

B∈T (tj )j ∈D(B)




Y

j∈B

! 

q

! 
nj Ij 
,

tj Ij

q

where the last equality is by corollary 5.3. On the other hand, by
part 1, X = {⊕rj=1 Uj | Uj ≤ Fnq ∧ Uj | lj Ij } − {0}. Let f : X →
Qr
n
r
j=1 {Z ≤ Fq | Z | lj Ij } − {0} be given by f (L) = (Lj )j=1 where Lj
is the homogeneous component of L associated to Ij , if Ij | L and 0
Q
otherwise, it is easy to see that f is a bijection, so |X| = rj=1 |{Z ≤
Fnq

| Z | lj Ij }| − 1 =



Qr

j=1


Plj

lj Ij 
tj =1 tj Ij q

17



+1

− 1.

−

3. If lj = 1 for all j = 1, ..., r, then D(B) = {(1, ..., 1)} for all B ∈ T .
Hence by part 2,

|X| =



X



B∈T



r
Y

nj Ij
Ij

Y

j∈B



n I
 j j
= 
Ij
j=1

!

q

! 

q



+ 1 − 1.

Moreover, if kj = 1 for all j = 1, ..., r, then lj = 1 for all j = 1, ..., r.
So by part 2,

|X| =

X

B∈T



= 




r
Y

Y q nj h j − 1

j∈B

q hj − 1

q nj h j




!
−1
+ 1  − 1,

q hj − 1

j=1

where the last equality is by corollary 5.8.

6

Computing sum of Fq [G]-submodules

Throughout this section A = Fq [G] is semisimple, and M is a finitely generated A-module. As every A-submodule of M must be a direct sum of a
finite number of simple A-submodules, all the A-submodules of M can be
computed by taking all the possible sums of simple A-submodules of M .
However, if this is not done carefully, the amount of work could increase
considerably because when an A-submodule does not have unique decomposition, it may be expressed in many different ways as a direct sum of
simple A-submodules. The following result provides a partial solution to
that problem.
Lemma 6.1 Let A = Fq [G] be semisimple, with I ≤ A a minimal ideal. Let
M be a finitely generated A-module, with I | M such that the collection of all
A-submodules of M isomorphic to I is {Ni }i∈J with J = {1, ..., r}, and H

18

the homogenous component
of M associated to I. Let n be the multiplicity
!
J
of I in M , and
the collection of subsets of J with k elements.
k
Let (F, Z, X) be given as output of Algorithm 1. Then the following
statements hold:
1. F contains all A-submodules of H.
2. If y0 , y1 ∈ Z, then
3. For all y ∈ Z,

P

P

j∈y

j∈y0

Nj 6=

P

j∈y1

Nj .

Nj = ⊕j∈y Nj .

Proof. Let J := {1, ..., r} and E :=

Sn

t=1

J
t .

Observe that E = X ⊔ Z.

1. Proceeding by induction on the multiplicity l of I in the A-submodules
of H, it is easy to see that for l = 2, the statement holds, i.e., F contains
all A-submodules of H that are the sum of two simple A-modules.
Suppose that the same is true for l k with k a positive integer, i.e.,
F contains all A-submodules of H that are the direct sum of l simple
A-modules with l
k. Let y ∈ E with |y| = k. If y ∈ Z, it is clear
P
that j∈y Nj ∈ F , otherwise if y ∈ X, there exists z ∈ Z with |z| ≤ k
P
P
such that j∈y Nj ⊆ i∈z Ni ∈ F (by construction of X, Algorithm
P
P
1, lines 22, 23, and 24). If j∈y Nj = i∈z Ni , the proof ends. On the
P
P
P
other hand, if j∈y Nj ( i∈z Ni , the multiplicity of I in j∈y Nj
P
must be less than the multiplicity of I in i∈z Ni , which is at most
P
|z| ≤ k, and by inductive hypothesis, j∈y Nj belongs to F .
P

P

2. Suppose that there exist y, y ′ ∈ Z with y 6= y ′ and i∈y Ni = j∈y′ Nj .
Without loss of generality, y was added before than y ′ to Z in line 9 of
P
P
P
Algorithm 1. Then i∈y Ni = j∈y′ Nj implies Nj ⊆ i∈y Ni for all
j ∈ y ′ . Let Ry := {j ∈ J − y | Nj ⊂ ⊕i∈y Ni } (the obtained set after
executing the loop in line 12 of Algorithm 1), then y ′ ⊆ Ry ∪ y. In
addition, |y ′ | ∈ [|y|, min{|Ry ∪ y|, n}], but in the step in which y was
added to Z, y ′ did not belong to Z (because y was added before than
y ′ to Z), thus y ′ was added to X (by construction of X, Algorithm 1,
lines 22, 23, and 24) which contradicts that y ′ ∈ Z.
P

3. Suppose that there exists y ∈ Z such that i∈y Ni is not a direct sum,
P
then there exists l ∈ E with |l| |y| and ⊕j∈l Nj = i∈y Ni . If l ∈ Z,
then l was added first than y to Z in line 9 of Algorithm 1 (because
|l|
|y|). Let Rl := {i ∈ J − l | Ni ⊂ ⊕j∈l Nj } (the obtained set
19

Algorithm 1 Sum of simple A-modules
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

function Subadd({N1 , ..., Nr }, n)
X = ∅; J = {1, ..., r}
⊲ Where ∅ is the empty set.
Z = {{1}, {2}, ..., {r}}
F = {N1 , ..., Nr , 0}
for k = 2 to n do
!
J
for y ∈
do
k
Ry = ∅
if not y ∈ X then
add y to Z
P
add j∈y Nj to F
count = 0
for t ∈ J − y do 
if count < kI
⊲
I q − |y| then
this conditional could be omitted, but that would make the algorithm
to execute slower, so for the proof of lemma 6.1 it can be ignored.
P
if Nt ⊂ j∈y Nj then
add t to Ry
count = count + 1
end if
else
break
end if
end for
for j = k to min{|R!y ∪ y|, n} do
Ry ∪ y
for u ∈
− Z do
j
add u to X
end for
end for
end if
end for
end for
return (F, Z, X)
end function

20

after executing the loop in line 12 of Algorithm 1), then y ⊆ Rl ∪ l.
In addition, |y| ∈ [|l|, min{|Rl ∪ l|, n}], however in the step in which
l was added to Z, y did not belong to Z (because |l|
|y|), thus
y was added to X (by construction of X, Algorithm 1, lines 22, 23,
and 24) which contradicts that y ∈ Z. If l ∈ X, there exists y ′ ∈ Z
P
with |y ′ | ≤ |l| such that ⊕j∈l Nj ⊆ j∈y′ Nj (by construction of X,
P
Algorithm 1, lines 22, 23, and 24), so i∈y Ni = ⊕j∈l Nj = ⊕j∈y′ Nj ,
but y 6= y ′ (because |y ′ | ≤ |l|
|y|) and y, y ′ ∈ Z which contradicts
part 2).

7

Computing the G-invariant codes of Fnq

In this section we provide a method to compute all the Fq [G]-submodules
(G-invariant codes) of Fnq for a given G ≤ AutFq (Fnq ), when |G| and q are
relative primes; In this case Maschke’s theorem guaranties that the Fq [G]submodules of Fnq are direct sums of simple Fq [G] submodules, so we will
start by finding these modules.

7.1

Additional results for the solution of the invariance problem

In this subsection different results that help to determine G-invariant codes
are presented, starting with Theorem 7.1. Although it is a particular case
of [1] Theorem 54.12, a different proof is offered here.
Theorem 7.1 (Minimal divisor) Let A = Fq [G] be a finite group algebra
with (|G|, q) = 1, e ∈ A a primitive idempotent, I = Ae the minimal ideal
generated by e, and M a finitely generated A-module. Then,
I | M if and only if eM 6= 0.
Proof. By lemma 2.1, HomA (I, M ) ∼
= eM as commutative groups, so
eM 6= 0 if and only if HomA (I, M ) 6= 0. By the additivity of the functor
HomA (Ae, ) respect to direct sums and Schur’s lemma, this happens if and
only if I | M .
Lemma 7.2 Let A = Fq [G] be semisimple, M a finitely generated A-module,
e ∈ A a primitive idempotent, such that I = Ae | M , and H the homogeneous component associated to I. If n is the multiplicity of I in H, then the
following statements hold:
21

1. H ∼
= n(Ae) as A-modules.
2. eM ∼
= n(eAe) as Fq -spaces.
3. If e is central, then eM = H.
Proof.
1. It is clear.
2. By lemma 2.1, HomA (Ae, M ) ∼
= eM as Fq -spaces, but HomA (Ae, M ) ∼
=
nHomA (Ae, Ae) = nEndA (Ae) ∼
n(eAe)
as
A-modules,
therefore
=
eM ∼
= n(eAe) as Fq -spaces.
3. If e is central, by lemma 2.1, eM ∼
= HomA (Ae, M ) ∼
= n(eAe) =
∼
n(Ae) = H as A-modules, this implies that every simple submodule of eM is isomorphic to Ae (by [2] proposition 3.20, part 2), so
eM ≤ H, thus eM = H.
Corollary 7.3 If A, M , H, e, and n are as in lemma 7.2, then n =
dimFq (H)/dimFq (Ae) = dimFq (eM )/dimFq (eAe).
Proof. It follows from lemma 7.2 parts 1 and 2.
There might be occasions in which one could know a generator element
of a minimal ideal that is not an idempotent (this is common when working
with the group algebra Fq [Cn ]), and try to find out if its generated ideal
divides a given module, for example, to compute its multiplicity or its associated homogeneous component. For that purpose we have the following
corollary.
Corollary 7.4 Let A = Fq [G] with (|G|, q) = 1, e ∈ A a e primitive idempotent, M a finitely generated A-module, and 0 6= f ∈ I = Ae such that
I | M . Then
1. eM 6= 0 if and only if f M 6= 0
2. If e and f are central, f M is the homogeneous component of M associated to I, and the multiplicity of I in M is n = dimFq (f M )/dimFq (f Af ).
Proof.
1. If eM = 0, then there exists b ∈ A such that f M = (be)M = b(eM ) =
0. Similarly, if f M = 0, then eM = 0, so eM = 0 if and only if
f M = 0.
22

2. Let e and f be central, then eM = f M and eAe = f Af , so by corollary
7.3, n = dimFq (eM )/dimFq (eAe) = dimFq (f M )/dimFq (f Af ) is the
multiplicity of I in M . In addition, if H is the homogeneous component
associated to I, then H = eM = f M by lemma 7.2 part 3 .
Corollary 7.5 Let G ≤ AutFq (Fnq ) with (|G|, q) = 1, C ≤ Fnq be a Ginvariant code, {e1 , ..., er } a basic set of idempotents for C, and Hi the
homogeneous components of C associated to ei for all i = 1, ..., r. Then the
following statements are equivalent
1. dimFq (ei C) = dimFq (ei Aei ) for all i = 1, ..., r.
2. Hi is a simple A-module for all i = 1, ..., r.
3. C is multiplicity-free.
(1) implies (2): if dimFq (ei C) = dimFq (ei Aei ) for all i = 1, ..., r, by
corollary 7.3, Hi is a simple A-module for all i = 1, ..., r. (2) implies (3): it
is clear. (3) implies (1): if C is multiplicity-free, by corollary 7.3, 1 = ni =
dimFq (ei C)/dimFq (ei Aei ) finishing the proof.
Lemma 7.6 Let A = Fq [G], M an A-module, and m ∈ M . Then A · m =
hO(m)iFq where O(m) is the orbit of m under the multiplication by elements
of G.
Proof.

A·m




 X


=
λg g · m | g ∈ G, λg ∈ Fq


g∈G



X

λg (g · m) | g ∈ G, λg ∈ Fq

=



g∈G

= h{g · m | g ∈ G}iFq = hO(m)iFq



Lemma 7.2 part 3 offers an easy way to compute a homogeneous component of an Fq [G]-module associated to a minimal ideal generated by a central
primitive idempotent, so it is natural to ask over what happens when this
idempotent is not central. Theorem 7.7 engloves both situations. However,
in practice, it is recommended to use corollary 7.2 instead of this theorem,
when possible, because it requires less work.
23

Theorem 7.7 Let A = Fq [G] with (|G|, q) = 1, M be a finitely generated
A-module, e a primitive idempotent in A such that I = Ae | M , and H the
homogeneous component of M associated to Ae. If β = {β1 , β2 , ..., βr } is a
P
generating set of M as Fq -vector space, then rj=1 A(eβi ) = H.

Proof. Let O(x) denote the orbit of x under the left action of G
in M for all x ∈ M . From lemma 7.2 eM ∼
= n(eAe) ≤ n(Ae) (as Fq vector spaces) where n is the multiplicity of Ae in M . Let yi ∈ n(eAe)
such that has e as its i-th entry and 0 otherwise for all i = 1, ..., n, then
Y := {yi | i = 1, ..., n} ⊂ n(eAe) is such that n(Ae) = ⊕ni=1 Ayi . For any
φ ∈ IsoA (H, nAe), its restriction η to eM ⊂ H belongs to IsoFq (eM, n(eAe))
and is such that η −1 (Y ) = {zi := η −1 (yi ) | i = 1, ..., n} is a subset of eM such
that H = ⊕ni=1 Azi (because Y generates nAe). On the other hand, X :=
P
{eβ1 , eβ2 , ..., eβr } generates eM as vector space, hence zi = rj=1 cij eβj for
Pr
all i = 1, ..., n, then gzi = j=1 cij g(eβj ) for all i = 1, ..., n and g ∈ G,
so O(zi ) ⊂

DS

E

r
j=1 O(eβj ) F
q

=

Pr

j=1 hO(eβj )iFq

=

Pr

j=1 A(eβj )

⊆ H for

all i = 1, ..., n, where the last of the equalities follows from lemma 7.6.
P
Then hO(zi )iFq = Azi ⊂ rj=1 A(eβj ) (by lemma 7.6) and ⊕rj=1 Azi = H ⊆
Pr
j=1 (Aeβj ).

Lemma 7.8 Let G = {gi | i = 1, ..., k} ≤ AutFq (Fnq ) with (|G|, q) = 1
and A = Fq [G]. Let I = Ae ≤ A with e a primitive idempotent.

 Let
g1 (m)
g (m) 


M = Am, and N = An be cyclic A-submodules of Fnq , B :=  2
, and
 ··· 
gk (m)


g1 (m)
g (m)
 2



C :=  · · · .


gk (m)
n
Then the following statements hold:
1. M ∼
= I if and only if dimFq (I) = rank(B) and e · O(m) 6= {0}.
Moreover, if e is central, the condition e·O(m) 6= {0} could be replaced
by e · m 6= 0.
2. N ≤ M if and only if rank(C) = rank(B). Moreover, If N, M are
simple A-modules, N = M if and only if rank(C) = rank(B).
Proof.
24

1. If M ∼
= I, in particular I | M and by theorem 7.1, e · M 6= 0, implying that e · O(m) 6= {0} (because M = hO(m)iFq by lemma 7.6), so
e · O(m) 6= {0} and dimFq (I) = dimFq (M ) = rank(B).
Conversely, if {0} =
6 e · O(m) ⊆ e · M , theorem 7.1 implies that I | M ,
but dimFq (I) = rank(B), so dimFq (M ) = dimFq (I) (by lemma 7.6),
therefore I ∼
= M as vector spaces.
If e is central, e(O(m)) = 0 if and only if e(m) = 0.
2. If N ≤ M , then n ∈ M = hO(m)iFq , thus rank(C) = rank(B).
Conversely, if rank(C) = rank(B), then n ∈ M = hO(m)iFq , so g(n) ∈
M for all g ∈ G, thus O(n) ⊆ M , and by lemma 7.6, N = An =
hO(n)iFq ≤ M . Moreover, if N, M are simple A-modules, then N ≤ M
if and only if N = M if and only if rank(C) = rank(B).

7.2

A method to compute G-invariant codes

In [11] Séguin describes an algorithm to obtain a unique generator for each
q-ary 1-generator quasi-cyclic code, later in [10] J. Pei and X. Zhang offer a
more general approach to the same question. A method for finding a unique
generating set for every G-invariant linear code when G ≤ AutFq (Fnq ) is
given here.
As it was mentioned before, the first step to determine the G-invariant codes
(Fq [G]-submodules) of Fnq for a given G ≤ AutFq (Fnq ), when |G| and q are
relative primes, is finding all simple Fq [G]-submodules, then compute all
their sums.
Let G ≤ AutFq (Fnq ) with (|G|, q) = 1, A = Fq [G], X be a basic set of idempotents for Fnq , and He the homogeneous component associated to I := Ae
for all e ∈ X. By doing what is indicated in the Steps 1 − 3 (presented
below) for all e ∈ X we can obtain all simple A-submodules of Fnq , and then
by doing what is indicated in Step 4 all A-submodules (G-invariant codes)
of Fnq are obtained.
Step 1(Computation of homogeneous components). Determine the homogeneous component He of Fnq , which can be done by using lemma 7.2
(part 3) or corollary 7.4 (part 2), if e is central. Otherwise, by using theorem 7.7.

25

Step 2:(Computation of quotient sets). Once He is determined, considering that all cyclic A-modules, and so all simple A-modules, are generated
as Fq -spaces by the orbit of one generating element as A-module (by lemma
7.6), the quotient set He /G = {O(m) | m ∈ He } of the orbits under the
action by evaluation of G on He is determined.
Step 3:(Determine a unique generating orbit for every simple A-module).
Determine those orbits on He /G that generate simple A-modules and obtain a unique generating orbit for every simple A-submodule contained in
He . All the orbits in He /G generate A-modules which have I (up to isomorphims) as a unique simple divisor (by [2] Proposition 3.20, part 2), so
by lemma 7.8 (part 1) and theorem 7.1, we just need to check whether an
orbit generates a space with the right dimension i = dimFq (I) and obtain
a unique generating orbit for every simple A-submodule. A way to do this
is as follows: First, if A is non-commutative, compute all the orbits O of
L := {o ∈ He /G | |o| = min{|u| | u ∈ I/G − {{0}} } } such that
dimFq (hOi) = i. When A is commutative, is not necessary to computate L,
because in this case every orbit different from the orbit of the zero vector
will generate a simple A-mopdule (by lemma 4.6). Second, identify when
two of orbits in L (when A is non-commutative) or He /G (when A is commutative) generates the same simple A-module by using lemma 7.8 (part 2)
to obtain only one generating orbit for every simple A-submodule contained
in He .
Another way to determine a unique generating orbit for every simple Amodule is by using Algorithm 0.
Step 4:(Computing direct sums). Once we have all the simple A-modules
contained in Fnq and the multiplicity of I in He (this last can be obtained by
using corollary 7.3), every A-submodule of each homogeneous component
can be computed, in an efficient way, by using Algorithm 1. After that, the
A-submodules of Fnq can be determined by taking all possible direct sums
of these submodules, this time without any worry of wasting resources, i.e.,
with no risks of getting repetitions, otherwise, the function given in lemma
5.10, part 1, would not be a bijection.
Let us make some remarks on how to get a generating set for every
G-invariant code. If we provide a (indexed) list of all the simple modules
contained in an homogeneous component of Fnq , Algorithm 1 gives a collection Z of subsets of the set of indices, such that every A-submodule of the
homogeneous component can be seen as a sum of some of these simple mod26

Algorithm 2 Orbits generating simple modules
1:
2:
3:

4:
5:
6:
7:
8:

9:
10:
11:

12:
13:
14:
15:

16:
17:
18:
19:

function Ogsm(G, He /G, I)
if G is not commutative then
L = {O ∈ He /G | |O| = min{|u| | u ∈ I/G − {{0}} } }⊲ This is
to discriminate orbits that do not fit with the proper size to generate a
simple module and to ease the verification of the dimensions.
U = ∅, V = ∅
for O in L − V do
if dimFq (hOiFq ) = dimFq (I) then
add O to U

V = V ∪ (hOiFq /G) ∩ L − {O}
⊲

This step is due to the fact
that if (hOiFq /G) ∩ L − {O} =
6 ∅, all the

orbits in (hOiFq /G) ∩ L −{O} will generate the same simple A-module
hOiFq and we want to have only one generating orbit for every simple
A-module.
end if
end for
else
⊲ In this case G is commutative and we do not have
to check dimensions, by lemma 4.6 every orbit in He /G will generate a
simple A-module.
U = ∅, V = ∅
for O ∈ (He /G) − V do
add O to U

⊲ This step is
V = V ∪ hOiFq /G − {O}
due to the fact that all the orbits in (hOiFq /G) − {O} will generate the
same simple A-module hOiFq and we want to have only one generating
orbit for every simple A-module.
end for
end if
return U
end function

27

ules, that is indexed by a unique element of Z. Thus, we could obtain one
( and only one) generating set for every A-submodule of an homogeneous
component of Fnq , that has been calculated by the Algorithm 1.
A generating set for one of the modules calculated by Algorithm 1 can be
obtained just by taking a non-zero element in each of the simple A-modules
that appears in its decomposition. In general, for the A-submodules of Fnq
(G-invariant codes), as they are direct sum of A-submodules of the homogeneous components of Fnq , we just need to take the unions of the generating
sets of these sumands.
We have just determined how to compute generating sets for G-invariant
codes. Nonetheless, when working with a code, it is important to know a
basis of it. The natural way to obtain a basis for a G-invariant code is by
computing it from a union of generating orbits of simple submodules belonging to a decomposition of it. The following results will show another
way to do so.
Lemma 7.9 Let A = Fq [G] be semisimple, Ae ≤ A an ideal with e primitive idempotent, 0 6= Ax a cyclic A-module isomorphic to Ae. Let B :=
{b1 , b2 , ..., bk } a Fq -basis for Ae. If ex 6= 0, then B ′ = {b1 x, b2 x, ..., bk x} is a
Fq -basis for Ax.
Proof. If g : Ae −→ Ax is given by g(ae) = (ae)x, then g is a morphism of A-modules, which is non-zero (because ex 6= 0), and so it is an
A-isomorphism (by Schur’s lemma). Therefore, g(B) = B ′ is a Fq -basis for
Ax.
Theorem 7.10 Let A = Fq [G] be semisimple, and M a finitely generated
A-module. Let {f1 , ..., fk } ⊂ A be a basic set of idempotents for M , X =
{n1 , ..., nr } ⊂ M such that Ani is simple for all i ∈ {1, ..., r} and M =
⊕ri=1 Ani . Let lj = {i ∈ {1, ..., r} | Ani ∼
= Afj } and Bj = {b1j , b2j , ..., buj j }
′ = {b n , b n , ..., b
a basis for Afj for all j = 1, ..., k. Let Bji
1j i 2j i
uj j ni } with
i ∈ ljfor all j = 1, ..., k. If fj ni 6= 0 for all i ∈ lj and j ∈ {1, ..., k}, then
Sk
S
′
j=1
i∈lj Bji is a basis for M .




Proof. Observe that M = ⊕ri=1 Ani = ⊕kj=1 ⊕i∈lj Ani . Let fj ni 6= 0
for all i ∈ lj and j ∈ {1, ..., k}. If j ∈ {1, ..., k} and i ∈ lj , fj ni 6= 0,
′ = {b n , b n , ..., b
so by lemma 7.9, Bji
1j i 2j i
uj j ni } is basis for Ani , therefore
Sk

j=1

S

i∈lj



′
is a basis for M .
Bji

28

8

What to do when a basic set of idempotents is
not known

Observe that the previous ideas work if a basic set of idempotents for Fnq is
known. In the following lines an alternative solution is discussed. Let G ≤
AutFq (Fnq ) and Fq [G] be its corresponding group algebra, with (|G|, q) = 1.
To find a basic set of primitive idempotents for Fq [G] the results presented
in [12], [7], [8], or [4] might be useful. After having determined a basic set
of idempotents for Fq [G], by using lemma 7.1, a basic set of idempotents
for Fnq can be computed. Otherwise, considering that, in theory, the use of
primitive idempotents of Fq [G] to solve the invariance problem is not strictly
necessary, we could work using the following reasoning instead.
Lemma 8.1 Let G ≤ AutFq (Fnq ), S = {s1 , ...sr } be a generating set for G,
hsi i the cyclic group generated by si for all i = 1, ..., r, and C ≤ Fnq a linear
code. The following conditions are equivalent:
1. C is a G-invariant code
2. C ∈

Tr

i=1 {D

≤ Fq | D is Fq [hsi i] − submodule of Fnq }

Proof. C is G-invariant if and only if g(C) = C for all g ∈ G, if and
only if si (C) = C for all i = 1, ..., r, if and only if C is Fq [hsi i]-submodule
T
of Fnq for all i = 1, ..., r, if and only if C ∈ ri=1 {D ≤ Fq | D is Fq [hsi i] −
submodule of Fnq }.
So one can solve the problem of determining the G-invariant codes by
finding the hsi i-invariant codes, where S = {s1 , ..., sr } is a generating set of
G. This theoretic result is unpractical thought, but if we combine what we
know up to now with lemma 8.1, we could be able to lower the computations.
For example, If we want to compute the G-invariant codes of Fnq , we could
find first the N -invariant codes for certain subgroup N of G, such that the
idempotents of Fq [N ] are easier to compute, and then see which of these
codes are invariant under the elements of T = {ti | i = 1, ..., u}, where T is
a set of representatives of G/N . With that reasoning the invariance problem
could be result with a more reasonable effort when we do not know a basic
set of idempotents for Fnq .

9

Examples of computations of G-invariant codes

In this section some examples that illustrate the process of solving the invariance problem will be offered. For that aim, we will use all the steps
29

presented in section 7.2.
Example 9.1 Let A = F2 [C3 ]. Consider γ ∈ AutF2 (F92 ) given by γ = σ 3 ,
where σ is the cyclic shift, then hγi ∼
= C3 = {1, x, x2 } and F92 is an F2 [C3 ]module. Using corollary 7.4 (part 1), it is easy to see that the minimal
ideals I0 := A(x − 1) and I1 := A(x2 + x + 1) of A divide F92 , so its simple
A-submodules (C3 -invariant codes) are isomorphic to I0 and I1 . As these
ideals are not isomorphic, {I0 , I1 } is a basic set of ideals for F92 .
Computing the A-submodules of the homogenous components H0 and H1 of
F92 .
Step 1: (Computation of homogeneous components). As both I0 and I1
divide F92 , and A is commutative ring, by corollary 7.4 (part 2), H0 :=
(γ + id)(F92 ) is the homogeneous component of F92 associated to I0 , and
H1 := (γ 2 + γ + id)(F92 ) is the homogeneous component associated to I1 . Let
β be the canonical basis of F92 , then
(γ + id)(β) = {100100000, 010010000, 001001000,
000100100, 000010010, 000001001,
100000100, 010000010, 001000001}
and (γ + γ 2 + id)(β) = {100100100, 010010010, 001001001} generate H0
and H1 as F2 -vector space respectively.
Steps 2: (Computation of quotient sets). Let H0 / hγi and H1 / hγi be the
quotient sets determined by the action by evaluation of hγi on H0 and H1
respectively, and O(v) the orbit of v for all v ∈ F92 . Then H0 / hγi is given
by
{O(100100000),
O(001001000),
O(111111000),
O(101001100),
O(011111100),
O(001011010),
O(011101110),

O(010010000), O(110110000),
O(101101000), O(011011000),
O(110010100), O(010110100),
O(001101100), O(111011100),
O(011001010), O(111101010),
O(101111010), O(111001110),
O(101011110), O(001111110)}.

and H1 / hγi is given by
{O(000000000), O(100100100), O(010010010),
O(110110110), O(001001001), O(101101101),
O(011011011), O(111111111)}.
30

Steps 3: (Determining a unique generating orbit for every simple Amodule). As A is commutative, every non-trivial orbit, i.e., different from
the orbit of the zero vector, in H0 / hγi and H1 / hγi, generates a simple Amodule (by lemma 4.6). Moreover, as every orbit in H0 / hγi has size 3
and |I0 | = 4, every simple A-module in H0 has a unique generating orbit.
Similarly, as every orbit in H1 / hγi has size 1 and |I1 | = 2, every simple
A-module in H1 has a unique generating orbit.
If we determine a unique generating vector for every simple F2 [C3 ]-submodules
of F92 that is isomorphic to I0 , we get
n0 =100100000,
n3 =001001000,
n6 =111111000,
n9 =101001100,
n12 =011111100,
n15 =001011010,
n18 =011101110,

n1 =010010000,
n4 =101101000,
n7 =110010100,
n10 =001101100,
n13 =011001010,
n16 =101111010,
n19 =101011110,

n2 =110110000,
n5 =011011000,
n8 =010110100,
n11 =111011100,
n14 =111101010,
n17 =111001110,
n20 =001111110.

If we determine a unique generating vector for every simple F2 [C3 ]submodules of F92 that is isomorphic to I1 , we get
m0 =100100100, m1 =010010010, m2 =110110110,
m3 =001001001, m4 =101101101, m5 =011011011,
m6 =111111111.
Let Ni := Ani for all i = 0, ..., 20, and Mj := Amj for all j = 0, ..., 6.
Note that h0 := dimF2 (H0 ) = dimF2 (h(γ+id)(β)i) = 6 and h1 := dimF2 (H1 ) =
dimF2 (h(γ + γ 2 + id)(β)i) = 3, so the multiplicities of I0 and I1 in H0
and H1 respectively, in both cases, are equal to 3 (by corollary 7.3), thus
H0 ∼
= I0 ⊕I0 ⊕I0 and H1 ∼
= I1 ⊕I1 ⊕I1 , hence, by corollary 5.8, I0 ⊕II00 ⊕I0 2 =
23×2 −1
22 −1



= 21, I1 ⊕II11 ⊕I1 2 =
tions we have just made.

23×1 −1
21 −1

= 7, which coincides with the computa-

Steps 4: (Computing direct sums). By using Algorithm 1 all the nonsimple A-submodules of H0 and H1 can be computed. Let (F0 , Z0 , X0 ), and
(F1 , Z1 , X1 ) be the outputs given by Algorithm 1 for the inputs ({Ni | i =
0, ..., 20}, 3) and ({Mi | i = 0, ..., 6}, 3) respectively.
Then the A-submodules of H0 isomorphic to I0 ⊕ I0 are of the form ⊕j∈l Nj

with l ∈ Z20 , and
Z0 
2 = {{0, 1} , {0, 3} , {0, 5} , {0, 13} , {0, 15} , {1, 3} ,
{1, 9} , {1, 10} , {2, 3} , {2, 4} , {9, 2} , {2, 10} , {3, 7} , {8, 3} ,
31

{4, 7} , {8, 4} , {5, 7} , {8, 5} , {6, 7} , {1, 4} , {8, 6}}
The A-submodules of H1 isomorphic to I1 ⊕ I1 are of the form ⊕j∈l Mj

with l ∈ Z21 , and

Z1
2 = {{0, 1} , {0, 3} , {0, 5} , {1, 3} , {1, 4} , {2, 3} ,
{2, 4}}.
There is only one A-submodule of H0 (H1 ) isomorphic to I0 ⊕ I0 ⊕ I0
(I1 ⊕ I1 ⊕ I1 ) which is the homogeneous component H0 (H
) itself, and
 1
this can be considered as ⊕j∈l Nj (⊕j∈l Mj ) with l ∈ Z31 = {{0, 1, 3}}

(l ∈ Z30 = {{0, 1, 3}}).
By lemma 5.10 (part 1) the collection W := {U ⊕ V | U ∈ F0 ∧ V ∈ F1 },
is precisely the collection of all the C3 -invariant codes of F92 . If we take two
different elements (W0 , W1 ), (T0 , T1 ) ∈ F0 × F1 , then W0 ⊕ W1 6= T0 ⊕ T1 ,
otherwise, the function given in the proof of lemma 5.10 (part 1) would not
be a bijection. Thus, we can be sure that when calculating W no element
will be computed
more than once.

2×2 −1
2I0 
22×1 −1
1
= 5 and 2I
Note that I0 2 = 2 22 −1
I1 2 = 21 −1 = 3, hence, by lemma
5.6,

I0 ⊕I0 ⊕I0 
I0 ⊕I0

h

2

i

(3II11 )2 (3II11 )2 −1

=

i

h

(3II00 )2 (3II00 )2 −1

21×20
5×4

i =

h

(2II00 )2 (2II00 )2 −1
7×6
3×2

= 21 = |

Z0 
2 |,

I1 ⊕I1 ⊕I1 
I1 ⊕I1
2

and

=

Z1 
2 |

=7=|

, which is consistent with our computa( ) ( )
tions.
Now we count the total of C3 -invariant codes and 1-generator C3 -invariant
codes. Let S(M ) := {C ≤ M | C is a C3 − invariant code} for all C3 invariant code M ≤ F92 . By the computations done up to now and lemma
5.10 (part 2),
2I1
I1 2

h

i =

2I1
−1
I1 2

1
Y

j=0

|S(Hj )| =

1
Y

j=0



= 




3
X

X

tj ∈{1,...,nj }

t0 =1

3I0
t0 I0

!

2

nj Ij
tj Ij


!

2



+ 1 × 



+ 1

3
X

t1 =1

3I1
t1 I1

!

2



+ 1

= [(21 + 21 + 1) + 1] × [(7 + 7 + 1) + 1]

= 704
Q

and as W = S(F92 ), |W | = |S(F92 )| = 1j=0 |S(Hj )| = 704. Let X =
{C ≤ F92 | C is a 1-generator C3 − invariant code}, then by lemma 5.11
(part 3)
32



|X| = 

1
Y

q nj h j

q hj − 1

j=0

=

"

!
−1
+1 −1
!

23×2 − 1
+1 ×
23 − 1

!#

23×1 − 1
+1
23 − 1

−1

= [(21 + 1) × (7 + 1)] − 1 = 175.
Example 9.2 Let A = F5 [S3 ], β be the canonical basis of F95 , and x, y ∈
AutF5 (F95 ) such that

and





3
1
1
0
0
0
4
1
1

4
0
2
2
3
1
4
1
2

4
2
4
3
3
4
4
4
4

0
0
4
3
4
2
3
1
1

3
3
2
0
3
0
2
3
1

3
1
1
2
3
1
1
3
0

2
3
2
2
2
4
1
2
2

1
2


2

3

0

0


0

3
2



2
2
3
1
3
4
3
1
2

0
0
4
0
0
0
0
0
0

0
0
1
2
1
2
3
3
0

1
4
0
2
1
3
4
2
1

2
3
4
3
4
0
4
0
4

0
0
1
0
0
0
1
0
0

0
0
1
3
3
1
3
4
2

0
0


1

4

4

3


0

0
0

0
4


0

3

[x]β = 
2
2


0

2
1
0
4


2

1

[y]β = 
4
2


1

0
0



Let G = hx, yi. Then f : G −→ S3 = ha, b | a3 = b2 = 1, bab =
= {1, a, a2 , b, ba, ba2 } given by x 7→ a and y 7→ b is an isomorphism. By
example4.10. e0 = 1+a+a2 +b+ba+ba2 , e1 = 1+a+a2 +4b+4ba+4ba2 , e2 =
2 + 3a2 + 2b + 3ba2 are a basic set of idempotents for F5 [S3 ]. Using theorem
7.1 is easy to see that the minimal ideal Ij := Aej divides F95 , thus {I0 , I1 , I2 }
is a basic set of ideals for F95 . In addition, using corollary 7.3 is easy to see
that the multiplicity of Ij is j + 1 for all j = 0, 1, 2.
a2 i

33

Step 1: (Computation of homogeneous components). As e0 , e1 are central elements of A and both I0 , and I1 divide F95 , then by lemma 7.2, H0 :=
e0 F92 = (id + x + x2 + y + yx + yx2 )(F92 ) = h140442324i F5 is the homogeneous component associated to I0 , and H1 := e1 (F92 ) = (id + x +
x2 + 4y + 4yx + 4yx2 )(F92 ) = h{10020401, 001112001}i F5 is the homogeneous
component associated to I1 . On the other hand, by theorem 7.7, the set
{e3 v | v ∈ β} = {140111222, 142330020, 322033442, 414332434, 322021431,
323102302, 232403203, 231322332, 411020204} generates H2 as A-module.
Steps 2: (Computation of quotient sets). Let Hi /G be the quotient set
determined by the action by evaluation of G on Hi for all i = 0, 1, 2, and
O(v) the orbit of v for all v ∈ F92 . Then H0 /G is given by
{O(000000000), O(140442324), O(230334143),
O(320221412), O(410113231)}
and H1 /G is given by
{O(00000000),
O(001112001),
O(331122204),
O(112244403),
O(442204101)}

O(110020401),
O(111132402),
O(441142100),
O(222214304),

O(220040302),
O(221102303),
O(002224002),
O(332234200),

As |H2 /G| = 2667, we prefer not to write it explicitly, but it is relevant
to mention that just some of those orbits generate simple A-submodules.
Steps 3:(Determining unique generating orbit for every simple A-module).
As the multipliticy of I0 and I1 in A is 1, every orbit in H0 /G and H1 /G
generates a simple A-module (by lemma 4.6), but in none of the cases there
exists a simple A-module with a unique generating orbit. On the other hand,
in H2 /G there are orbits that do not generate simple A-modules, these are
precisely those that generate A-modules isomorphic to 2I2 . For example,
O(100000032) = {100000032, 130021232, 320034341, 042311021, 012314343,
001430241}. We use the instructions given in Step 3 (Section 7.2) to get a
unique generating orbit of Hi /G for each simple A-submodule of Hi for all
i = 0, 1, 2. When determining a unique generating vector for the simple Asubmodules of F95 isomorphic to I0 we get the vector l0 = 140442324. When
doing the same for the simple A-submodules of F95 isomorphic to I1 , we get
m0 =110020401, m1 =001112001, m2 =111132402,
m3 =221102303, m4 =331122204, m5 =441142100,
34

and when doing it for the simple A-submodules of F95 isomorphic to I2 ,
we get
n0 =221100102,
n3 =323311232,
n6 =221011401,
n9 =213021224,
n12 =411001232,
n15 =042010323,
n18 =414301401,
n21 =001100443,
n24 =400401244,
n27 =121001341,
n30 =322021431.

n1 =103100210,
n4 =234001133,
n7 =342101443,
n10 =412101120,
n13 =430201003,
n16 =234141023,
n19 =140111222,
n22 =320321100,
n25 =013201040,
n28 =033301213,

n2 =001331412,
n5 =131401423,
n8 =413201013,
n11 =144011334,
n14 =234301142,
n17 =234110040,
n20 =044411334,
n23 =310110242,
n26 =324111111,
n29 =020311031,

Let L0 := Al0 , Mi := Ami for all i = 0, ..., 5, and Nj := Amj for all
j = 0, ..., 30.
As Ij has multiplicity j + 1 in F95 for j = 0, 1, 2 respectively, H0 ∼
= I0
∼
and H1 ∼
I
⊕
I
⊕
I
.
As
the
multiplicity
of
I
in
A
is 1
= I1 ⊕ I1 and H
=
2
2
2
2
1

51×2 −1
1
=
6.
Observe
that,
up
to
now,
we
do
not
by corollary 5.8, I1I⊕I
=
55 −1
1
5

have a formula to calculate

I2 ⊕I2 ⊕I2 
I2
5

= 31.

Steps 4:(Computing direct sums). By using Algorithm 1, we can compute all the non-simple A-submodules of H2 (H1 only has one non-simple Asubmodule which is H1 itself, and H0 does not have non-simple A-submodules,
because H0 is simple). Let (F2 , Z2 , X2 ) be the output given by Algorithm 1
for the input ({Ni | i = 0, ..., 30}, 3) respectively.
The A-submodules of H1 isomorphic to I2 ⊕ I2 are of the form ⊕j∈l Nj with

l ∈ Z22 , and
Z2 
2 = {{0, 1} , {0, 6} , {0, 8} , {0, 10} , {0, 11} , {0, 14} ,
{1, 6} , {1, 7} , {8, 1} , {1, 11} , {1, 15} , {2, 6} , {2, 7} , {9, 2}
{2, 13} , {2, 15} , {3, 6} , {3, 7} , {9, 3} , {10, 3} , {11, 3} ,
{4, 6} , {4, 7} , {8, 4} , {9, 4} , {12, 4} , {5, 6} , {5, 7} , {8, 5} ,
{9, 5} , {12, 5}}
There is only one A-submodule of H2 isomorphic to I2 ⊕ I2 ⊕ I2 which
is H2 itself.
By lemma 5.10 the collection W := {L0 ⊕ U ⊕ V | U ∈ F1 ∧ V ∈ F2 }, is
the collection of all the S3 -invariant codes of F95 .
By doing some computations, is easy to see that N0 , N1 , N2 , N3 , N4 , N5 are
2
all the simple A-submodules contained in N0 ⊕ N1 ∼
=
= 2I2 , so I2I⊕I
2
5
35

6, hence

I2 ⊕I2 ⊕I2 

=

h

i

(3II22 )5 (3II22 )5 −1

i =

31×30
6×5

= 31 = |

Z2 
2 |,

which is
(2II22 )5 (2II22 )5 −1
consistent with our computations.
Now we offer an example over how to compute a basis for a given G-invariant
code using theorem 7.10. Observe that {e2 , ae2 }, {e0 }, {e1 } are basis for I2 ,
I0 , and I1 respectively. Consider the A-submodule C := N0 ⊕ N1 ⊕ M0 ⊕ L0 .
As e2 n0 , e2 (xn1 ), e1 (m0 ), and e1 (m0 ) are non-zero, by theorem 7.10,
I2 ⊕I2

5

h

γ := ({e2 (n0 ), ae2 (n0 )} ∪ {e2 (xn1 ), ae2 (xn1 )}) ∪
{e1 (m0 )} ∪ {e0 (l0 )}
=

({144030301, 334400403)} ∪ {414320423, 043130422}) ∪
{110020401} ∪ {140442324}

is a basis for C.

References
[1] Ch. W. Curtis, Irving Reiner. Representation Theory of Finite Groups
and Associative Algebras. Jhon Wiley and sons, 1962.
[2] C. Curtis, I. Reiner. Methods of representation theory with applications
to finite groups and orders. vol. 1, John Wiley and sons, 1981.
[3] F. S. Dutra, R. A. Ferraz and C. Polcino Milies, Semisimple group codes
and dihedral codes, Algebra and Disc. Math., number 3 , 28-48, 2009.
[4] C. Ding, D. R. Kohel, S. Ling, Split group codes. IEEE Transactions on
Information Theory, vol. 46, no. 2, 485-495, 2000.
[5] W. Knapp, P. Schmid, Codes with prescribed permutation group, J.
Algebra 67, 415-435, 1980.
[6] B. Kumar, B. Sundar, Codes closed under arbitrary abelian group of
permuatations. J. Disc. Math., Vol 18, No 1, 1-18, 2004.
[7] G. K. Bakshi, S. Gupta, I. S. Passi, The structure of finite semisimple
metacyclic group algebras, J. Ramanujan Math. Soc. 28, No.2, 141–158,
2013.

36

[8] G. K. Bakshi, S. Gupta, I. S. Passi, Semisimple metacyclic group algebras, Proc. Indian Acad. Sci. (Math. Sci.), vol. 121, No. 4, 379–396 ,
2011.
[9] H. Nagao, Y. Tsushima. Representations of finite groups. Academic Press
Inc., 1989.
[10] J. Pei, X. Zhang, 1-generator quasi-cyclic codes, Journal of Systems
Science and Complexity, 20, 554-561, 2007.
[11] G. E. Seguin, A class of 1-generator quasi-cyclic codes, IEEE Transactions on Information Theory, vol. 50, 1745-1753, 2004.
[12] I. V. Gelder, G. Olteanu, Finite group algebras of nilpotent groups: A
complete set of orthogonal primitive idempotents, Finite Fields and Their
Applications, 17, 157–165, 2011.

37

