How to Find the Equivalence Classes in a Set of Linear Codes in Practice?

Abstract

An algorithm for equivalence of linear codes over finite fields is presented. Its main advantage is that it can extract exactly one representative from each equivalence class among a large number of linear codes. It can also be used as a test for isomorphism of binary matrices. The algorithm is implemented in the program LCequivalence, which is designed to obtain the inequivalent codes in a set of linear codes over a finite field with $q<64$ elements. This program is a module of the free software package QextNewEdition for constructing, classifying and studying linear codes.

1. Introduction

Solving classification problems is of interest for both practical and theoretical reasons. Already, Felix Klein in his Erlanger Programm (1872) [1] described mathematics as the study of properties of sets that remain invariant under certain specified groups of transformations. The classification of codes with given parameters and/or properties is one of the main problems in Coding theory. Two equivalent codes are considered to be the same code, and one can replace the other if it is more convenient in the corresponding practical application. For example, we say that there is only one Reed–Muller $[32,16,8]$ binary code, but in fact there are many different codes with these parameters and they are all equivalent to each other. Some algorithms for construction and/or classification of linear codes use the set of all inequivalent codes with smaller parameters and/or given properties. For more theoretical and practical issues of the classification problem we refer to the book of Kaski and Östergård, Classification Algorithms for Codes and Designs [2]. The equivalence test is the main part in any classification algorithm.

In this paper, we describe the algorithm implemented in the program LCequivalence, which can be downloaded from the website [3]. The program uses as input a file with generator matrices of linear codes over a finite field ${\mathbb{F}}_q$ with $q<64$ elements and gives as output a maximum set of inequivalent codes among them. Moreover, it calculates the order of the automorphism group of a codes and presents the orbits of the coordinates with respect to this group.

Although there are many classification results, the known algorithms for equivalence of linear codes that are implemented in a software are the algorithm of J. Leon [4] (implemented in Magma [5] and GAP [6]), the algorithm of Thomas Feulner [7] (implemented in SageMath [8]) and Bouyukliev’s algorithm [9] (implemented in Q-Extension). An algorithm was proposed by N. Sendrier in [10], but his algorithm has mostly theoretical value. There are many papers considering the complexity of the code equivalence problem (we distinguish the papers [11,12]). Each of the respective programs has its advantages and limitations, and in our opinion it is good to have more choice so that users can test and use the software that is most suitable for their particular research.

Leon’s algorithm checks two codes for equivalence and computes automorphism groups. It is implemented in the computer algebra system Magma, which is not freely available, and to compare more codes, a program must be written for it. The same algorithm is implemented in the free computer algebra system GAP, but only for the binary case, i.e., for linear codes over ${\mathbb{F}}_2$. Feulner’s program can only be used via the computer algebra system SageMath (as far as we know), so if one wants to use this algorithm one must be familiar with that system. The algorithm implemented in Q-Extension works with codes over fields with up to 5 elements.

As main advantages of the program LCequivalence, we can point out the following: (1) it can be used to find the inequivalent among a huge number of linear codes; (2) it works for codes over prime and composite fields with $q<64$ elements; (3) the limits on the length and dimension of the considered codes depend only on the used hardware and the computational time (not on the algorithm). As far as we know, there is no other program for the equivalence test of a large number of linear codes. The algorithms implemented in popular packages for computations with linear codes, such as Magma and GAP package GUAVA, check pairs of codes for equivalence, and if the researcher needs to test more codes, he/she has to write a program to use this check.

The main idea of the algorithm is to associate each code (regardless of what field it is over) with a binary matrix, so that two codes are equivalent if and only if the corresponding binary matrices are isomorphic. A similar idea was used in [9], but the problem there is that not every automorphism of the binary matrix used is an automorphism of the code, therefore additional verification is needed.

Algebraically, an equivalence relation can be considered in terms of the action of a finite group G on a set of objects $\Omega$. Then, the equivalence classes coincide with the orbits under this action, so two objects are equivalent if and only if they belong to the same orbit of G on $\Omega$ [2]. The efficiency of some algorithms depends mostly on the order of the group G, and if it is too large, the equivalence test becomes a very hard problem.

We use an algorithm that involves obtaining canonical forms for the objects using a canonical representative map. To check whether $X\cong Y$ we only need to compare their canonical forms. This approach is used in [9,13]. In most cases, algorithms of this type are more efficient and faster.

The paper is organized as follows. In Section 2, we present some important definitions that we need in our research. In Section 3, we discuss the representation of the linear codes as binary matrices. This representation is very important for the algorithm which is described in the following Section 4. Some computational results are shown in Section 5. In the end, before the references, we give a small conclusion.

2. Preliminaries

In this section, we present the most important definitions that we need in our work. By ${\mathbb{F}}_q^n$, we denote the n-dimensional vector space over the finite field ${\mathbb{F}}_q$ with q elements. As a metric, we use the Hamming distance between two vectors of ${\mathbb{F}}_q^n$, which is defined as the number of coordinates in which they differ. Any k-dimensional linear subspace of ${\mathbb{F}}_q^n$ is called a linear code of length n and dimension k. The vectors in a code are called codewords, and the minimum among the distances between two different codewords is called the minimum distance of the code. If a linear code over ${\mathbb{F}}_q$ has length n, dimension k and minimum distance d, we say that it is an ${[n,k,d]}_q$ code. Any matrix of rank k whose rows are codewords from C is called its generator matrix.

Definition 1.

We say that two linear q-ary codes $C_1$ and $C_2$ of the same length and dimension are equivalentif the codewords of $C_2$ can be obtained from the codewords of $C_1$ via a finite sequence of transformations of the following types:

(1) 

Permutation of coordinate positions;

(2) 

Multiplication of the elements in a given position by a non-zero element of the field;

(3) 

Application of a field automorphism to the elements in all coordinate positions.

