论文标题
在张量和通勤矩阵上
On tensor rank and commuting matrices
论文作者
论文摘要
在复杂性理论中，在张量等级上获得张量的超线性下限是一个主要的开放问题。在本文中，我们提出了Strassen在其3N/2边界等级下限的证明中使用的方法的概括。我们的方法围绕通勤矩阵的问题展开： 给定的矩阵z_1，...，大小为n和整数r> n的z_p，是否有通勤矩阵z'_1，...，z'_p的大小为r，使每个z_k的每个z_k都嵌入为z'_k左上角的subseDrix？ 作为我们的主要结果之一，我们表明，这个问题始终具有大于级别（t）+n的正面答案，其中t表示张张量z_1，..，z_p。采用隔开效率，如果可以显示一些特定矩阵z_1，...，z_p和一个特定的整数r，该问题具有负面答案，则会产生下限等级（t）> r-n。上面的等级（t）+n结合中有一点松弛，但是在真实和复数的字段上，我们还提供了普通和对称张量的张量等级和对称等级的许多精确特征。这些特征中的每一个都表明上述方法的相应变化。为了解释Strassen的定理在此框架中的适合，我们还提供了他的下限的独立证明。
Obtaining superlinear lower bounds on tensor rank is a major open problem in complexity theory. In this paper we propose a generalization of the approach used by Strassen in the proof of his 3n/2 border rank lower bound. Our approach revolves around a problem on commuting matrices: Given matrices Z_1,...,Z_p of size n and an integer r>n, are there commuting matrices Z'_1,...,Z'_p of size r such that every Z_k is embedded as a submatrix in the top-left corner of Z'_k? As one of our main results, we show that this question always has a positive answer for r larger than rank(T)+n, where T denotes the tensor with slices Z_1,..,Z_p. Taking the contrapositive, if one can show for some specific matrices Z_1,...,Z_p and a specific integer r that this question has a negative answer, this yields the lower bound rank(T) > r-n. There is a little bit of slack in the above rank(T)+n bound, but we also provide a number of exact characterizations of tensor rank and symmetric rank, for ordinary and symmetric tensors, over the fields of real and complex numbers. Each of these characterizations points to a corresponding variation on the above approach. In order to explain how Strassen's theorem fits within this framework we also provide a self-contained proof of his lower bound.
