PaperlayerView exact revision on arXiv

Source-linked AI summary

Shortest self-orthogonal and LCD embeddings of linear codes over Fq+uFq

Junmin An, Jon-Lark Kim

arXiv:2608.28222v1cs.IT

TL;DR

The paper asks for exact shortest self-orthogonal and LCD embedding lengths for linear codes over Fq+uFq. It decomposes Gram matrices into finite-field components and applies congruence and Witt theory, obtaining complete characteristic-dependent formulas and constructions. It also characterizes shortest LCD embeddings and reports examples whose selected Gray images can be optimal over Fq.

  • Problem

    Embedding methods require determining how many columns must be appended to a generator matrix to obtain self-orthogonal or LCD codes.

  • Method

    The paper decomposes Gram matrices over R = Fq + uFq into symmetric matrices over Fq and uses congruence classification and Witt theory.

  • Results

    The paper determines exact shortest self-orthogonal and LCD embedding lengths, with two self-orthogonal cases in each characteristic and constructions of all shortest self-orthogonal embeddings.

  • Takeaways & Limitations

    Every self-orthogonal code with nonzero free rank can be realized as a shortest self-orthogonal embedding, while shortest LCD embeddings are characterized by appended matrices of prescribed sizes.

  • Takeaways & Limitations

    The embeddings may change the original code's type, motivating future work that preserves type.

Abstract

from arXiv · show

This paper determines the exact lengths of shortest self-orthogonal and LCD embeddings of linear codes over $\mathbb{F}_q+u\mathbb{F}_q$. By decomposing Gram matrices over $\mathbb{F}_q+u\mathbb{F}_q$ into pairs of symmetric matrices over the finite field $\mathbb{F}_q$, the embedding problems are reduced to the congruence classification of symmetric and alternate matrices over finite fields. Complete formulas for the shortest self-orthogonal embedding length are obtained, with two distinct cases arising in both even and odd characteristic. We also show that every self-orthogonal code over $\mathbb{F}_q+u\mathbb{F}_q$ with nonzero free rank can be viewed as a shortest self-orthogonal embedding of another code. We use Witt theory to construct all shortest self-orthogonal embeddings. A complete characterization of shortest LCD embeddings is also established in terms of invertible and arbitrary matrices of prescribed sizes appended to a generator matrix. Examples of self-orthogonal and LCD embeddings with the largest minimum distance for the code considered are also presented, some of whose Gray images are optimal codes over $\mathbb{F}_q$.

1 Introduction

The paper studies shortest self-orthogonal and LCD embeddings over Fq+uFq, motivated by embedding methods that append columns to generator matrices. It reduces these problems to finite-field matrix classification and gives exact self-orthogonal embedding lengths in even and odd characteristic.

  • Embedding methods append columns to a generator matrix to obtain codes with properties such as self-orthogonality or the LCD condition.
  • The paper determines exact shortest self-orthogonal and LCD embedding lengths for linear codes over R = Fq + uFq.
  • Gram matrices over R decompose into two symmetric matrices over Fq, reducing embedding lengths to congruence classification of symmetric and alternate finite-field matrices.
  • Shortest self-orthogonal embedding lengths split into two cases for each of even and odd characteristic.
  • The paper uses Witt theory to construct all shortest self-orthogonal embeddings and provides examples for the four characteristic-dependent cases.

2 Preliminaries

The preliminaries define codes, duality, self-orthogonality, LCD codes, embeddings, Gram matrices, and the finite-field bilinear-form tools used later. They also establish the ring and matrix facts underlying the embedding analysis.

  • R = Fq + uFq is a commutative local ring whose maximal ideal is (u), and invertibility reduces modulo (u) to invertibility over Fq.
  • A linear code over R has type {k1, k2}, where k1 is its free rank and k2 counts the generators lying in (uR)^n.
  • The dual is defined by the standard dot product; self-orthogonality means C ⊆ C⊥, while LCD means Hull(C) = {0}.
  • For a generator matrix G, self-orthogonality is equivalent to GGT = O, whereas a free code is LCD exactly when GGT is invertible.
  • A shortest self-orthogonal embedding appends the fewest columns needed to make the generated code self-orthogonal, with length denoted ns(C).
  • Symmetric matrices represent symmetric bilinear forms, and alternate matrices, symplectic spaces, isotropic subspaces, and Witt decompositions supply the finite-field classification framework.