This definition is well motivated as the transformations (1)–(3) preserve the Hamming distance and the linearity (for more details see [2], Chapter 7.3). It is based on the action of the semilinear isometries group ${\mathcal{M}}_n^{*}\left(q\right)={\mathrm{Mon}}_n\left({\mathbb{F}}_q^{*}\right)⋊\mathrm{Aut}\left({\mathbb{F}}_q\right)\le {\Gamma }_n\left({\mathbb{F}}_q\right)$ on the vector space ${\mathbb{F}}_q^n$, where ${\Gamma }_n\left({\mathbb{F}}_q\right)$ is the set of all semilinear mappings, i.e., the general semilinear group ${\mathrm{Mon}}_n\left({\mathbb{F}}_q^{*}\right)$ is the group of all monomial $n\times n$ matrices over ${\mathbb{F}}_q$, and $\mathrm{Aut}\left({\mathbb{F}}_q\right)$ is the automorphisms group of the field ${\mathbb{F}}_q$. Note that the group ${\mathrm{Mon}}_n\left({\mathbb{F}}_q^{*}\right)$ is isomorphic to the wreath product ${\mathbb{F}}_q^{*}\wr {\mathcal{S}}_n$, and any monomial matrix is a product of a permutation matrix P and a diagonal matrix $D=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(d_1,\dots ,d_n)$, where $d_i\in {\mathbb{F}}_q^{*}$, $i=1,\dots ,n$. Linear q-ary codes $C_1$ and $C_2$ of the same length n are equivalent whenever $C_2=C_{1}T$ for some $T\in {\mathcal{M}}_n^{*}\left(q\right)$. If $CT=C$ for an element $T\in {\mathcal{M}}_n^{*}\left(q\right)$, then T is called an automorphism of the code C. The set of all automorphisms of C form a group denoted by $\mathrm{Aut}\left(C\right)$.

Any element $T\in {\mathcal{M}}_n^{*}\left(q\right)$ can be written as $T=PD\tau$ where P is a permutation matrix (permutation part), D is a diagonal matrix (diagonal part) and $\tau \in Aut\left({\mathbb{F}}_q\right)$. Note that in the case of prime q, ${\mathcal{M}}_n^{*}\left(q\right)={\mathrm{Mon}}_n\left({\mathbb{F}}_q^{*}\right)$, and if $q=2$, then ${\mathcal{M}}_n^{*}\left(q\right)\cong {\mathcal{S}}_n$, where $S_n$ is the symmetric group of degree n.

To construct all inequivalent codes with given parameters means to have one representative of each equivalence class. To easily make a distinction between the equivalence classes, we use the concept for a canonical representative, selected on the base of some specific conditions.

Let G be a group acting on a set $\Omega$. This action defines an equivalence relation such that the equivalence classes are the G-orbits in $\Omega$.

Definition 2.

A canonical representative map for the action of the group G on the set Ω is a function $\rho :\Omega \to \Omega$ that satisfies the following two properties:

1. 

For all $X\in \Omega$ it holds that $\rho \left(X\right)\cong X$;

2. 

For all $X,Y\in \Omega$ it holds that $X\cong Y$ implies $\rho \left(X\right)=\rho \left(Y\right)$.

For $X\in \Omega$, $\rho \left(X\right)$ is called the canonical form of X, and $\rho \left(X\right)$ is the canonical representative of its equivalence class with respect to ρ.

In our case, the set $\Omega$ consists of linear codes, and we can take for a canonical representative of one equivalence class a code which is more convenient for our purposes.

In addition, we use integer-valued invariants. An invariant over the set $\mathbb{E}$ (we use the set of integers $\mathbb{Z}$) is a mapping $f:\Omega \to \mathbb{E}$ such that $f\left(a\right)=f\left(b\right)$ if a and b are in the same orbit with respect to the action of the group G. We use two different actions:

(1)

We take $\Omega$ to be the set of all linear ${[n,k]}_q$ codes (with additional restrictions if needed, for example, only self-orthogonal codes with these parameters or codes with a given minimum and dual distance, etc.) and $G={\mathcal{M}}_n^{*}\left(q\right)$.

(2)

For the second action, we take $\Omega$ to be the set of all codewords of a linear code C, and the group $G=\mathrm{A}\mathrm{u}\mathrm{t}\left(C\right)$. The main invariant that we use in this case is the weight of the codewords.

Finding the canonical form is generally not difficult, but since it is time-consuming, it is important which canonical representation we choose and how we design the algorithm to calculate it. In this work, we do not present a new algorithm for computing canonical forms, but use the algorithm algorithm described in [9]. If the coordinates are previously partitioned according to suitable invariants, the algorithm works much faster. An invariant of the coordinates of C is a function $f:N=\{1,2,\dots ,n\}\to \mathbb{Z}$, such that if i and j are in the same orbit with respect to $\mathrm{A}\mathrm{u}\mathrm{t}\left(C\right)$ then $f\left(i\right)=f\left(j\right)$, $i,j\in N$. The code C and the invariant f define a partition $\pi =\{N_1,N_2,\dots ,N_l\}$ of the coordinate set N, such that $N_i\cap N_j=\varnothing$ for $i\ne j$, $N=N_1\cup N_2\cup \cdots \cup N_l$, and two coordinates $i,j$ are in the same subset of $N\iff f\left(i\right)=f\left(j\right)$. The description of some very effective invariants and the process of their application are detailed in [9,13].

To define pseudoorbits and coloring, we consider a set of invariants for the codewords of C. The automorphism group $\mathrm{A}\mathrm{u}\mathrm{t}\left(C\right)$ acts on the code and partitions the codewords into orbits. All codewords with the same value of an invariant f define a set which consists of one or more orbits called a pseudoorbit. The values of f give an ordering of the pseudoorbits and a coloring of the codewords (the codeword $u\in C$ has color $f\left(u\right)$). The most natural invariant for a codeword is its weight.

As already mentioned, we associate with each q-ary linear code a binary matrix such that two codes are equivalent if and only if the corresponding binary matrices are isomorphic. Therefore, we need a definition for isomorphism of binary matrices.

Definition 3.

Two binary matrices of the same size are isomorphic if the rows of the second one can be obtained from the rows of the first one by a permutation of the columns.

We also use a similar definition for the equivalence of integer matrices.

Definition 4.

Two integer matrices A and B of the same size are isomorphic ($A\cong B$) if the rows of the second one can be obtained from the rows of the first one by a permutation of the columns.

Any permutation of the columns of an integer (or binary) matrix A which maps the rows of A into the rows of the same matrix is called an automorphism of A. The set of all automorphisms of A is a subgroup of the symmetric group ${\mathcal{S}}_n$, denoted by $\mathrm{A}\mathrm{u}\mathrm{t}\left(A\right)$.

3. Representing the Objects

