🔢 mathematics

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

本文利用半线性表示和贝祖行列式，建立了由二元 m 序列的 n 个连续子序列构造的 $n \times n$ 格拉姆矩阵的完整秩分布与动态行为，从而完全刻画了打孔循环单纯形码的核分布。

原作者： Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou

发布于 2026-04-30

📖 1 分钟阅读🧠 深度阅读

原作者： Hengfeng Liu, Chunming Tang, Cuiling Fan, Zhengchun Zhou

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你拥有一条由名为“线性反馈移位寄存器（LFSR）”的简单机器生成的、神奇的、无限的二进制数字（0 和 1）流。在数学和工程领域，这被称为m 序列。它之所以闻名，是因为尽管它是通过严格且可预测的规则生成的，但看起来却非常随机。

本文就像一部侦探故事，作者们利用**格拉姆矩阵（Gram matrices）**这一特定视角来审视这条数字流。

设定：构建“快照”

想象你正在拍摄一场行进中的游行。

你有一长排人（即 m 序列）。
你决定拍摄一组特定的、站在一起的 $n$ 个人。
然后，你将相机向右滑动一步，拍摄下一组人。
你持续这样做，从而形成一叠照片。

在论文中，作者们构建了一个名为 $G_t$ 的数学“堆栈”（即矩阵）。这个堆栈包含 $n$ 行，其中每一行都是长度为 $t$ 的序列切片。

核心谜题：“内积”之镜

现在，作者们不仅仅是在看这些照片；他们为照片创建了一个镜像。他们取堆栈中的每一行，并将其与每一行进行比较，以查看它们有多少“重叠”或“一致”。用数学术语来说，他们计算了每一对行的内积。

当你将所有这些比较排列成一个新的方格网格时，你就得到了一个格拉姆矩阵（让我们称之为 $M$ ）。

如果所有行都是唯一且独立的，该矩阵就是“满秩”的（它包含大量信息）。
如果某些行仅仅是其他行的副本或简单组合，该矩阵就会失去“秩”（它变得“奇异”或被压扁）。

本文提出的大问题是：当我们改变切片长度（ $t$ ）时，该矩阵保持“满秩”的频率是多少，以及它何时会崩溃？

发现：隐藏的模式

作者们发现，该矩阵的行为并非随机。它遵循一个基于有理函数（由多项式构成的分数）的非常具体且优雅的规则。

以下是主要发现，已转化为日常类比：

1. “半对半”规则
他们发现，对于大约一半的所有可能切片长度，矩阵是完美的“满秩”（它是一个坚固的三维结构）。对于另一半，它会坍缩成更低的维度。

类比： 想象为每一个可能的长度抛一次硬币。大约 50% 的时间，你会得到“满秩”（正面），其余时间你会得到“亏秩”（反面）。

2. “果冻”与“岩石”的动态
本文描述了随着你逐步增加切片长度（ $t$ ），秩是如何变化的。

不稳定的果冻（亏秩状态）： 如果矩阵当前处于“被压扁”（秩亏）状态，它就极不稳定。下一步（ $t+1$ ）必须改变秩。它不能保持原样。这就像一块摇晃的果冻；它无法连续两秒保持其形状。
持久的岩石（满秩）： 如果矩阵是“满秩”的，它就非常稳定。一旦达到这种全强度状态，它往往会保持一段时间，就像一块不会立即崩解的实心岩石。

3. “山谷”（局部极小值）
作者们计算了秩下降到低点然后在两侧反弹（就像山脉中的山谷）的次数。他们找到了一个精确的公式，用于计算给定序列长度下存在多少个这样的“山谷”。

应用：构建更好的代码

这为什么重要？本文将这一数学与编码理论联系起来，具体涉及一种名为**单纯形码（Simplex codes）**的纠错码。

问题： 在数字通信中，我们需要“LCD"（线性互补对偶）代码。这是一种花哨的说法，意指该代码具有“自我保护”能力，不会意外与其自身的影子（即其对偶码）重叠。这使得代码非常高效且安全。
解决方案： 作者们证明，如果你将他们的 m 序列在正确的长度处切断，你就会得到一个 LCD 代码。
结果： 他们精确计算出了有多少这样的代码是 LCD 代码。答案是：几乎有一半是完美的 LCD 代码。 这为工程师在设计安全通信系统时选择最佳长度提供了清晰的方案。

总结

简而言之，本文选取了一个经典的、众所周知的数学对象（m 序列），从中构建了一个特定的数字网格（格拉姆矩阵），并发现了该网格的“强度”（秩）变化中隐藏的韵律。他们证明了：

强度遵循基于多项式分数的可预测模式。
弱态是暂时且不稳定的，而强态则是持久的。
这一知识使我们能够完美地识别出哪些版本的这些代码最适合数字通信。

作者们不仅仅是猜测；他们使用了来自代数的先进工具（如伽罗瓦群和贝祖行列式）来证明这些模式在数学上是得到保证的，而不仅仅是幸运的观察。

以下是论文《二元 M 序列 Gram 矩阵的秩分布与动力学及其在 LCD 码中的应用》的详细技术总结。

1. 问题陈述

本文解决了二元最大长度序列（m 序列）理论中的一个根本性空白。尽管 m 序列在经典性质（平衡性、游程分布、理想自相关）方面已得到充分理解，但将其状态向量视为Gram 矩阵时所表现出的结构行为，在很大程度上仍未被探索。

