The equivalent condition for GRL codes to be MDS, AMDS or self-dual

Technical Summary: Equivalent Conditions for GRL Codes to be Non-GRS MDS, AMDS, or Self-Dual

Problem Statement
Maximum Distance Separable (MDS) and Almost MDS (AMDS) codes, along with self-dual codes, possess significant algebraic properties and are widely applied in communication systems, data storage, quantum coding, and cryptography. While Reed-Solomon (RS) codes are a well-known class of MDS codes, constructing codes that are not equivalent to RS codes (non-RS) remains a critical area of research to expand the diversity of available code families. Previous works by Roth and Lempel [20], and subsequently by Wu et al. [21] and [22], constructed specific classes of non-RS MDS codes by augmenting the generator matrix of RS codes with two or three additional columns. This paper addresses the need to generalize these constructions further and establish precise algebraic conditions under which these generalized codes (and their duals) exhibit MDS, AMDS, or self-dual properties without being equivalent to RS codes.

Methodology
The authors introduce a class of Generalized Roth-Lempel (GRL) codes, denoted as $GRL_k(\alpha, v, A_{l \times l})$, defined over a finite field $F_q$. This construction generalizes previous models by replacing the specific augmentation matrices used in [21] and [22] with an arbitrary invertible matrix $A_{l \times l} \in GL_l(F_q)$. Specifically, the paper focuses on the case where $l=3$, denoted as $GRL_k(\alpha, v, A_{3 \times 3})$.

The methodology employs the following technical approaches:

1. Generator Matrix Analysis: The authors define the generator matrix $G_4$ for the $GRL_k(\alpha, v, A_{3 \times 3})$ code, which consists of a standard Vandermonde-like structure augmented by three columns derived from the matrix $A_{3 \times 3}$.
2. Non-RS Verification: To prove the codes are non-RS, the authors utilize Lemma 5 (a characterization of RS codes via generator matrix entries) and demonstrate that the specific structure of the augmented columns prevents the code from satisfying the necessary conditions for RS equivalence when $k > 3$.
3. MDS and AMDS Conditions: Using Lemma 6 (which states an $[n, k]$ code is MDS if and only if any $k$ columns of its generator matrix are linearly independent), the authors analyze the determinants of all possible $k \times k$ submatrices formed by the generator matrix. This involves extensive case analysis regarding the inclusion of the augmented columns ($u_1, u_2, u_3$) in the submatrices.
4. Parity-Check Matrix Construction: For the self-dual analysis, the authors derive an explicit parity-check matrix $H_5$ for the GRL code. They utilize Lemma 4 (properties of sums of powers of field elements weighted by inverse differences) to verify the orthogonality condition $G H^T = 0$.
5. Self-Duality Criteria: The condition for self-duality ($C = C^\perp$) is established by requiring the generator matrix and the parity-check matrix to span the same space, leading to specific constraints on the vector $v$ and the matrix $A_{3 \times 3}$.

Key Contributions and Results

1. Non-RS Property: Theorem 7 establishes that for $k > 3$, the code $GRL_k(\alpha, v, A_{3 \times 3})$ is strictly non-GRS (Generalized Reed-Solomon), regardless of the choice of parameters, provided $A_{3 \times 3} \in GL_3(F_q)$.

2. Equivalent Conditions for Non-RS MDS: Theorem 8 provides necessary and sufficient conditions for $GRL_k(\alpha, v, A_{3 \times 3})$ to be MDS. These conditions are expressed as inequalities involving sums of products of the evaluation points $\alpha_i$ and the entries of $A_{3 \times 3}$. Specifically, for any subset of size $k-1$ or $k-2$, certain polynomial expressions involving the matrix entries must not vanish.

   • Corollary 10 and Example 11 illustrate these conditions with a specific matrix form and a concrete example over $F_{11}$, yielding an $[8, 4, 5]$ code.

3. Equivalent Conditions for AMDS Duals: Theorem 12 determines the conditions under which the dual code $GRL_k^\perp(\alpha, v, A_{3 \times 3})$ is AMDS. This requires that any $k-1$ columns of the generator matrix are linearly independent, while at least one set of $k$ columns is dependent. The theorem lists six specific cases involving the entries of $A_{3 \times 3}$ and sums of $\alpha_i$.

   • Corollary 13 and Example 14 provide a specific instantiation over $F_7$, resulting in an $[8, 4, 4]$ code.

4. Parity-Check Matrix and Self-Duality: Theorem 16 constructs the parity-check matrix $H_5$ for the GRL code. Building on this, Theorem 17 provides the equivalent condition for the code to be non-RS self-dual. The conditions require:

   • $n + 3 = 2k$ (dimension constraint).
   • The vector $v$ must be proportional to the vector of inverse differences $u$ (i.e., $v_i = \lambda u_i$).
   • The matrix $A_{3 \times 3}$ must satisfy a specific quadratic relation involving the sums of $\alpha_i$ and $\alpha_i^2$.
   • Examples 18 and 19 demonstrate the construction of such self-dual codes over $F_{13}$ and $F_{19}$, respectively. Notably, Example 19 highlights that self-dual GRL codes can be constructed for $q \equiv 3 \pmod 4$, a case where previous self-dual constructions in [22] were limited.

Significance
The paper claims to generalize the results found in [21] and [22] by replacing the specific augmentation matrices with a general invertible matrix $A_{3 \times 3}$. The primary significance lies in providing a unified framework to determine when these generalized codes possess optimal distance properties (MDS/AMDS) or self-duality. The authors explicitly note that their results recover the theorems in [21] as special cases. Furthermore, the construction of self-dual codes for $q \equiv 3 \pmod 4$ (Example 19) extends the applicability of such codes beyond the constraints of previous literature. The paper concludes that these equivalent conditions allow for the systematic construction of non-RS codes with desirable properties for applications in communications and cryptography.