To check codes for equivalence, we need (1) to find a proper set $M\left(C\right)$ of codewords, (2) to set a binary matrix $GM\left(C\right)$ corresponding to $M\left(C\right)$ (if the code is not binary) and (3) to compute the canonical form of $GM\left(C\right)$. The set $M\left(C\right)$ of codewords of the code C must have the following properties:

• $M\left(C\right)$ generates the code C;
• $M\left(C\right)$ is stable with respect to $Aut\left(C\right)$;
• If $C^{\prime }\cong C^{″}$ and $\sigma \left(C^{\prime }\right)=C^{″}$ then $\sigma \left(M\left(C^{\prime }\right)\right)\equiv M\left(C^{″}\right)$, $\sigma \in {\mathcal{M}}_n^{*}$.

We begin with an algorithm for finding a proper set $M\left(C\right)$:

• Initialization: $M\left(C\right)=\varnothing$;
• generate the set D of all codewords with smallest not considered weight;
• Find and order pseoudoorbits $\{O_1,O_2,\dots ,O_l\}$ of D according to the value of the applied invariant;
• For r from 1 to l do the following:
  If $\mathrm{rank}(M\left(C\right)\bigcup O_r)>\mathrm{rank}\left(M\left(C\right)\right)$, then $M\left(C\right)=M\left(C\right)\bigcup O_r$;
• If $\mathrm{rank}\left(M\right(C\left)\right)<\mathrm{rank}\left(C\right)$, then go to point 2 else return.

Since the set $M\left(C\right)$ is stable under the action of the automorphism group of the code, together with each vector it contains all its proportional vectors. Let $Mt$ be a $(q-1)s\times n$ matrix whose rows are the codewords from the set $M\left(C\right)$. For any column v of this matrix we add all its proportional column vectors and thus construct the matrix $M{t}_{ext}$ with the same number of $(q-1)s$ rows but $(q-1)n$ columns. If the codes $C^{\prime }$ and $C^{″}$ are equivalent then there is a monomial matrix $M\in {\mathrm{Mon}}_n\left({\mathbb{F}}_q^{*}\right)$ and an automorphism of the field $\varphi$ such that $vM\varphi \in C^{″}$ for any codeword $v\in C^{\prime }$. It turns out that $M{t}^{\prime }·M\varphi =P·M{t}^{″}$, where P is a permutation matrix that permutes the rows of $M{t}^{″}$. Since in the definition for equivalence of integer matrices we use only permutations (resp. permutation matrices), we consider the matrices $M{t}_{ext}^{\prime }$ and $M{t}_{ext}^{″}$. If we map the monomial matrix M to the permutation $(q-1)n\times (q-1)n$ matrix $P_M$ by replacing any element with a $(q-1)\times (q-1)$ matrix in the following way:

$$0\mapsto \mathrm{c}\mathrm{i}\mathrm{r}\mathrm{c}(00\dots 0),{\alpha }^i\mapsto \mathrm{c}\mathrm{i}\mathrm{r}\mathrm{c}(0\dots 0\underset{i}{\underbrace{ 1 }}0\dots 0)\mathrm{f}\mathrm{o}\mathrm{r}i=0,1,\dots ,q-2,$$

(1)

we have $M{t}_{ext}^{\prime }·P_M\varphi =P·M{t}_{ext}^{″}$. This gives us that

$$P_M^T·M{t}_{ext}^{\prime T}\varphi =M{t}_{ext}^{″T}·P^T\Rightarrow M{t}_{ext}^{\prime T}·{\left(P^T\right)}^{-1}\varphi ={\left(P_M^T\right)}^{-1}·M{t}_{ext}^{″T}.$$

This means that instead of the matrices $M{t}_{ext}^{\prime }$ and $M{t}_{ext}^{″}$, we can use their transpose matrices, which is important if $s<n$.

Example 1.

The ternary codes $C^{\prime }=\langle \left(\begin{array}{ccc}1& 0& 1\\ 0& 1& 2\end{array}\right)\rangle$ and $C^{″}=\langle \left(\begin{array}{ccc}1& 0& 2\\ 0& 1& 2\end{array}\right)\rangle$ are equivalent and the monomial matrix $M=\left(\begin{array}{ccc}0& 0& 2\\ 1& 0& 0\\ 0& 1& 0\end{array}\right)$ maps the codewords of $C^{\prime }$ to codewords of $C^{″}$. We take

$$M{t}^{\prime }=\left(\begin{array}{ccc}1& 0& 1\\ 2& 0& 2\\ 0& 1& 2\\ 0& 2& 1\\ 1& 1& 0\\ 2& 2& 0\end{array}\right),M{t}^{″}=\left(\begin{array}{ccc}1& 0& 2\\ 2& 0& 1\\ 0& 1& 2\\ 0& 2& 1\\ 1& 2& 0\\ 2& 1& 0\end{array}\right),M{t}^{\prime }\left(\begin{array}{ccc}0& 0& 2\\ 1& 0& 0\\ 0& 1& 0\end{array}\right)=\left(\begin{array}{cccccc}0& 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\end{array}\right)M{t}^{″},$$

$$M{t}_{ext}^{\prime }=\left(\begin{array}{cccccc}1& 2& 0& 0& 1& 2\\ 2& 1& 0& 0& 2& 1\\ 0& 0& 1& 2& 2& 1\\ 0& 0& 2& 1& 1& 2\\ 1& 2& 1& 2& 0& 0\\ 2& 1& 2& 1& 0& 0\end{array}\right),M{t}_{ext}^{″}=\left(\begin{array}{cccccc}1& 2& 0& 0& 2& 1\\ 2& 1& 0& 0& 1& 2\\ 0& 0& 1& 2& 2& 1\\ 0& 0& 2& 1& 1& 2\\ 1& 2& 2& 1& 0& 0\\ 2& 1& 1& 2& 0& 0\end{array}\right).$$

We take only one representative of each class of proportional vectors and thus obtain the set $M^{\prime }\left(C\right)$. To define the binary matrix $GM\left(C\right)$ that corresponds to the set $M^{\prime }\left(C\right)$, we consider the cases $q=2$ and $q\ge 3$ separately.

Consider first the binary case. Let $GM\left(C\right)$ be a binary matrix whose rows are the codewords from $M\left(C\right)$.

Theorem 1.

The binary $[n,k]$ codes $C_1$ and $C_2$ are equivalent if and only if the binary matrices $GM\left(C_1\right)$ and $GM\left(C_2\right)$ are isomorphic.

Proof. 

