🔢 mathematics

Rank Distribution and Dynamics of Gram Matrices from Binary m-Sequences with Applications to LCD Codes

This paper establishes the complete rank distribution and dynamic behavior of $n \times n$ Gram matrices constructed from $n$ consecutive subsequences of binary m-sequences using semilinear representations and Bézoutians, thereby fully characterizing the hull distribution of punctured cyclic simplex codes.

Original authors: Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou

Published 2026-04-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a magical, endless stream of binary digits (0s and 1s) generated by a simple machine called a Linear Feedback Shift Register (LFSR). In the world of math and engineering, this is known as an m-sequence. It's famous for looking very random, even though it's generated by a strict, predictable rule.

This paper is like a detective story where the authors take this stream of numbers and look at it through a specific lens: Gram matrices.

The Setup: Building a "Snapshot"

Imagine you are taking photos of a moving parade.

You have a long line of people (the m-sequence).
You decide to take a photo of a specific group of $n$ people standing next to each other.
Then, you slide your camera one step to the right and take another photo of the next group.
You keep doing this, creating a stack of photos.

In the paper, the authors create a mathematical "stack" (a matrix) called $G_t$ . This stack contains $n$ rows, where each row is a short slice of the sequence of length $t$ .

The Core Mystery: The "Inner Product" Mirror

Now, the authors don't just look at the photos; they create a mirror image of them. They take every row in their stack and compare it with every other row to see how much they "overlap" or "agree." In math terms, they calculate the inner product of every pair of rows.

