High-rank subtensors of high-rank tensors

A basic result in linear algebra is that every matrix of rank \(k\) contains a \(k\) by \(k\) submatrix of rank \(k\). A natural question is how this extends to tensors in higher dimension, that is functions from a cartesian product of finite sets \(Q_1\times \ldots \times Q_d\) to some fixed field.

For this we first need to specify an appropriate notion of rank for tensors. There are several natural generalizations, each useful in a particular context (see for instance this blog post for a rephrasing of the exponential improvement on the cap set problem using the notion of slice rank). All first specify the tensors with rank 1, and then the rank of an arbitrary tensor \(T\) is defined as the smallest \(k\) such that \(T\) can be written as a sum of \(k\) tensors of rank 1.

This paper considers in particular the tensor rank, the slice rank, and the partition rank. Tensors of tensor rank 1 are those defined as the tensor product of \(d\) vectors. The other types of ranks can be defined similarly, by restricting the dependence between the different dimensions appropriately, and each of them specialises to the matrix rank in dimension 2.

The paper first shows that there are examples in dimension 3 with slice rank equal to 4, but in which every 4 by 4 by 4 subtensor has slice rank less than 4. So the most immediate generalisation of the original matrix property in higher dimension unfortunately does not hold. However, the paper proves that for each of these rank types (and in fact any rank defined using a similar recipe), any tensor of sufficiently large rank has a bounded size subtensor of large rank.

The proof techniques are then adapted to prove an approximate min-max duality, for any tensor \(T\), between the maximum rank of all subtensors of \(T\) with pairwise disjoint coordinates sets, and the minimum rank of \(T+V\), over all tensors \(V\) where all non-zero entries have some repeated coordinates.