具体而言，作者研究了 Gram 矩阵族 $\{G_t G_t^\top \mid 1 \le t \le 2^n - 1\}$ ，其中 $G_t$ 是由周期为 $2^n - 1$ 的 m 序列中 $n$ 个连续的长度为 $t$ 的子序列构成的 $n \times t$ 可观测性矩阵。核心问题如下：

秩分布：在所有可能的长度 $t$ 下，这些 Gram 矩阵的秩的确切分布是什么？
秩动力学：随着 $t$ 循环增加，秩如何演变？在秩亏缺状态中是否存在稳定性或不稳定性的模式？
应用：这些秩性质如何刻画穿孔循环单纯形码的核（hull）分布，特别是如何识别线性互补对偶（LCD）码？

2. 方法论

作者采用了一种复杂的代数工具组合，将组合问题转化为代数计数问题。

提升到扩域：作者没有直接在 $\mathbb{F}_2$ 上分析二元矩阵 $G_t G_t^\top$ ，而是将问题提升到扩域 $\mathbb{F}_{2^n}$ 。他们利用 m 序列的迹表示（ $s_t = \text{Tr}_{\mathbb{F}_{2^n}/\mathbb{F}_2}(\lambda \alpha^t)$ ）将可观测性矩阵 $G_t$ 分解为涉及范德蒙德矩阵和对角矩阵的乘积。这将 $G_t G_t^\top$ 的秩降低为 $\mathbb{F}_{2^n}[x]$ 上对称矩阵 $M(x)$ 的秩，其中 $x = \alpha^t$ 。
半线性表示：为了刻画奇异矩阵（即行列式为零的矩阵），作者利用了伽罗瓦群的半线性表示。他们证明了奇异矩阵 $M(x)$ 的核包含一个分量构成弗罗贝尼乌斯轨道（ $c, c^2, c^4, \dots$ ）的向量。这使得他们能够将奇异性条件与特定的有理函数联系起来。
有理函数规范表示：一个关键的理论突破是建立了奇异参数 $x$ 的集合与特定形式的有理函数集合 $\frac{z^k \tilde{u}(z)}{u(z)}$ 之间的双射，其中 $u(z)$ 是与其互反多项式 $\tilde{u}(z)$ 互质的多项式。
贝祖矩阵（Bézoutian Matrices）：奇异矩阵的秩利用多项式的**贝祖式（Bézoutian）**被明确确定。 $M(x)$ 的秩被证明等于 $\deg(u) + |k|$ ，其中 $u$ 和 $k$ 来自 $x$ 的规范表示。
生成函数：满足互质条件（ $\gcd(u, \tilde{u}) = 1$ ）的多项式的计数是使用生成函数完成的，从而推导出了秩分布的闭式公式。

3. 主要贡献与结果

A. 全局秩分布（定理 1.1）

论文提供了 Gram 矩阵 $G_t G_t^\top$ 产生特定秩 $k$ 的 $t$ 值数量的完整且显式的公式：

秩 0：1 种情况。
秩 1：2 种情况。
秩 $k$ ( $2 \le k \le n-1$ )： $2^{k-1}$ 种情况。
秩 $n$ （满秩）： $2^{n-1} - 2$ 种情况。
意义：这证明了大约一半的容许 $t$ 值会导致满秩 Gram 矩阵。

B. 局部秩动力学（定理 1.2 和 1.3）

作者揭示了秩函数 $r_n(t)$ 的不同动态行为：

满秩的持续性：一旦秩达到 $n$ （满秩），它至少会持续一步。如果 $r_n(t) = n$ ，则 $r_n(t+1) = n$ 。
亏缺状态的不稳定性：秩亏缺状态是严格不稳定的。如果 $r_n(t) < n$ ，则 $r_n(t+1) \neq r_n(t)$ 。秩在下一步必须发生变化（增加或减少）。
局部极小值：论文枚举了秩函数中局部极小值的数量，提供了基于 $n$ 的公式。

C. 在编码理论中的应用（第 5 节）

结果被应用于由可观测性矩阵生成的穿孔循环单纯形码族 $\{C_t\}$ 。

核分布：利用关系式 $\dim(\text{Hull}(C_t)) = n - \text{rank}(G_t G_t^\top)$ ，作者推导出了核维数的确切分布。
LCD 码：如果码的核维数为 0（即 Gram 矩阵满秩），则该码为 LCD 码。论文证明，在长度为 $t$ ( $n \le t \le 2^n-1$ ) 的穿孔单纯形码族中，恰好有 $2^{n-1} - 2$ 个 LCD 码。
自正交码：该族中恰好有一个自正交码（即全长度循环单纯形码）。

4. 意义与影响

新的结构洞察：这项工作揭示了 m 序列中以前未知的深层代数结构，超越了 Golomb 的经典性质，转向了矩阵论的刻画。
算法效用：显式的秩分布和 LCD 码的识别对于编码理论应用至关重要。LCD 码因其对侧信道攻击的抵抗力以及在量子纠错中的效用而备受重视。
理论框架：结合伽罗瓦半线性表示、贝祖式和有理函数枚举的方法论提供了一个强大的工具包，可被调整用于研究其他序列族或不同域上的码。
开放问题：论文最后提出了关于 $q$ 元 m 序列（特别是 $q=3$ 和 $q=5$ ）的开放问题，表明观察到的模式可能推广到其他有限域，从而邀请进一步的研究。

总之，本文弥合了序列设计与矩阵理论之间的差距，提供了对源自 m 序列的 Gram 矩阵秩性质的严格刻画，并直接将这些发现应用于优化 LCD 码的构造。