小阶整数称重矩阵空间的构造、分类与研究

《Discrete Mathematics》：Constructing, classifying and studying the space of small integer weighing matrices

　　

整数称重矩阵（IW-matrices）是整数值正交方阵。其一个用途是创建具有各种块结构的经典称重矩阵。在本文中，研究人员研究并分类了小尺寸n×n和重量k的整数称重矩阵空间IW(n,k)。该分类包括了所有非等价矩阵的完整列表（关于Hadamard等价和自同构群）[14]。然后，研究人员继续进行对称和反对称IW关于对称Hadamard等价的二次分类，并将其应用于射影空间称重矩阵的情况。接下来，研究人员利用该分类计算所有IW(n,k)空间以及对称和反对称子空间的基数。研究人员提供了实用算法并在Sagemath[11]中实现。在给定的Hadamard类中寻找（反对）对称IW矩阵可以对显著更高的阶数进行。特别地，研究人员解决了一些开放问题：对称W(23,16)、W(28,25)和W(30,17)，以及一个反对称W(28,25)。最后，研究人员展示了IW(7,25)的详细分类。研究人员还改进了NSOKS[30]算法，以找到整数k表示为n个整数平方和的所有可能表示。

**论文解读：小阶整数称重矩阵的构造、分类与研究**

**研究背景与问题**
正交矩阵在数学与工程领域（如线性代数、数值分析、量子力学、编码理论、密码学与组合设计）中具有核心地位。整数称重矩阵（integer weighing matrices，简称IW-matrices）是整数值正交方阵，其所有行向量具有相同范数。经典称重矩阵W(n,k)是IW(n,k)的子集，元素取自{-1,0,1}，其中Hadamard矩阵H(n) = W(n,n)是重要特例。Hadamard猜想指出H(n)对所有4的倍数n存在，该猜想可推广至称重矩阵：W(4l,k)对任意l和k≤4l非空。然而，IW(n,k)的完整分类尚不明确，且存在许多开放问题，如对称W(23,16)、W(28,25)、W(30,17)及反对称W(28,25)的构造。此外，IW矩阵与数论、格论、投影空间结构及多级Hadamard矩阵等密切相关。因此，系统研究小阶IW空间的分类、对称性及计数，对于推动经典称重矩阵的构造、解决开放问题具有重要理论价值。

**研究内容与结论**
本文由研究人员完成，发表于《Discrete Mathematics》。研究人员提出了构造、分类和研究小阶整数称重矩阵空间IW(n,k)的系统方法，包括：改进NSOKS算法以枚举整数平方和表示；定义行-lex序（row-lex ordering）并设计搜索算法，穷举所有Hadamard等价类；通过图同构计算自同构群；对对称与反对称IW进行二次分类（基于对称Hadamard等价）；利用分类结果计算各类空间的基数；并应用于射影空间称重矩阵。最终得到了所有小阶IW(n,k)（n≤7）的完整分类，解决了多个开放问题，例如发现了对称W(23,16)、W(28,25)、W(30,17)和反对称W(28,25)的存在性，并给出了IW(7,25)的详细分类。该研究为更大阶未知称重矩阵的构造（如W(35,25)）提供了基础。

**关键技术方法**（不超过250字）
（1）改进的NSOKS算法：递归枚举整数n表示为r个非负整数平方和的所有表示，通过处理多重性减少递归深度，输出PIW(1,n,k)的候选向量。
（2）行-lex序及最小化算法：定义矩阵的行字典序，通过MINCLASS算法（结合行/列取反与置换）找到每个Hadamard类的唯一最小代表矩阵。
（3）图同构方法：将IW矩阵扩展为2m×2n的矩阵E(A)，并构造有向加权二分图，利用Sagemath图论库计算自同构群与等价性。
（4）对称分类算法：基于自同构群和TAut(A)群，利用Proposition 5.2和Lemma 5.7，通过搜索满足条件的单项矩阵M，找出类中所有对称/反对称成员，并分类至SH等价。
（5）计数公式：基于原始分解，利用指数生成函数Z_k(t) = exp(PZ_k(t))计算所有IW(n,k)及对称/反对称子空间的基数。