Let the binary codes $C_1$ and $C_2$ be equivalent. Hence, there is a permutation $\sigma \in {\mathcal{S}}_n$ such that $\sigma \left(C_1\right)=C_2$. It follows that $\sigma \left(M\left(C_1\right)\right)=M\left(C_2\right)$, therefore the matrices $GM\left(C_1\right)$ and $GM\left(C_2\right)$ are isomorphic.

Let $GM\left(C_1\right)\cong GM\left(C_2\right)$. Then, there is a permutation $\tau \in {\mathcal{S}}_n$ such that the matrices $\tau \left(GM\left(C_1\right)\right)$ and $GM\left(C_2\right)$ have the same rows but are ordered differently. Hence, $\tau$ maps the codewords from $M\left(C_2\right)$ to codewords in $M\left(C_2\right)$, therefore the codes $C_1$ and $C_2$ are equivalent.    □

Representing a linear code over a field with more than two elements as a binary matrix is already introduced in [9,14], but here we present a different approach which is more general and more suitable for codes over fields with $q\ge 5$ elements.

Let C be a q-ary linear code for with $q=p^m\ge 3$, where p is a prime, and let $\alpha$ be a primitive element of ${\mathbb{F}}_q$. We map each element of ${\mathbb{F}}_q$ to a circular binary matrix of order $q-1$ in the same way as shown in (1).

Consider the matrix $M{t}^{\prime }\left(C\right)$ whose rows are the codewords from $M^{\prime }\left(C\right)$ for the q-ary linear code C of length n. Replacing all elements in $Mt\left(C\right)$ using (1), we obtain the matrix $GM\left(C\right)$ of size $(q-1)s\times (q-1)n$ where $s=|M^{\prime }\left(C\right)|$. Note that this presentation includes also the proportional vectors of the codewords in $M^{\prime }\left(C\right)$ and $(q-1)s=\left|M\right(C\left)\right|$.

To construct the needed binary matrix, we use some additional matrices that depend on the field. Denote the $(q-1)\times (q-1)$ circulant $\mathrm{c}\mathrm{i}\mathrm{r}\mathrm{c}(010\dots 0)$ by L and let

$$A^{*}=I_{q-1}+2(L+L^p+\cdots +L^{p^{m-1}}).$$

The automorphism group of this matrix is $\mathrm{A}\mathrm{u}\mathrm{t}\left(A^{*}\right)=\langle \sigma ,\tau \rangle <{\mathcal{S}}_{q-1}$, where $\sigma =(0,1,\dots ,$$q-2)$ is the presented cycle of length $q-1$, and $\tau ={\Omega }_1\dots {\Omega }_t$, where ${\Omega }_i$ corresponds to the i-th ciclotomic class modulo $q-1$. This group is isomorphic to ${\mathbb{F}}_q^{*}⋊\mathrm{Aut}\left({\mathbb{F}}_q\right)$ which is the automorphism group of the trivial ${[1,1]}_q$ code. We prove this isomorphism in detail in the following lemma.

Lemma 1.

$Aut\left(A^{*}\right)\cong {\mathbb{F}}_q^{*}⋊Aut\left({\mathbb{F}}_q\right)$.

Proof. 

Let us label the rows and the columns of the matrix $A^{*}$ from 0 to $q-2$. We first consider the case of a prime $q\ge 3$. Then the i-th row of $A^{*}$ is

$$(0,\dots ,0,\underset{i}{\underbrace{ 1 }},\underset{i+1}{\underbrace{ 2 }},0,\dots ,0),\mathrm{for}0\le i\le q-3,$$

and $(2,0,\dots ,0,1)$ if $i=q-2$. The j-th column is ${(1,0,\dots ,0,2)}^T$ if $j=0$, and

$$(0,\dots ,0,\underset{j-1}{\underbrace{ 2 }},\underset{j}{\underbrace{ 1 }},0,\dots ,0),\mathrm{if}1\le j\le q-2.$$

Now, take a permutation $\tau \in \mathrm{A}\mathrm{u}\mathrm{t}\left(A^{*}\right)\le {\mathcal{S}}_{q-1}$. If $\tau \left(0\right)=j$, then the column with number 0 goes to the j-th column. This column contains only one coordinate equal to 1 and this 1 is on the j-th row which contains only one coordinate equals to 2, namely the $j+1$-th coordinate. Hence, $\tau \left(1\right)=j+1$. Considering the $j+1$-th column and the positions of the coordinates equal to 1 and 2, we have $\tau \left(i\right)=j+i(modq-1)$. Hence, $\tau ={(0,1,\dots ,q-2)}^j$ and $\mathrm{A}\mathrm{u}\mathrm{t}\left(A^{*}\right)=\langle (0,1,\dots ,q-2)\rangle \cong {\mathbb{F}}_q^{*}$.

Let us now consider the general case when $q=p^m$ for a prime p and integer $m\ge 1$. In this case, if $A^{*}=\left(a_{ij}\right)$, $0\le i,j\le q-2$, then $a_{ii}=1$ for all $i=0,1,\dots ,q-2$, and $a_{ij}=2$ if $j=i+p^s(modq-1)$, $s=0,1,\dots ,m-1$. We can consider any automorphism $\tau \in Aut\left(A^{*}\right)\le {\mathcal{S}}_{q-1}$ as a permutation of the nonzero elements of the field. If $\tau \left({\alpha }^0\right)={\alpha }^i$, the row with number 0 goes to the i-th row. This means that

$${\{\alpha ,{\alpha }^p,\dots ,{\alpha }^{p^{m-1}}\}}^{\underrightarrow{\tau }}\{{\alpha }^{i+1},{\alpha }^{i+p},\dots ,{\alpha }^{i+p^{m-1}}\}$$

(these are the positions of the coordinates equal to 2 in these two rows). But then, $\tau \left(\alpha \right)={\alpha }^{i+p^{s_1}}$ and the number 1 row goes to row with number $i+p^{s_1}$ and therefore

$${\{{\alpha }^2,{\alpha }^{1+p},\dots ,{\alpha }^{1+p^{m-1}}\}}^{\underrightarrow{\tau }}\{{\alpha }^{1+i+p^{s_1}},{\alpha }^{i+p^{s_1}+p},\dots ,{\alpha }^{i+p^{s_1}+p^{m-1}}\}.$$

Hence, $\tau \left({\alpha }^2\right)={\alpha }^{i+p^{s_1}+p^{s_2}}$. Then,

