论因子宽度秩

《Linear Algebra and its Applications》：On factor-width ranks

　　

**摘要**

一个实数或复数的正半定矩阵 A，若可以表示为若干个秩-1正半定矩阵之和，且其中每个矩阵在某个 k×k 主子矩阵之外的元素均为零，则称 A 的因子宽度至多为 k。A 的因子宽度-k 秩是这种求和所需秩-1矩阵的最小个数。在 [Linear Algebra Appl. 716 (2025) 32–59] 中，Johnston、Moein 和 Plosker 开始研究这一参数。

本文扩展并改进了该文章中的若干结果，并引入了一些新结论。具体而言，我们确定了所有因子宽度-2矩阵的因子宽度-2秩，建立了它们因子宽度-3秩的上界，并细化了 n×n 矩阵因子宽度-k秩的一个基本上界。此外，我们还确定了具有特定图类型的矩阵的因子宽度秩。

**引言**

一个正半定矩阵 A（实数或复数）若存在矩阵 V 使得 A = VV?，且 V 的每一列至多有 k 个非零元素，则称 A 的因子宽度至多为 k。Boman、Chen、Parekh 和 Toledo 在文献 [3] 中首次为实矩阵定义了这一概念，并建议将 A 的因子宽度-k秩定义为这样的 V 所需的最小列数。因子宽度的概念已被应用于优化理论和量子信息领域，详见文献 [7] 的引言部分及其中的参考文献。在文献 [7] 中，Johnston、Moein 和 Plosker 将因子宽度至多为 k 和因子宽度-k秩这两个概念推广到复数情形，并开始对后者展开研究。

因子宽度-k秩的概念加入了其他"分解秩"的行列。这里特别值得关注的是 cp-秩。若存在一个元素逐元素非负的矩阵 B 使得 A = BB?，则称矩阵 A 为完全正定（CP）的。A 的 cp-秩 cpr(A) 即为这样的 B 所需的最小列数。完全正定性及其 cp-秩已被研究了数十年，文献 [8] 给出了全面的综述。cp-秩与因子宽度-k秩之间存在根本性差异。在 cp-秩的情形中，重点在于非负性；在完全正定分解 A = BB? 中，B 每列的非零元素个数并不是主要关注点（尽管 A 的零-非零模式可以给出这些个数的界）。而在因子宽度-k秩的情形中，重点恰好相反（事实上，非负性不起作用）。然而，两者有一个交集：一个完全正定矩阵 A，若存在分解 A = BB?，其中 B 为非负矩阵且 B 每列至多有两个非零元素。这一情形在文献 [4] 以及后来的文献 [2] 中得到了处理。在本文中，我们借鉴这两篇论文的结果和证明方法来研究因子宽度-2矩阵。我们在定理 4 中求出了任意因子宽度-2矩阵的因子宽度-2秩，从而推广了文献 [7] 中的若干结果。此外，我们还建立了因子宽度-2矩阵的因子宽度-3秩的上界（定理 5）。对于其他因子宽度，我们在定理 1 中改进了文献 [7] 中得到的因子宽度-k矩阵的因子宽度-k秩的上界，并在定理 6 中略微扩展了该论文的另一个结果。我们还研究了具有某些零-非零模式（由图描述）的矩阵的因子宽度秩。在引理 1 中，我们证明任何因子宽度至多为 k 的矩阵 A 都存在一个"k宽度分解" A = VV?，其中 V 的列数等于 A 的因子宽度-k秩，且 V 的各列具有互不相同的支撑集。该结果用于定理 4 的证明，并且可能对这一参数的进一步研究有所帮助。关于直接和的因子宽度-k秩的一个问题仍留为未决。

在下一节中，我们介绍符号和形式化定义，并引用关于因子宽度秩的一些基本结果。第3节证明了关于不同支撑集的结果，以及 n×n 矩阵因子宽度-k秩的改进基本上界。第4节研究因子宽度为2的矩阵及其因子宽度秩。第5节针对某些特殊图，研究具有这些图的矩阵的因子宽度和因子宽度秩。最后，在第6节中，我们利用上述部分结果在特定例子中进行应用，并回顾未决问题。

**章节摘录**

**符号与术语**