**研究结果**
**1. 引言**
定义了PIW(m,n,k)和IW(n,k)，介绍了Hadamard等价（H等价）和转置-Hadamard等价（TH等价），并指出分类经典称重矩阵的重要性。研究人员将分类问题扩展至IW矩阵，并计划处理H与TH等价、自同构群、对称/反对称分类及计数。

**2. NSOKS算法**
改进了现有NSOKS算法，通过递归循环最大平方及其多重性，在Sagemath中实现，速度显著提高（如NSOKS(200,200)在0.3秒内输出27482种表示，而Maple需13秒）。该算法为后续搜索提供了所有候选行向量。

**3. 行-lex序与搜索算法**
定义行-lex序≤_R，证明最小矩阵的非零行/列以负值开头，且列递增。基于引理3.5（最小矩阵的前缀也最小），设计RepPIW算法，以mindepth参数控制性能，逐步构建所有最小Hadamard代表矩阵。算法输出包含所有最小元素，但可能有多余代表，后续通过同构处理。

**4. H等价与自同构**
利用扩展矩阵E(A)和二分图同构，将自同构计算转化为图自同构问题，并给出从图自同构恢复单项对(L,R)的方法。定义原始矩阵（图连通），证明原始分解定理（Theorem 4.6），并给出自同构群表达式（Theorem 4.8）：Aut(A) ? ∏ Aut(A_t) ? S_{r_t}。还设计了验证算法（Algorithm 4）以确认全自同构群，通过代码不变量（CodeInv）辅助证明非同构。

**5. 对称与反对称IW分类**
定义对称Hadamard等价（SH等价）和对称自同构群SAut(A)。提出寻找对称/反对称代表的条件（Proposition 5.2），并利用TAut(A)群的短正合列将对称子类与上同调集H^1(Z/2; Aut(A))一一对应（Corollary 5.6）。通过分类算法（Algorithm 5）枚举所有SH等价类。针对原始/非原始情况，给出对称分类定理（Theorem 5.12）和反对称分类定理（Theorem 5.13），将矩阵分解为类型I、II、III块。案例研究：对射影空间关联矩阵（PI）和称重矩阵（PW），利用PGΓL(V)群作用，证明了对称SH等价类的个数公式（Theorem 5.15），例如PW的类数为2+M_{d,q}+N_r，PI的类数为2+M_d+?N_r。

**6. 计数IW矩阵**
利用轨道-稳定子公式|[A]| = 2^{2n}n!^2 / |Aut(A)|，结合原始分解，导出指数生成函数Z_k(t) = exp(PZ_k(t))，其中PZ_k(t)由原始类贡献（Proposition 6.1）。类似地，对称/反对称计数公式为Z_k^S(t) = exp(PZ_k^S(t))和Z_k^A(t) = exp(PZ_k^A(t))（Proposition 6.5），其中PZ_k^S包含原始对称类及原始类中类型II/III块的贡献。

**7. IW(7,25)的结果**
给出了所有原始IW(m,25)（m≤7）的显式矩阵列表（共24个原始类），并标注了非对称类（6.8, 6.9, 6.13, 7.6, 7.18）。计算了每个原始类的自同构群标识符（GAP/LMFDB格式）、类基数、对称子类数量及对称自同构群大小（图1）。非原始分解（图2）列出了所有可能的块组合。总计数：|IW(7,25)| = 1,915,159,357,440，|SIW(7,25)| = 14,813,808，|AIW(7,25)| = 0。原始矩阵占比84.8%。

**总结与讨论**
研究人员通过系统的方法，完整分类了小阶整数称重矩阵空间，解决了多项开放问题（对称W(23,16)、W(28,25)、W(30,17)及反对称W(28,25)的存在性）。研究表明，对称与反对称IW矩阵在中小阶数中非常丰富，建议未来解决称重矩阵开放问题时优先从对称实例入手。论文提供的算法（Sagemath实现）和分类数据（发表于[14]）为后续研究奠定了基础。研究结论强调：原始分解、自同构群计算和对称分类技术可推广至更大阶数，且计数公式有效降低了计算量。