On the hull-variation problem of equivalent vector rank metric codes

1. Problem Statement

The paper addresses the hull-variation problem within the context of vector rank-metric codes.

• Background: The hull of a linear code $C$ is defined as the intersection of the code with its dual, $H(C) = C \cap C^\perp$. Codes with a trivial hull ($H(C) = \{0\}$) are known as Linear Codes with Complementary Duals (LCD codes).
• Context: In classical Hamming-metric codes, it was recently established (by Hao Chen and others) that for fields $\mathbb{F}_q$ with $q > 3$, any linear code is equivalent to an LCD code, and the hull dimension can be varied under equivalence.
• The Gap: It was an open question whether this phenomenon holds for vector rank-metric codes (codes over $\mathbb{F}_{q^m}$ equipped with the rank distance), particularly for small fields ($q=2, 3$) and regarding the associated matrix and extended block codes.
• Objective: The authors investigate whether the hull dimension of a vector rank-metric code can be reduced (or eliminated) through equivalence transformations, and how this affects associated matrix codes and extended block codes.

2. Methodology

The authors employ a combination of linear algebra, generator matrix manipulation, and field theory to construct equivalent codes with specific hull dimensions.

• Generator Matrix Decomposition:
  For a code $C$ with hull dimension $h$, the generator matrix $G$ is transformed (via row operations and column permutations) into a block form:
  $$G = \begin{bmatrix} I_h & A \\ 0 & B \end{bmatrix}$$
  where $I_h$ is the identity matrix corresponding to the hull basis. The condition that the first $h$ rows lie in the hull implies specific orthogonality constraints: $AA^\top + I_h = 0$ and $AB^\top = 0$.

• Equivalence Transformations:
  The authors construct an equivalence transformation matrix $M \in GL_n(\mathbb{F}_q)$ (or $GL_n(\mathbb{F}_{q^m})$ depending on the metric) to generate a new code $C' = C \cdot M$. The goal is to choose $M$ such that the rank of the new Gram matrix $G'G'^\top$ increases, thereby reducing the hull dimension ($\dim(H(C')) = k - \text{rank}(G'G'^\top)$).

• Case-Specific Constructions:

  • Case $q > 3$: The authors utilize diagonal matrices with entries $a_i$ such that $a_i^2 \neq 1$. This allows for the reduction of the hull dimension by 1 at a time.
  • Case $q \in \{2, 3\}$: Standard diagonal scaling fails because $x^2 = 1$ for all non-zero $x$ in $\mathbb{F}_2$ and $\mathbb{F}_3$.
    • For reducing hulls by 2 or more ($h \ge 2$), the authors construct block-diagonal matrices using specific small matrices $Z_2$ and $Z_3$ (derived from Lemma 3.3) that ensure invertibility of $YY^\top - I$.
    • For reducing a hull of dimension $h=1$ to $0$ (proving equivalence to an LCD code), the authors employ a specific affine transformation involving a vector $v$. They define a quadratic form $f(v)$ and prove that for $q=2$ and $q=3$, there always exists a vector $v$ such that $f(v) \neq 0$, effectively breaking the hull.

• Lifting to Associated Codes:
  Using the properties of self-dual bases and the trace map, the results for vector rank-metric codes are extended to:

  1. Matrix Codes: Codes in $\mathbb{F}_q^{n \times m}$.
  2. Extended Block Codes: The "flattened" vector representations of the matrix codes.

3. Key Contributions and Results

A. Hull Variation for Vector Rank-Metric Codes

The paper proves that for any vector rank-metric code $C$ over $\mathbb{F}_{q^m}$:

• If $q > 3$: For any hull dimension $h \ge 1$, there exists an equivalent code with hull dimension $\ell$ for any $0 \le \ell \le h-1$.
• If $q \in \{2, 3\}$:
  • If $h \ge 2$, the hull dimension can be reduced to any $\ell \in \{0, \dots, h-2\}$.
  • Crucially, if $h=1$, there exists an equivalent code with hull dimension $0$ (an LCD code).

B. Equivalence to LCD Codes

Corollary 3.6 is a major result: Every vector rank-metric code over any finite field $\mathbb{F}_q$ (including $q=2$ and $q=3$) is equivalent to an LCD code. This contrasts with the Hamming-metric case where the behavior for small fields was historically more complex or required specific conditions.

C. Implications for Matrix and Extended Block Codes

Under the condition that a self-dual basis exists (which holds if $q$ is even or both $q, m$ are odd):

• The hull dimension of the associated matrix code $D$ can be varied in steps of $m$. Specifically, if the vector code hull is reduced by $\ell$, the matrix code hull dimension is reduced by $m\ell$.
• The same variation holds for extended block codes.

D. Invariance and Matroid Theory

The authors demonstrate that the hull dimension is not an invariant of the underlying combinatorial structures in the rank-metric setting.

• In Hamming-metric codes (over $\mathbb{F}_2, \mathbb{F}_3$), equivalent codes share the same hull dimension because it is determined by the matroid/Tutte polynomial.
• In rank-metric codes, equivalent codes can induce isomorphic $(q, m)$-polymatroids (or $q$-matroids) yet possess different hull dimensions. This implies that the hull dimension captures information not reflected in the standard rank-metric matroidal invariants.

4. Significance

1. Theoretical Advancement: The paper resolves the hull-variation problem for vector rank-metric codes, extending previous results from Hamming-metric codes to the rank-metric domain, including the difficult cases of small fields ($q=2, 3$).
2. Construction of LCD Codes: It provides a constructive proof that LCD codes exist in the equivalence class of any vector rank-metric code. This is significant for applications in cryptography (e.g., side-channel attack resistance) and quantum error correction, where LCD codes are highly desirable.
3. Limitations of Matroid Invariants: The results highlight a fundamental difference between Hamming and Rank metrics. The fact that hull dimension varies under equivalence while the associated polymatroid remains isomorphic suggests that current matroid-based classification tools for rank-metric codes are insufficient to capture all structural properties of the code.
4. Algorithmic Potential: The constructive nature of the proofs (providing explicit matrices $M$ and vectors $v$) offers a pathway for algorithms to transform arbitrary rank-metric codes into LCD codes for practical implementation.

5. Conclusion

Ho and Johnsen successfully generalize the hull-variation problem to vector rank-metric codes. They prove that hull dimensions can be systematically reduced, culminating in the equivalence of any such code to an LCD code, regardless of the field size. This work not only solves a specific coding theory problem but also reveals new structural nuances in rank-metric codes that distinguish them from their Hamming-metric counterparts, particularly regarding the relationship between code equivalence and combinatorial invariants.