九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

正交阵列达到 Rao 界的谱

《组合设计中的 50 个公开问题》 · 问题 04 专题综述

题面强度 t 的正交阵列 OA(λs^t, n, s, t) 何时达到 Rao 界?达到界的阵列如何分类?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

正交阵列 OA(N,n,s,t) 是一个 N×n 的表,列取值于 s 元集,任何 t 列的行向量恰把 st 种取值组合各出现 N/st = λ 次(λ 称指数)。Rao(1947)给出了 N 的下界:达到此界的阵列是 «最省行数的实验表»。本问题问:哪些参数能达到 Rao 界?达到界的阵列如何分类?这是正交阵列理论的脊柱问题——它与编码理论中的 LP 界同源,达到界情形与 MDS 码、紧框架一一对应。

主要概念

Rao 界

记 t = 2g 或 2g+1。Rao 界:N ≥ Σi=0g C(n,i)(s−1)i(t 偶);N ≥ Σi=0g C(n,i)(s−1)i + C(n−1,g)(s−1)g+1(t 奇)。最常用的是强度 2 情形(g=1):N ≥ 1 + n(s−1)。证明工具是 «正交多项式»(Krawtchouk 型)——与 Delsarte 的码 LP 界同一台机器:阵列的列对偶到 «因子空间» 的函数,计数恒等式给出二次型的非负性。

与 Hadamard、MDS 的对应

强度 2、s=2 时 Rao 界为 N ≥ n+1,达到 ⟺ Hadamard 矩阵(14 号)。一般地,达到 Rao 界的阵列等价于 «极小距离最大» 的码:把行看作长 n、字母表大小 s 的码字,OA 性质给出最小距离 δ = n−t+1(强度 t ⟹ 任何 n−t+1 列内无重复行模式),«N 达到 Rao 界» ⟺ «码达到 Singleton 界» ⟺ MDS 码。于是本问题与 36 号(MDS 猜想)互锁。

主要命题与证明

命题 1(Plackett–Burman 定理,1946,完整证明) OA(N,n,2,2) 满足 N ≥ n+1;且 N=n+1 的阵列等价于 N 阶 Hadamard 矩阵。

证明 把阵列写成 N×n 矩阵 A,元素取 ±1,并在左端添一列全 1 得 A′(N 行、n+1 列)。正交性:OA 强度 2 性质说任何两列的四种符号组合各出现 λ=N/4 次。任取两列 c,d:内积 c·d =(++ 与 −− 的次数)−(+− 与 −+ 的次数)= λ − λ = 0。特别地,取 d 为全 1 向量(它不是阵列的列,但组合均衡论证同样适用):均衡性给出每列中 +1 与 −1 各半,即每列与全 1 向量内积为 0。下界:于是 A′ 的 n+1 个列向量两两正交且皆非零,而它们都生活在 ℝN 中——两两正交的非零向量至多 N 个,故 n+1 ≤ N。等价性:设 N=n+1。此时 A′ 是 N 阶方阵且 A′TA′ = N·IN,故 A′ 可逆且 (A′)−1 = N−1A′T,从而 A′A′T = N·I 亦成立——每行也两两正交、每行范数 √N:这正是 Hadamard 矩阵的定义。反之,任何 Hadamard 矩阵可归一化(行、列乘 −1)使第一列全 1;删去该列后,其余列两两正交且与全 1 正交,即四种组合均衡——恰是 OA(N,N−1,2,2)。□

命题 2(Rao 界与 Singleton 界的对偶一致;陈述) 把 OA(N,n,s,t) 的行视为 s 元码字,得到大小 N、长 n、最小距离 ≥ n−t+1 的码(强度 t 保证 t 列模式无重复,即任何 n−t+1 列内的截断互异)。在此对应下,Rao 界与码的 Singleton 型界互为对偶:OA 的 «列数–强度» 平面与码的 «长度–距离» 平面经转置换位,Rao 界的证明正是 Delsarte LP 法在置换后的参数平面上的重演。

梗概 Delsarte 框架中,码的距离分布与 OA 的模式分布都落在 Krawtchouk 多项式张成的 «正锥» 内,两个线性规划互为对偶,故最优值相同。达到界 ⟺ LP 最优解落在有限极值点集上 ⟺ 结构为 MDS 型(对应 36 号)。□

进展与文献

Rao 1947 的因子实验纲领;Plackett–Burman 1946;Bush 1952 的正交阵列构造(达到界一族);Hedayat–Sloane–Stufken《Orthogonal Arrays》专著的系统整理;MDS 码侧见 36 号文献。开放核心:一般 (t,n,s) 达到 Rao 界的参数谱(等价于 «弧的极大谱» 问题,与 11、36 号联动);指数 λ>1 的 «广义 Rao 界» 紧性;量子信息侧的对应见 24 号。

← 返回问题 04