$${\{{\alpha }^3,{\alpha }^{2+p},\dots ,{\alpha }^{2+p^{m-1}}\}}^{\underrightarrow{\tau }}\{{\alpha }^{1+i+p^{s_1}+p^{s_2}},{\alpha }^{i+p^{s_1}+p^{s_2}+p},\dots ,{\alpha }^{i+p^{s_1}+p^{s_2}+p^{m-1}}\}.$$

Thus, $\tau \left({\alpha }^3\right)={\alpha }^{i+p^{s_1}+p^{s_2}+p^{s_3}}$. In this way we obtain that $\tau \left({\alpha }^p\right)={\alpha }^{i+p^{s_1}+p^{s_2}+\dots +p^{s_p}}$. But at the same time, $\tau \left({\alpha }^p\right)={\alpha }^{i+p^r}$ and so ${\alpha }^{i+p^{s_1}+p^{s_2}+\cdots +p^{s_p}}={\alpha }^{i+p^r}$. It follows that

$${\alpha }^{p^{s_1}+p^{s_2}+\cdots +p^{s_p}-p^r}=1\Rightarrow p^m-1\mid p^{s_1}+p^{s_2}+\cdots +p^{s_p}-p^r.$$

But $s_j\le m-1$, $j=1,\dots ,p$, and $r\ge 0$, thus $p^{s_1}+p^{s_2}+\cdots +p^{s_p}-p^r\le p^m-1$. Hence, $p^{s_1}+p^{s_2}+\cdots +p^{s_p}-p^r=0$ or $p^m-1$. It turns out that $s_1=s_2=\cdots =s_p=s$, $r=s+1$, and $\tau \left({\alpha }^j\right)={\alpha }^{i+j{p}^s}$ for $j=0,1,\dots ,q-2$ which means that $\tau ={\sigma }^i{\varphi }^s\in G$, where $\sigma =(0,1,2,\dots ,q-2)$ and $\varphi$ is the Frobenius automorphism defined by $\varphi \left(a\right)=a^p$, $a\in {\mathbb{F}}_q$. It follows that $\mathrm{Aut}\left(A^{*}\right)\cong \langle \sigma ,\varphi \rangle \cong {\mathbb{F}}_q^{*}⋊\mathrm{Aut}\left({\mathbb{F}}_q\right)$.    □

We give two examples with the matrices $A^{*}$.

Example 2.

Consider the cases $q=5$ and $q=8$:

(1) 

If $q=5$ we have $A^{*}=\mathrm{circ}\left(1200\right)=\left(\begin{array}{cccc}1& 2& 0& 0\\ 0& 1& 2& 0\\ 0& 0& 1& 2\\ 2& 0& 0& 1\end{array}\right)$, $Aut\left(A^{*}\right)=\langle \left(0123\right)\rangle <{\mathcal{S}}_4$;

(2) 

If $q=8$ then $A^{*}=\mathrm{circ}\left(1220200\right)=\left(\begin{array}{ccccccc}1& 2& 2& 0& 2& 0& 0\\ 0& 1& 2& 2& 0& 2& 0\\ 0& 0& 1& 2& 2& 0& 2\\ 2& 0& 0& 1& 2& 2& 0\\ 0& 2& 0& 0& 1& 2& 2\\ 2& 0& 2& 0& 0& 1& 2\\ 2& 2& 0& 2& 0& 0& 1\end{array}\right)$,

$Aut\left(A^{*}\right)=\langle \left(0123456\right),\left(124\right)\left(365\right)\rangle <{\mathcal{S}}_7$, $\left|Aut\right(A^{*}\left)\right|=21$.

Next, we replace the elements 0, 1 and 2 in the matrix $A^{*}$ with binary column-vectors with two coordinates as follows:

$$0\mapsto \left(\genfrac{}{}{0pt}{}{0}{0}\right),1\mapsto \left(\genfrac{}{}{0pt}{}{1}{0}\right),2\mapsto \left(\genfrac{}{}{0pt}{}{1}{1}\right)$$

and in this way from the matrix $A^{*}$ we construct the matrix $B^{\prime }$. To have a matrix with an automorphism group which is isomorphic to $\mathrm{Aut}\left(A^{*}\right)$, we expand $B^{\prime }$ with the columns of the matrix $I_{q-1}\otimes \left(\genfrac{}{}{0pt}{}{1}{1}\right)$, and denote the obtained matrix by $B^{*}$.

Example 3.

Consider again the case $q=5$. Then,

$$B^{*}=\left(\begin{array}{cccccccc}1& 1& 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 1& 0& 0& 0\\ 0& 1& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 1& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0& 1\end{array}\right)$$

Recall that $\mathrm{Aut}\left(A^{*}\right)=\langle \sigma ,\tau \rangle$. Let us map $\sigma \in {\mathcal{S}}_{q-1}$ to the permutation ${\sigma }^{\prime }=(0,1,\dots ,q-2)(q-1,q,\dots ,2q-3)\in {\mathcal{S}}_{2q-2}$, and $\tau$ to ${\tau }^{\prime }={\Omega }_1\dots {\Omega }_t{\Omega }_1^{\prime }\dots {\Omega }_t^{\prime }\in {\mathcal{S}}_{2q-2}$ where ${\tau }^{\prime }$ is defined as follows: if ${\Omega }_i=(j_1,\dots ,j_{m_i})$ then ${\Omega }_i^{\prime }=(q-1+j_1,\dots ,q-1+j_{m_i})$, $i=1,\dots ,t$. This map defines an isomorphism between $\mathrm{Aut}\left(A^{*}\right)$ and $\mathrm{Aut}\left(B^{*}\right)$, and so $\mathrm{Aut}\left(B^{*}\right)\cong {\mathbb{F}}_q^{*}⋊\mathrm{Aut}\left({\mathbb{F}}_q\right)$.

We need two more square matrices, namely the $(q-1)n\times (q-1)n$ matrix $A=I_n\otimes A^{*}$ and the $2(q-1)n\times 2(q-1)n$ matrix $B=(I_n\otimes B^{\prime }|I_{(q-1)n}\otimes \left(\genfrac{}{}{0pt}{}{1}{1}\right))$. The automorphism groups of these two matrices are isomorphic to ${\mathcal{M}}_n^{*}\left(q\right)$.