When you arrange all these comparisons into a new square grid, you get a Gram matrix (let's call it $M$ ).

If the rows are all unique and independent, the matrix is "full rank" (it holds a lot of information).
If some rows are just copies or simple combinations of others, the matrix loses "rank" (it becomes "singular" or squashed).

The big question the paper asks is: As we change the length of the slice ( $t$ ), how often does this matrix stay "full rank," and when does it collapse?

The Discovery: A Hidden Pattern

The authors discovered that the behavior of this matrix isn't random. It follows a very specific, elegant rule based on rational functions (fractions made of polynomials).

Here are the main findings, translated into everyday analogies:

1. The "Half-and-Half" Rule
They found that for roughly half of all possible slice lengths, the matrix is perfectly "full rank" (it's a sturdy, 3D structure). For the other half, it collapses into a lower dimension.

Analogy: Imagine flipping a coin for every possible length. About 50% of the time, you get a "Full Rank" (Heads), and the rest of the time, you get a "Deficient Rank" (Tails).

2. The "Jelly" vs. "Rock" Dynamics
The paper describes how the rank changes as you increase the slice length ( $t$ ) step-by-step.

The Unstable Jelly (Deficient States): If the matrix is currently "squashed" (rank-deficient), it is extremely unstable. The very next step ( $t+1$ ) must change the rank. It cannot stay the same. It's like a wobbly jelly; it can't hold its shape for two seconds in a row.
The Persistent Rock (Full Rank): If the matrix is "full rank," it is very stable. Once it hits that full-strength state, it tends to stay that way for a while, like a solid rock that doesn't crumble immediately.

3. The "Valleys" (Local Minima)
The authors counted how many times the rank dips down to a low point and then bounces back up on both sides (like a valley in a mountain range). They found a precise formula for how many of these "valleys" exist for any given sequence length.

The Application: Building Better Codes

Why does this matter? The paper connects this math to coding theory, specifically to a type of error-correcting code called Simplex codes.

The Problem: In digital communication, we want codes that are "LCD" (Linear Complementary Dual). This is a fancy way of saying the code is "self-protecting" and doesn't accidentally overlap with its own shadow (its dual code). This makes the code very efficient and secure.
The Solution: The authors proved that if you take their m-sequence and cut it at the right length, you get an LCD code.
The Result: They calculated exactly how many of these codes are LCD. The answer is: Almost half of them are perfect LCD codes. This gives engineers a clear recipe for picking the best lengths to use when designing secure communication systems.

Summary

In short, this paper took a classic, well-known mathematical object (the m-sequence), built a specific grid of numbers from it (the Gram matrix), and discovered a hidden rhythm in how that grid's "strength" (rank) changes. They proved that:

The strength follows a predictable pattern based on polynomial fractions.
Weak states are temporary and unstable, while strong states are persistent.
This knowledge allows us to perfectly identify which versions of these codes are the most robust for digital communication.

The authors didn't just guess; they used advanced tools from algebra (like Galois groups and Bézoutians) to prove these patterns are mathematically guaranteed, not just lucky observations.

1. Problem Statement

The paper addresses a fundamental gap in the theory of binary maximum-length sequences (m-sequences). While m-sequences are well-understood regarding their classical properties (balance, run distribution, ideal autocorrelation), their structural behavior when viewed through the lens of Gram matrices formed by their state vectors remains largely unexplored.

Specifically, the authors investigate the family of Gram matrices $\{G_t G_t^\top \mid 1 \le t \le 2^n - 1\}$ , where $G_t$ is the $n \times t$ observability matrix constructed from $n$ consecutive subsequences of length $t$ from an m-sequence of period $2^n - 1$ . The core questions are:

Rank Distribution: What is the exact distribution of the ranks of these Gram matrices across all possible lengths $t$ ?
Rank Dynamics: How does the rank evolve as $t$ increases cyclically? Are there patterns of stability or instability in rank-deficient states?
Application: How do these rank properties characterize the hull distribution of punctured cyclic simplex codes, specifically identifying Linear Complementary Dual (LCD) codes?

2. Methodology

The authors employ a sophisticated blend of algebraic tools to transform the combinatorial problem into an algebraic enumeration problem.

Lifting to Extension Fields: Instead of analyzing the binary matrix $G_t G_t^\top$ directly over $\mathbb{F}_2$ , the authors lift the problem to the extension field $\mathbb{F}_{2^n}$ . They utilize the trace representation of m-sequences ( $s_t = \text{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(\lambda \alpha^t)$ ) to factorize the observability matrix $G_t$ into a product involving a Vandermonde matrix and a diagonal matrix. This reduces the rank of $G_t G_t^\top$ to the rank of a symmetric matrix $M(x)$ over $\mathbb{F}_{2^n}[x]$ , where $x = \alpha^t$ .
Semilinear Representations: To characterize the singular matrices (those with determinant zero), the authors utilize the semilinear representation of Galois groups. They prove that the kernel of a singular matrix $M(x)$ contains a vector with components forming a Frobenius orbit ( $c, c^2, c^4, \dots$ ). This allows them to link the singularity condition to specific rational functions.
Rational Function Canonical Representation: A key theoretical breakthrough is the establishment of a bijection between the set of singular parameters $x$ and a specific set of rational functions of the form $\frac{z^k \tilde{u}(z)}{u(z)}$ , where $u(z)$ is a polynomial coprime to its reciprocal $\tilde{u}(z)$ .
Bézoutian Matrices: The rank of the singular matrices is explicitly determined using the Bézoutian of polynomials. The rank of $M(x)$ is shown to be equal to $\deg(u) + |k|$ , where $u$ and $k$ come from the canonical representation of $x$ .
Generating Functions: The enumeration of polynomials satisfying the coprimality condition ( $\gcd(u, \tilde{u}) = 1$ ) is performed using generating functions, allowing for the derivation of closed-form formulas for the rank distribution.

3. Key Contributions and Results

A. Global Rank Distribution (Theorem 1.1)

The paper provides a complete and explicit formula for the number of $t$ values yielding a specific rank $k$ for the Gram matrix $G_t G_t^\top$ :

Rank 0: 1 case.
Rank 1: 2 cases.
Rank $k$ ( $2 \le k \le n-1$ ): $2^{k-1}$ cases.
Rank $n$ (Full Rank): $2^{n-1} - 2$ cases.
Significance: This proves that approximately half of the admissible values of $t$ result in full-rank Gram matrices.

B. Local Rank Dynamics (Theorems 1.2 & 1.3)

The authors uncover distinct dynamical behaviors of the rank function $r_n(t)$ :

Persistence of Full Rank: Once the rank reaches $n$ (full rank), it persists for at least one more step. If $r_n(t) = n$ , then $r_n(t+1) = n$ .
Instability of Deficient States: Rank-deficient states are strictly unstable. If $r_n(t) < n$ , then $r_n(t+1) \neq r_n(t)$ . The rank must change (either increase or decrease) in the next step.
Local Minima: The paper enumerates the number of local minima in the rank function, providing a formula based on $n$ .

C. Application to Coding Theory (Section 5)

The results are applied to the family of punctured cyclic simplex codes $\{C_t\}$ generated by the observability matrices.

Hull Distribution: Using the relation $\dim(\text{Hull}(C_t)) = n - \text{rank}(G_t G_t^\top)$ , the authors derive the exact distribution of hull dimensions.
LCD Codes: A code is LCD if its hull dimension is 0 (i.e., the Gram matrix is full rank). The paper proves that in the family of punctured simplex codes of length $t$ ( $n \le t \le 2^n-1$ ), there are exactly $2^{n-1} - 2$ LCD codes.
Self-Orthogonal Codes: There is exactly one self-orthogonal code in this family (the full-length cyclic simplex code).

4. Significance and Impact

New Structural Insight: The work reveals deep algebraic structures within m-sequences that were previously unknown, moving beyond Golomb's classical properties to a matrix-theoretic characterization.
Algorithmic Utility: The explicit rank distribution and the identification of LCD codes are crucial for coding theory applications. LCD codes are highly valued for their resistance to side-channel attacks and their utility in quantum error correction.
Theoretical Framework: The methodology combining Galois semilinear representations, Bézoutians, and rational function enumeration provides a powerful toolkit that could be adapted to study other sequence families or codes over different fields.
Open Problems: The paper concludes by proposing open problems for $q$ -ary m-sequences (specifically for $q=3$ and $q=5$ ), suggesting that the observed patterns may generalize to other finite fields, inviting further research.

In summary, this paper bridges the gap between sequence design and matrix theory, providing a rigorous characterization of the rank properties of Gram matrices derived from m-sequences and directly applying these findings to optimize the construction of LCD codes.