复数 z ≠ 0 的复符号记为 sgn(z)，即 sgn(z) = z/|z|。对于整数 p ≤ q，我们使用记号 [p:q] = {p, p+1, …, q}。基域 F 为 ? 或 ?。当未特别指明域时，结果对任意域均成立。按照惯例，A? 和 A? 分别表示矩阵 A 的转置和共轭转置，向量均为列向量。向量 v ∈ F? 的第 i 个分量记为 v?，v 的支撑集为 supp v = {i ∈ [1:n] | v? ≠ 0}。若 σ ? [1:n]，向量 1σ 的分量定义为：当 i ∈ σ 时为1，否则为0。若 i, j ∈ [1:n]，e? 表示第 i 个标准基向量。若 i ∈ [1:n]，|i| 表示整数 i 的绝对值。若 A = (a??) 为一个矩阵，A[i:j; k:l] 表示 A 的子矩阵，其行指标为 i, i+1, …, j，列指标为 k, k+1, …, l。对于集合 S ? [1:n]，diag(S) 表示对角矩阵，其对角线上对应于 S 的位置为1，其余为0。若 A 是一个 n×n 矩阵，σ ? [1:n]，则 A[σ] 表示 A 的主子矩阵，其行列指标均为 σ 中的元素。设 G = (V, E) 是一个图，V 为其顶点集，E 为其边集。若 A 是一个 n×n 矩阵，且 σ ? [1:n] 使得 a?? = 0 当且仅当 (i,j) ? E ∪ {(i,i) : i ∈ V}，则称 A 的图 G(A) 为 G。特别地，若 G 是一个森林（无环图），则 A 的图是一个森林。矩阵的图 G(A) 仅依赖于 A 的零-非零模式。矩阵 A 的支撑图为 A 的非零元素对应的图。若 A 是实对称或复数 Hermitian 矩阵，G(A) 也是对称的。对于图 G，δ(G) 和 Δ(G) 分别表示 G 的最小度和最大度。n-cycle C? 是 n 个顶点的环图。K? 是 n 个顶点的完全图。

**因子宽度秩的一般结果**

我们在本节中证明两个结果。给定一个因子宽度-k矩阵 A，引理 1 建立了 A 的（极小）k宽度分解的存在性，其中不存在两个具有相同支撑集的向量。该结果用于下一节，并且可能对因子宽度秩的进一步研究有所帮助。第二个结果改进了文献 [7] 中给出的 n×n 矩阵因子宽度-k秩的基本上界。

**引理 1**

设 A 是一个 n×n 正半定矩阵，其因子宽度至多为 k，且具有一个k宽度分解

A = ∑???^r v?v??

其中每个 v? 的支撑集至多包含 k 个元素。则存在一个极小的k宽度分解 A = VV?，使得 V 中不存在两个向量具有相同的支撑集。

**因子宽度-2矩阵**

在本节中，我们求出任意因子宽度-2矩阵的因子宽度-2秩。k宽度-2分解的优势在于其因子非常稀疏。然而，由于 frank?(A) 可能随 k 的增大而减小，因此可以合理地提出：是否放宽对因子稀疏度的要求（即允许稍不稀疏的因子）可能会导致左因子具有更少的列数？因此，我们同时也研究因子宽度-2矩阵的因子宽度-3秩。

**矩阵图与因子宽度秩**

在前一节中，我们研究了具有无环图（森林）的矩阵的因子宽度和因子宽度秩。现在我们考虑具有其他特殊图的矩阵的因子宽度和因子宽度秩。首先是环图。n-环图记为 C?。

**命题 4**

设 A 是一个正半定矩阵，其图 G(A) = C?，n ≥ 3。则 A 的因子宽度为 2 或 3，且 frank?(A) = rank(A)。

**证明**

这样的 A 的因子宽度不为 1，因为它不是对角矩阵；对于 n = 3 的情形，结果已为人所知。为了证明……

**一个具体例子与未决问题**

我们没有对主要结果进行总结，而是选取文献 [7, Example 2] 中的8顶点立方图 Q?，应用上述若干结果来分析与之相关的正半定矩阵的因子宽度和因子宽度秩。在讨论中，我们假设 A 是一个正半定矩阵且 G(A) = Q?，其中 Q? 的顶点编号如图 1 所示。

**例 2**

正半定矩阵 A（G(A) = Q?）的秩至少为 4，因为 A 没有零行且含有一个 4×4 的对角主子矩阵。该下界……

**致谢**

我们感谢一位认真负责的审稿人提出了若干有益的评论和修改建议。特别是，他/她提供了一个反例，指出一个具有非零元素的因子宽度-2矩阵的因子宽度-3秩不一定等于 ?n2/4?。该 5×5 的反例现已出现在注 5 中。

Naomi Shaked-Monderer