3 Shortest self-orthogonal embeddings of linear codes over R with even characteristic

For even characteristic, the paper reduces shortest self-orthogonal embeddings to a matrix invariant ν and classifies it through the Gram matrix decomposition. It proves finiteness and gives exact formulas based on the residue code and ranks of finite-field components.

  • Bounds and invariants: For q even, every code that is not self-orthogonal satisfies ns(C) ≤ 2n.
  • Construction: Appending a duplicate generator matrix, G′ = [G | G], produces a self-orthogonal embedding, so ν(GGT) is finite in even characteristic.
  • Bounds and invariants: The invariant ν(GGT) equals the minimum number of appended columns required to embed C into a self-orthogonal code.
  • Bounds and invariants: Congruent symmetric matrices have the same ν, and block-diagonal matrices satisfy ν(M) ≤ ν(A) + ν(B).
  • Exact lengths: For even q, Theorem 3.6 expresses ns(C) using r = rankFq(A0), ρ = rankFq(NA1NT), and whether Res(C) is self-orthogonal.
  • Exact lengths: When Res(C) is not self-orthogonal, ns(C) = n + r + 1; in the zero-diagonal case the additional term is r + ρ when ρ > 0 and r + 1 when ρ = 0.

4 Shortest self-orthogonal embeddings of linear codes over R with odd characteristic

For odd characteristic, the paper treats Gram matrices through finite-field symmetric-matrix representations and Witt indices. This yields finite shortest self-orthogonal embeddings and a case distinction governed by determinant-square conditions.

  • Construction: Appending suitable columns generates a self-orthogonal embedding, and ν(GGT) is finite even in odd characteristic.
  • Finite-field representation: The quantity µ(A) is the minimum m such that A = XKmXT for a finite-field matrix X, and it is invariant under adjoining zero blocks.
  • Matrix bounds: For an invertible symmetric matrix over Fq, ν(A) is at least its size, with equality characterized by a determinant-square condition.
  • Witt-theoretic construction: A symmetric matrix over Fq can be represented using a nonsingular form built from the structured component S and hyperbolic blocks, connecting the embedding problem to Witt theory.
  • Reduction: For odd q, the paper writes GGT = A0 + uA1 and reduces the problem using an invertible finite-field congruence that puts A0 into a structured form.

5 Construction of shortest self-orthogonal embeddings of linear codes over R

The section characterizes shortest self-orthogonal embeddings over R through matrix equations over Fq, constructs them explicitly, and classifies all shortest embeddings. It also shows that self-orthogonal codes with nonzero free rank arise as shortest embeddings of shorter codes.

  • Reverse embedding construction: Every self-orthogonal code of type {k1, k2} with k1 > 0 is a shortest self-orthogonal embedding of a code of each length n0 satisfying n−k1 ≤ n0 < n.The shorter code is obtained by puncturing selected coordinates, and the puncturing map is an isomorphism preserving the code type.
  • Scope boundary: Free-rank-zero self-orthogonal codes can be obtained by embedding shorter codes, but not as shortest embeddings, so this case is excluded from detailed treatment.Their generator entries are multiples of u, and every punctured code remains self-orthogonal.
  • Constructing all embeddings: Witt-theoretic constructions provide an explicit shortest embedding, and Theorem 5.6 generates every other shortest embedding from it using prescribed matrix transformations.The classification starts from a fixed completion B* = X* + uY* and characterizes all equivalent shortest completions.
  • Matrix characterization: The embedding condition reduces to solving XXT = −A0 and XYT + YXT = −A1 after decomposing GGT = A0 + uA1.Here B = X + uY is appended to G, and [G | B] must have zero Gram matrix.
  • Matrix characterization: Proposition 5.2 characterizes when the linear map φA can attain a prescribed symmetric matrix through the kernel restriction NAMNT.This criterion supports the existence arguments for matrices completing the Gram-matrix equations.
  • Length and rank: The shortest completion size is governed by the rank of A0 and the restricted matrix ˜N = NA1NT, with the even-characteristic rank formula rank(A0) + rank(˜N)/2.The associated hull dimension and radical structure determine the rank of admissible completion matrices.
  • Characteristic cases: Even-characteristic codes split into Case I and Case II, distinguished by structural conditions including whether Res(C) is self-orthogonal.For Case I, the all-one vector is excluded from the relevant column space; otherwise it belongs to every such column space.

