On the equivalence between additive and linear codes

1. Problem Statement

Additive codes over $\mathbb{F}_{q^2}$ (specifically quaternary codes where $q=2$) have gained attention for potentially outperforming linear codes in terms of minimum distance. However, a fundamental ambiguity exists: it is often unclear whether a newly constructed "strictly additive" code (one that is not equivalent to any linear code) is genuinely new or merely a linear code disguised under a different representation.

Existing methods to distinguish strictly additive codes from linear ones rely heavily on geometric techniques (e.g., pseudo-arcs and Desarguesian spreads), which are complex and not universally applicable. The authors address the open question: Given a generator matrix of an additive code, how can one deterministically test if it is equivalent to a linear code over $\mathbb{F}_{q^2}$?

2. Methodology

The authors develop a purely algebraic framework based on the generator matrix of the code, avoiding the need for geometric constructions.

2.1 Mathematical Framework

• Representation: An additive code $C \subseteq \mathbb{F}_{q^2}^n$ is viewed as an $\mathbb{F}_q$-linear subspace of dimension $k$ in $\mathbb{F}_{q^2}^n$. The map $\phi: \mathbb{F}_{q^2}^n \to \mathbb{F}_q^{2n}$ converts the code into a linear subspace over $\mathbb{F}_q$.
• Equivalence Definition: Two codes are monomially equivalent if one can be transformed into the other via a permutation of coordinates and multiplication by invertible $2 \times 2$ matrices ($A_i \in GL_2(\mathbb{F}_q)$) acting on coordinate pairs.
• The Regular Representation: The authors utilize the regular representation of the field $\mathbb{F}_{q^2}$. Let $\omega$ be a primitive element with minimal polynomial $x^2 + c_1x + c_0$. The multiplication by $\omega$ corresponds to a companion matrix $M_\omega$.
• The Core Condition: An additive code $C$ with generator matrix $G$ is equivalent to a linear code if and only if there exists an invertible matrix $R \in GL_k(\mathbb{F}_q)$ and a block-diagonal matrix $A = \text{diag}(A_1, \dots, A_n)$ such that:
  $$RG = G(AM_\omega A^{-1})$$
  This equation implies that the code is closed under the scalar multiplication by $\omega$ (up to equivalence).

2.2 The Deterministic Algorithm (Algorithm 1)

The authors propose a three-step algorithm to test for equivalence:

1. Rank Check:

   • Partition the generator matrix $G$ into $n$ block columns $G_i$ of size $k \times 2$.
   • If any $G_i$ is the zero matrix, puncture the coordinate.
   • Theorem 3.2: If any remaining $G_i$ has rank 1, the code is strictly additive (not equivalent to a linear code). This is because any linear transformation preserving a 1D subspace must have an eigenvalue in $\mathbb{F}_q$, whereas the required transformation $R$ for a linear code must have no eigenvalues in $\mathbb{F}_q$.

2. Nullity Test:

   • Construct a large linear system $S\mathbf{x} = 0$ derived from the condition $RG_i = G_i T_i$ (where $T_i$ is conjugate to $M_\omega$).
   • Compute the nullity (dimension of the null space) of matrix $S$, denoted as $d$.
   • Theorem 3.3: If $d$ is odd, the code is strictly additive. The proof relies on the fact that if the code were linear, the solution space for $R$ would form a field isomorphic to $\mathbb{F}_{q^2}$, implying the dimension must be even.

3. Null Space Search:

   • If the nullity is even and no rank-1 blocks exist, the algorithm searches the null space of $S$ for a valid matrix $R$ that satisfies the equivalence condition.

3. Key Contributions

1. Algebraic Characterization: The paper provides the first deterministic, algebraic test (Theorem 3.1) to determine if an additive code is equivalent to a linear code, solely using the generator matrix.
2. Necessary Conditions:
   • Eigenvalue Condition (Theorem 3.2): If a generator block has rank 1, the code cannot be linear.
   • Parity Condition (Theorem 3.3): If the nullity of the constructed matrix $S$ is odd, the code cannot be linear.
3. General Applicability: Unlike previous geometric methods, this approach applies to any additive code and is computationally efficient using standard linear algebra tools (implemented here in MAGMA).

4. Results and Applications

The authors applied their algorithm to verify several sets of codes reported in recent literature:

• Quaternary Additive Codes from [14]:

  • They tested codes from Table II of Guan et al. [14].
  • Result: All tested codes (including extended and augmented versions) had odd nullity for matrix $S$.
  • Conclusion: These codes are strictly additive and not equivalent to any linear code. This resolves the ambiguity regarding whether these high-performance codes were merely linear codes in disguise.

• Additive Complementary Dual (ACD) Codes:

  • Case 1 (Strictly Additive): They tested ACD codes from [14, Table IV] and [18, Table 2].
    • Codes from [18] (Plotkin sum construction) were confirmed as strictly additive.
    • Codes from [14, Table IV] (Lines 5, 6, 10) were confirmed as strictly additive via the nullity test.
  • Case 2 (Equivalent to Linear):
    • They analyzed the ACD code from [14, Table IV, Line 1] with parameters $[22, 10, 9]_2^2$.
    • The nullity test was inconclusive (nullity = 2, which is even).
    • By solving the system, they found a transformation matrix $A$ proving this code is equivalent to a linear Hermitian LCD code with parameters $[22, 10, 9]_4$.
    • Significance: This finding improves the best-known bounds for linear Hermitian LCD codes, showing that an "additive" construction can yield a superior linear code.

5. Significance

• Resolution of Ambiguity: The paper definitively settles the status of several "new" additive codes, confirming that many are indeed strictly additive and offer performance unattainable by linear codes.
• Discovery of New Linear Codes: Conversely, the method successfully identified an additive code that is actually a linear code, thereby updating the best-known parameters for linear Hermitian LCD codes.
• Methodological Shift: The shift from geometric to algebraic testing provides a scalable, deterministic tool for coding theorists to classify codes without relying on complex geometric structures.
• Practical Utility: The algorithm is implemented and verified using MAGMA, making it immediately applicable for researchers constructing new codes.

In summary, Abdukhalikov and Ho provide a rigorous algebraic "litmus test" for additive codes, clarifying the landscape of quaternary coding theory by distinguishing between truly novel additive structures and linear codes that merely appear additive.