Now expand the matrix $GM\left(C\right)$ by adding the rows of the matrix A. In this way we obtain the matrix $G{M}_A\left(C\right)=\left(\genfrac{}{}{0pt}{}{GM\left(C\right)}{A}\right)$ with $(q-1)(s+n)$ rows and $(q-1)n$ columns.

Example 4.

Consider the ${[2,1]}_5$ code C with a generator matrix $\left(12\right)$. For this code

$$G{M}_A\left(C\right)=\left(\begin{array}{cccccccc}1& 0& 0& 0& 0& 1& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 0\\ 0& 0& 1& 0& 0& 0& 0& 1\\ 0& 0& 0& 1& 1& 0& 0& 0\\ 1& 2& 0& 0& 0& 0& 0& 0\\ 0& 1& 2& 0& 0& 0& 0& 0\\ 0& 0& 1& 2& 0& 0& 0& 0\\ 2& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 2& 0& 0\\ 0& 0& 0& 0& 0& 1& 2& 0\\ 0& 0& 0& 0& 0& 0& 1& 2\\ 0& 0& 0& 0& 2& 0& 0& 1\end{array}\right)$$

The automorphism group of the matrix A is isomorphic to ${\mathcal{M}}_n^{*}\left(q\right)$ and therefore $\mathrm{Aut}\left(G{M}_A\left(C\right)\right)<\mathrm{Aut}\left(A\right)$ and consists of those automorphisms of A which belong to $\mathrm{Aut}\left(GM\right(C\left)\right)$.

Example 5.

Consider the code from Example 4. If we swap the two coordinates and then multiply the second coordinate by 4, we obtain the same code. Hence, the monomial matrix $\left(\begin{array}{cc}0& 4\\ 1& 0\end{array}\right)$ belongs to the automorphism group of this code. We map this monomial matrix to the permutation matrix

$$Q_A=\left(\begin{array}{cccccccc}0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0\end{array}\right).$$

It is easy to see that the matrix $G{M}_A\left(C\right)Q_A$ has the same rows as the matrix $G{M}_A\left(C\right)$ and so $Q_A\in Aut\left(G{M}_A\left(C\right)\right)$.

The matrices $GM\left(C\right)$ and $G{M}_A\left(C\right)$ are related to the matrix $G{M}_B\left(C\right)$ which we construct in the following way: (1) we glue the $(q-1)s\times (q-1)n$ zero matrix to the matrix $GM\left(C\right)$; (2) we add the rows of B. The obtained matrix has $(q-1)(s+2n)$ rows and $2(q-1)n$ columns.

Example 6.

Consider the same ${[2,1]}_5$ code C with a generator matrix $\left(12\right)$. For this code

$$G{M}_B\left(C\right)=\left(\begin{array}{cccccccccccccccc}1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ 1& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0\\ 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 0& 1& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& 1\end{array}\right)$$

Theorem 2.

The q-ary $[n,k]$ codes $C_1$ and $C_2$ are equivalent if and only if the binary matrices $G{M}_B\left(C_1\right)$ and $G{M}_B\left(C_2\right)$ are isomorphic.

Proof. 

In converting the matrix $Mt\left(C\right)$ to the matrix $G{M}_B\left(C\right)$, we replace each column with a group of $(q-1)$ columns and then extend the obtained matrix with extra zero columns and the rows of the matrix B. Therefore, there is a one-to-one correspondence between the permutations of the coordinates of C and the permutations of the corresponding groups of columns in $G{M}_B\left(C\right)$. More precisely, if $\tau \in {\mathcal{S}}_n$ is a permutation of the n coordinates of C, it goes to the permutation ${\tau }_B\in {\mathcal{S}}_{2(q-1)n}$ of the columns of $G{M}_B\left(C\right)$ such that if $\tau \left(j\right)=i_j$ then ${\tau }_B((q-1)j-j_1)=(q-1)i_j-j_1$ and ${\tau }_B((q-1)(n+j)-j_1)=(q-1)(n+i_j)-j_1$ for $1\le j\le n$, $0\le j_1\le q-2$. Moreover, the multiplication of a coordinate by ${\alpha }^i$ can be considered as applying the permutation $\sigma =(0,1,\dots ,q-2)$ on the corresponding group of $2(q-1)$ columns i times. The automorphism of the field applied to all coordinates of all codewords also can be considered as a permutation of the columns of $G{M}_B\left(C\right)$.

The above observation shows that if $\phi \in {\mathcal{M}}_n{\left(q\right)}^{*}$ maps the code $C_1$ to $C_2$, then the corresponding to $\phi$ permutation of the columns of $G{M}_B\left(C_1\right)$ maps the rows of this matrix to the rows of $G{M}_B\left(C_2\right)$. Note that $\varphi$ can be considered as a permutation followed by multiplications of the coordinates of the code by nonzero elements of the field and eventually applying an automorphism of the field to all coordinates of all codewords.

Conversely, if we take a permutation $\pi$ of the columns of $G{M}_B\left(C_1\right)$ that maps the rows of this matrix to the rows of $G{M}_B\left(C_2\right)$, then $\pi \in \mathrm{Aut}\left(B\right)\cong {\mathcal{M}}_n^{*}\left(q\right)$ and $\pi$ maps the rows of $G{M}^{\prime }\left(C_1\right)$ to the rows of $G{M}^{\prime }\left(C_2\right)$.    □

Corollary 1.

$Aut\left(C\right)\cong Aut\left(G{M}_B\left(C\right)\right)$.

Example 7.

The automorphism group of the code $C=\langle (1,2)\rangle \subset {\mathbb{F}}_5^2$ is

$$Aut\left(C\right)=\{\beta I_2,\beta \left(\begin{array}{cc}0& 4\\ 1& 0\end{array}\right),\beta \in {\mathbb{F}}_5^{*}\},\left|Aut\left(C\right)\right|=8.$$

According to Corollary 1, $Aut\left(C\right)\cong Aut\left(G{M}_B\left(C\right)\right)$. Indeed,

$$Aut\left(G{M}_B\left(C\right)\right)=\langle (1,2,3,4)(5,6,7,8)(9,10,11,12)(13,14,15,16),$$

$$(1,7,3,5)(2,8,4,6)(9,15,11,13)(10,16,12,14)\rangle \cong Aut\left(C\right).$$