6 Shortest LCD embeddings of linear codes over R

The paper characterizes shortest LCD embeddings over R through the rank and radical structure of the field component A0 of the Gram matrix. It proves the minimum length and describes exactly which appended matrices produce all shortest embeddings.

  • Length characterization: nℓ(C) is bounded below by n + k − r, where r = rankFq(A0) and k is the number of generator-matrix rows.The proof writes the appended matrix as B = B0 + uB1 and studies invertibility over Fq.
  • Length characterization: A basis extending Rad(A0) puts A0 into a congruent block form S ⊕ O, with S invertible on the complementary subspace.This decomposition isolates the radical coordinates that must be handled by appended columns.
  • Length characterization: An appended matrix constructed from the radical decomposition makes A0 + DDT invertible, establishing nℓ(C) ≤ n + k − r.The construction proves the lower bound is attained.
  • All shortest embeddings: Theorem 6.3 characterizes every shortest LCD embedding using an invertible change-of-basis matrix U whose first ℓ rows span Rad(A0).The appended block contains an ℓ × ℓ invertible matrix D over R and an arbitrary matrix E of corresponding size.
  • All shortest embeddings: Conversely, the radical-sized block in any shortest LCD embedding must be invertible, completing the if-and-only-if characterization.A noninvertible block would contradict invertibility of the transformed Gram matrix.

7 Some examples

Examples instantiate the shortest self-orthogonal embedding formulas in even and odd characteristic and illustrate the LCD characterization. The authors also enumerate shortest embeddings and select examples with the largest minimum distance, including strong Gray-image codes.

  • Examples 7.1–7.5: Examples 7.1–7.4 cover the two even-characteristic and two odd-characteristic self-orthogonal cases, while Example 7.5 treats LCD embeddings.The examples use the paper’s classification results and construction theorems.
  • Example 7.1: 27 is the shortest self-orthogonal embedding length in Example 7.1, computed as 20 + 6 + 1.The selected embedding has minimum distance 8, and its Gray image is a [54, 14, 14] binary code.
  • Example 7.2: 27 is the shortest self-orthogonal embedding length in Example 7.2, computed as 22 + 5 + 0.A selected embedding has minimum distance 8 and Gray image [54, 14, 16].
  • Example 7.3: 28 is the shortest self-orthogonal embedding length in Example 7.3, computed as 23 + 5 + 0.The selected embedding has minimum distance 9, verified as the largest among shortest self-orthogonal embeddings for that code.
  • Example 7.4: 27 is the shortest self-orthogonal embedding length in Example 7.4, computed as 22 + 4 + 0 + 1.The selected embedding has minimum distance 10, verified as largest among shortest self-orthogonal embeddings for that code.
  • Example 7.5: 10 is the shortest LCD embedding length in Example 7.5, computed as 8 + 3 − 1.The selected embedding has minimum distance 4, and its Gray image is an optimal [20, 6, 8] LCD code over F2.

8 Conclusion

The paper determines exact shortest self-orthogonal and LCD embedding lengths over R, constructs all shortest self-orthogonal embeddings, and characterizes shortest LCD embeddings. Its scope leaves type preservation as a future requirement because embeddings may change the original code’s type.

  • Contributions: The paper obtains complete shortest self-orthogonal results for two cases in each characteristic and develops constructions for all shortest embeddings.The four cases are illustrated by examples, which are also enumerated for largest minimum distance.
  • Contributions: The paper characterizes shortest LCD embeddings and applies that characterization to enumerate them and identify one with largest minimum distance in an example.This extends the conclusion beyond self-orthogonal embeddings to the LCD setting.
  • Scope and future work: The embeddings may change the type of the original code, so preserving type is identified as a direction for future research.The stated future problem adds type preservation as a requirement to shortest embedding questions over rings.
Loading 2608.28222v1…