Calculating $\left|Aut\right(GM\left(C\right)\left)\right|=384$, $\left|Aut\right(G{M}_A\left(C\right)\left)\right|=8$, $\left|Aut\right(G{M}_{B^{\prime }}\left(C\right)\left)\right|=48$, where $G{M}_{B^{\prime }}\left(C\right)$ is the matrix $G{M}_B\left(C\right)$ without the last $n(q-1)$ columns, we see that the extra rows and columns are important to remove the automorphisms of the matrices that do not correspond to automorphisms of the code.

4. The Algorithm

The classification problem we want to solve is the following: given a set of linear q-ary codes of length n and dimension k, take only one representative of each equivalence class. We present the algorithm that gives a solution of the problem. As an input, we have a family of linear codes presented by a generator matrix. The set of these matrices is denoted by W. As an output, we have one representative of each equivalence class with respect to the defined (in the previous sections) equivalence relation in the set of linear codes. Generator matrices of these representatives compose the set U. The algorithm follows these steps:

• We find a generating set $M\left(C\right)$ for each code C. In most cases this is the set of codewords with minimum weight. If this set has a rank smaller than k, we add the codewords with another weight, etc. In some cases we also use other invariants to get a smaller and more convenient generating set.
• We take the binary matrix $G{M}_B\left(C\right)$ as it is described in the previous section. According to Theorem 2, two codes $C_1$ and $C_2$ are equivalent if and only if $G{M}_B\left(C_1\right)\cong G{M}_B\left(C_2\right)$.
• We find the canonical form of the matrix $G{M}_B\left(C\right)$ as it is described in [9].
• We compare the canonical forms of the matrices. If two matrices have the same canonical form, they are isomorphic and the corresponding codes are equivalent. If these matrices have different canonical forms, the codes are not equivalent.

A pseudocode of Algorithm 1 is given below.

Algorithm 1 Procedure Find_Inequivalent_Codes

Input:  A set W of generator matrices of linear codes. Output:  A maximal set $U\subseteq W$ of generator matrices of inequivalent codes.       var       HA: array of integers;       Hf: file;       not_found: boolean;   1: Initialize Hf;   2: $HA\left[i\right]\leftarrow 0$ for all $i=0,\dots ,size$;   3: for each generator matrix $G\in W$ do   4:    Find generating set $M\left(C\right)$ of the corresponding linear code C;   5:    construct the corresponding binary matrix $G{M}_B\left(C\right)$;   6:    find the canonical form A the matrix $G{M}_B\left(C\right)$ and its hash value $h\left(A\right)$;   7:    call the procedure SEARCH_IN_HASH_TABLE with parameters $HA$, A, $h\left(A\right)$, $Hf$    {the procedure gives the value of the boolean variable $not\_found$ which is true or false}   8:    if $not\_found$ then   9:    $U\leftarrow U\cup \left\{G\right\}$ 10:    end if 11: end for

For fast search between a large number of similar objects (in our case, binary matrices in canonical form), an abstract data structure known as a hash map is used (more information about hash tables and hash maps can be found in [15,16]). It consists of three components: a hash array, a hash function and a hash table or file. The basic idea is that when we get a new code, we first compare its hash with the hash values of already considered codes. If the new hash is different from all already computed, the new code is not equivalent to either of the previous codes. If the hash is equal to the hash value of another code, then we compare the corresponding binary matrices.

Let us introduce the hashing we use in a little more detail. A hash array $HA\left[\right]$ can be considered as an array of non-negative integers. To any object, the hash function associates an integer, which can be considered as an index in the hash array $HA\left[\right]$. Each element of the array $HA\left[i\right]$ (if $HA\left[i\right]\ne 0$) is a pointer (a positive integer) to the location of the object in a hash file or table. In the beginning, all values in the array $HA$ are 0s. We define a hash file as an addressable memory of a large size that consists of cells. Objects or records (that contain an object) can be written in these cells. A binary file which has direct access, or a dynamic structure (if enough RAM is available), can serve as the hash file (hash table).

We use a non-cryptographic hash function h that maps an object of arbitrary size to a positive integer not larger than the size of the hash array. If the number of different matrices we examine is greater than the size of the hash array, there will be at least two matrices with the same hash value, which is called a collision. The hash function h must meet the following requirements:

• The function should be easily and quickly calculated.
• It should provide a uniform distribution in the hash array. In this case, the number of collisions will be smaller. Even with a very good hash function, collisions are not excluded. The collision handling technique which we use is known as Separate Chaining (Open Hashing). It is usually implemented using linked lists. A nonzero cell of the hash array points to the first object in a linked list of objects that have the same hash value (if no matches with the same hash value are found, the list consists of one element).

An implementation of this approach is presented in Algorithm 2.

The total complexity of the main algorithm depends on the size of the set of codes (the set W consists of their generator matrices) but is difficult to determine because it depends on many subalgorithms. For codes with large dimension, one of the most expensive parts is the generating a proper set $M\left(C\right)$ of codewords. In this case, a more efficient approach than the standard brute force algorithm (with Gray code) gives the Brouwer–Zimmermann algorithm and its modifications [17]. The construction of the binary matrix $G{M}_B\left(C\right)$, which corresponds to the set $M\left(C\right)$, despite its theoretical complexity, practically does not affect the execution time of the algorithm. Finding the canonical form of a binary matrix represents the solution to the graph isomorphism problem, since in this case a bipartite graph is considered. The computation time required depends on whether the binary matrix corresponds to a regular structure such as a combinatorial design and does not particularly depend on the order of the automorphism group. The use of a canonical form reduces the isomorphism problem between binary matrices to a matrix comparison problem which has complexity fixed by the matrix parameters and negligible execution time. In the case of a large number m of non-equivalent matrices, if a hash map is not used, the complexity of comparing a matrix with the others becomes linear with respect to m, and when a hash map is used, the complexity is reduced to a constant.

Algorithm 2 Procedure SEARCH_IN_HASH_TABLE

Input:  $hashkey=h\left(A\right)$, the matrix A, the integer array $HA$, the file $Hf$ Output:  $not\_found$: boolean;     type      structure MATREC {       matrix M;          integer $Next$}    // next matrix with the same hashkey     var       $AMATREC$, $BMATREC$ of type MATREC;      $curent\_position$, $old\_position$: integer;   1: $AMATREC.M\leftarrow A$;   2: $AMATREC.next\leftarrow 0$;   3: if $HA\left[hashkey\right]=0$ then   4:    append $AMATREC$ to the file $Hf$;   5:    $HA\left[hashkey\right]\leftarrow$ the position of $AMATREC$ in the file $Hf$;   6:    return $not\_found\leftarrow true$   7: else   8:    $curent\_position\leftarrow HA\left[hashkey\right]$;   9:    while $curent\_position\ne 0$ do 10:    $old\_position\leftarrow curent\_position$; 11:    read from $curent\_position$ the structure $BMATREC$ {from the file $Hf$}; 12:    $curent\_position\leftarrow BMATREC.next$ 13:    if $AMATREC.M=BMATREC.M$ then 14:    return $not\_found\leftarrow false$ 15:    end if 16:    end while 17:    append $AMATREC$ to the file $Hf$; 18:    $curent\_position\leftarrow$ the first position of $AMATREC$ in the file $Hf$; 19:    $BMATREC.Next\leftarrow curent\_position$; 20:    write from $old\_position$ the structure $BMATREC$ to the file $Hf$ 21:    return $not\_found\leftarrow true$; 22: end if

5. Computational Results

We made some experiments with codes with different lengths and dimensions over different finite fields.

In

Table 1. Execution times (in seconds) for obtaining inequivalent codes in a set of randomly constructed linear codes with the program LCequivalence.

n	k	q	Number of Codes	Number of Inequivalent Codes	Time in Seconds	Comment
20	10	2	100,000	65,566	39.47	random
40	20	2	10,000	10,000	89.25	random
120	40	2	100	100	336.98	quasi-cyclic
120	40	2	100	100	214.34	random
28	14	3	6931	6931	15,386.21	self-dual
60	16	4	100	100	231.30	random
5000	10	4	1000	1000	153.91	random
16	8	5	535	535	33.187	self-dual
12	6	7	64	64	0.30	self-dual
40	20	7	2	1	12.44	self-dual
56	28	7	2	1	25,161.18	self-dual
15	3	9	1,000,000	4115	621.85	quasi-cyclic
20	10	16	1000	1000	9.87	random
20	10	17	1000	1000	17.33	random
20	10	23	1000	1000	110.38	random
1000	5	31	100	100	110.39	random
10	3	32	10,000	9999	167.81	random
20	10	61	100	100	80.59	random

, we present the execution times for obtaining inequivalent codes. In the table, we have presented results in the following cases, which we consider to be significant:

• Finding the inequivalent codes in a set of randomly constructed linear codes. This is useful for the process of generating linear codes of a given type and/or given parameters. During the intermediate steps in the generation process, a large amount of codes is usually constructed, from which only the inequivalent ones should be taken and the procedure continued with them. As an example, we can mention one of the methods for isomorph-free exhaustive generation, namely isomorph rejection based on recorded objects [2].
• One of the most important classes of linear codes for theoretical and practical reasons is the class of self-dual codes. A self-dual code over ${\mathbb{F}}_q$ is a linear code which coincides with its orthogonal complement in the vector space ${\mathbb{F}}_q^n$ with respect to a given inner product [18]. The study of these codes involves the generation and classification of self-dual codes over a given finite field with prescribed length, minimum distance and other parameters such as a weight enumerator or an automorphism group (see, for example, [19]). Therefore, we have included in the table results on this type of codes over fields with 3, 5 and 7 elements.
• The quasi-cyclic codes have nontrivial automorphism groups that contain as a subgroup a cyclic group of a given order (see [18] for more details about these codes). This is the reason why we also consider these types of codes and include a special option in the LCequivalence program to generate random quasi-cyclic codes.

Table 1 is structured as follows. The first three columns contain the parameters n (length), k (dimension) and q (size of the field) of the constructed ${[n,k]}_q$ codes. In the fourth column we present the number of constructed codes that will be checked for equivalence. The next column contains the number of the inequivalent codes in the given set of codes. The execution time is shown in the sixth column. In the last column we comment on whether the constructed codes are of special types, for example self-dual or quasi-cyclic.

The computations were executed on a Windows 11 OS in a single core of an Intel Xeon Gold 5118 CPU with a 2.30 GHz clock frequency.

The program LCequivalence has two options for constructing random codes—for given positive integers ℓ, n, k, d and q, (1) constructing ℓ random linear ${[n,k,\ge d]}_q$ codes and (2) constructing ℓ random quasi-cyclic ${[n,k,\ge d]}_q$ codes. We have provided this option so that we can test a large number of random codes for equivalence. The self-dual codes that we check for equivalence are taken from the Database of self-dual codes by Masaaki Harada and Akihiro Munemasa [20].

As input we use generator matrices of the considered codes. The program then goes through the four steps presented in Section 4 and takes exactly one representative from each equivalence class. Generator matrices of these representatives, as well as additional information about them (parameters, automorphism groups, orbits, etc.), are written to a file.

6. Conclusions

This paper is devoted to the algorithm for equivalence of linear codes over finite fields implemented in the program LCequivalence, which is a module of the software package QextNewEdition v1.1 [3]. The program takes as input a file with generator matrices of linear codes and gives as output a file with generator matrices for the maximum set of inequivalent among the input codes. Using this program, one can test for equivalence codes over fields with $q<64$ elements. As can be seen in Table 1, the file may contain large number of codes. As far as we know, there is no other program for the equivalence test of a large number of linear codes. The algorithms implemented in the popular packages that deal with linear codes check pairs of codes for equivalence.

Instead of linear codes, the program LCequivalence can test binary matrices for equivalence. This means that it can be used for equivalence (isomophism) testing of objects that can be represented by binary matrices including graphs [14].

The program also gives the orders and generators of the automorphism groups of the corresponding binary matrices. Optionally, by marking the corresponding option, the program can also write additional information to the output file, such as a permutation that leads one matrix to its equivalent, orbits, weight distributions of the codes, etc.

No installation of the program is required. It is only necessary for the user to create a directory and download a version of the program that corresponds to the operating system used—Linux or Windows. The interface is very simple. The user can choose from the following seven options:

• Find inequivalent codes.
• Find inequivalent matrices.
• What to print in the output file about codes?
• What to print in the output file about matrices?
• Change the name of the input file.
• Random codes (will be written in a file with name EXAM in the directory RES_DIR0).
• Random quasi-cyclic codes (will be written in a file with name EXAM in the directory RES_DIR0).

As an input the program LCequivalence uses a text file with generator matrices of linear codes in the form described in the previous version of Q-Extension. There is no limit to the number of codes in the input file.