The ranks of tensors between scientific application and basic understanding – a case study by Thomas Karam

This case will be devoted to the ranks of tensors. 

We will focus on the following aspects: (1) How several rank notions historically arose and came to be defined: (2) The formal definitions of some of these notions: (3) Some of the many applications of these notions, both inside mathematics and more externally to science: (4) Reasons why understanding basic properties of tensors is harder than in the matrix case, and how some analogues of matrix properties fail: (5) How these properties can nonetheless often be rectified, with two kinds of rectifications. In order to simultaneously keep the present case study within a reasonable length and be able to write with an appropriate level of detail, we have omitted or significantly limited the discussion of many highly developed, fruitful and valuable strands of research on tensors and their ranks, such as the algebraic geometry viewpoint on the ranks of tensors and approximation algorithms for tensor rank decompositions. 

Beginnings 

Although there are multiple ways of defining a notion of complexity on matrices, there is one which is widely viewed among mathematicians as being the canonical notion: the rank from linear algebra. A matrix is, among other things, a two-dimensional table, where each pair (row, column) defines a cell containing a field element. Likewise, for every integer $d \ge 2$, an order-$d$ tensor can be defined simply as a $d$-dimensional table, or equivalently as a function $[n_1] \times \dots \times [n_d] \to \mathbb{F}$, where $\mathbb{F}$ is a field and $[n]$ denotes the set $\{1,\dots,n\}$ for every positive integer

Conceiving the basic theory of linear algebra was a long process centered around the 19th century, and it will come as no surprise that tensors were scarcely studied by that time. Instead, the first notion of rank on tensors, called the tensor rank or CP-rank, among other names, arose in a paper by Hitchcock [19] in 1927, before being rediscovered in 1970 by Carroll and Chang [8] and independently by Harshman [17]. Since then, the notion has attracted attention both for its theoretically aspects and for its applications‚ as discussed, for instance, in the surveyby Kolda and Bader [24], yet as we shall mention later, many surprisingly basic challenges remain regarding that notion. 

In a much more recent development, several new algebraic notions of rank on tensors have seen the light of day in the last ten years. From the perspective of algebra, it might come as a surprise that the definition of the first of these newer notions originated, in 2016, as a key ingredient from a solution to a problem in the field of combinatorial number theory. The cap-set problem consists in proving that if a subset $A$ of $\mathbb{F}_3^n$ is such that $A \times A \times A$ contains no solutions to the equation $x+y+z=0$ other than 'diagonal' solutions of the type $(x,x,x)$, then $A$ must have size $O(C^n)$ for some $C<3$. This problem was solved in two papers, by Croot, Lev, and Pach [11] and the other by Ellenberg and Gijswijt (13), then published side by side in the Annals of Mathematics. The solution was reformulated by Tao [37] in a way that treats the three variables symmetrically, in terms of what came to be known as the slice rank notion on tensors. In that formulation, the proof consists in two bounds on the slice rank: a lower bound on the rank of an 'identity' tensor, extending the property that an identity matrix has full rank, and an upper bound on the slice rank of the tensor corresponding to the indicator of $x+y+z=0$. A year later, another notion, the partition rank, was defined by Naslund [30], again in a combinatorial context, and as the modification of the slice rank that would naturally enable a proof of existence results in $\mathbb{F}_q^n$ on a structure called $k$-right corners. 

Definitions of some rank notions

Although the tensor rank, slice rank, and partition rank each constitute a different definition of rank on tensors, there are similarities in how these notions (as well as many others) are defined. One similarity is that these notions are each defined using a common two-step process for which the second step is identical. At the first step, the set of tensors with rank at most $1$ is specified, and at the second step, the rank of a tensor $T$ is defined as the smallest nonnegative integer $k$ such that we may decompose \[T = T_1 + \dots + T_k\] for some tensors $T_1,\dots, T_k$ that each have rank at most $1$. Where the definitions differ is at the first step, in their tensors with rank at most $1$. For the tensor rank, they are the tensors that may be factored as \[T(x_1,\dots,x_d) = a_1(x_1) \dots a_d(x_d).\] For the slice rank, they are the tensors that may be factored as \[T(x_1,\dots,x_d) = a(x_j) b(x_1,\dots,x_{j-1},x_{j+1},\dots,x_d)\] for some coordinate $j \in [d]$. For the partition rank, they are the tensors that may be factored as \[T(x_1,\dots,x_d) = a(x(I)) b(x(J))\] where we write $x(I) = (x_i)_{i \in I}$ and where the sets $I,J$ of coordinates on which the functions $a,b$ depend constitute a non-trivial bipartition of $[d]$. 

It follows from their definitions that these three notions have decreasing granularity in quantifying the complexity of tensors. Indeed the inclusions between the sets of tensors with rank at most $1$ establish that the partition rank is always at most the slice rank, which in turn is always at most the tensor rank. For $d=2$ all three notions coincide and specialise to the matrix rank; for $d=3$, the slice rank and partition rank are the same notion, but may be strictly smaller than the tensor rank; the value $d=4$ is the first value for which the three notions are genuinely pairwise distinct.

More generally, whenever $R$ is a non-empty family of partitions of $[d]$, we can define a notion of $R$-rank, for which the tensors with rank at most $1$ are those that may be written as some product of functions such that the sets of coordinates on which these functions depend constitute a partition in $R$. The tensor rank, slice rank, and partition rank are then recovered by taking $R$ to contain respectively only the discrete partition of $[d]$, all bipartitions of $[d]$ with a part of size $1$, and all non-trivial bipartitions of $[d]$. Excluding the case where $R$ contains the trivial partition (which leads to the $R$-rank of a non-zero tensor always being equal to $1$), the tensor rank and partition rank may be seen to play extremal roles among the remaining notions of $R$-rank, with the tensor rank as maximum and the partition rank as minimum.

In addition to the notions of rank following the above two-step process and which fundamentally measure lengths of decompositions, other rank notions have been defined, for instance the analytic rank of Gowers and Wolf [15] and the geometric rank of Kopparty, Moshkovitz, and Zuiddam [25]. If $T$ is an order-$d$ tensor over a finite field $\mathbb{F}$ and $m$ is the corresponding $d$-linear form, then the bias of $m$ is defined as the common value \[\operatorname{bias}m = \mathbb{E}_{y^1 \in \mathbb{F}^{n_1},\dots, y^d \in \mathbb{F}^{n_d}} \chi(m(y^1,\dots,y^d))>0\] where $\chi$ is any non-trivial character, and the analytic rank of $T$, which quantifies the equidistribution of $m$, is then defined to be $- \log_{|\mathbb{F}|} \operatorname{bias} m$. Meanwhile the geometric rank is defined as the codimension of the set \[\{(y^1,\dots,y^{d-1}) \in \mathbb{F}^{n_1} \times \dots \times \mathbb{F}^{n_{d-1}}: m(y^1,\dots,y^{d-1},-) = 0\}\] of choices of the tuple of $d-1$ first coordinates at which the multilinear form $m$ evaluates to the identically zero linear form. Yet more notions, each interesting in its own way, have been developed quite recently, such as the $G$-stable rank of Derksen [12] and the local rank of Moshkovitz and Zhu [29].

Internal and external applications

Different notions of rank on tensors often serve different purposes, and the most useful of the notions often tightly depends on the specific problem at hand.

The tensor rank is widely used in computational complexity theory, and one of the most famous problems that can be reformulated in terms of the tensor rank is the problem of matrix multiplication. It has been known since the work of Strassen [36] in 1969 that there exists $c<3$ such that two $n \times n$ matrices may be multiplied using fewer than $n^c$ multiplications, and a long line of work has aimed to determine how far $c$ can be reduced. As explained for instance by Blaser [4], answering that question can be reduced to determining the tensor rank of the matrix multiplication tensor.

After the slice rank was defined, the slice rank has then continued to have applications to problems in combinatorics and Ramsey theory, such as the first exponential improvement to the size of sunflower-free families by Naslund and Sawin [31]. The slice rank has also been used by Blasiak, Church, Cohn, Grochow, Naslund, Sawin and Umans [5] to obtain bounds on the size of tricoloured sum-free sets in abelian groups with bounded exponent, and by Fox and (Miklós) Lovász [14] to obtain tight bounds for Green's arithmetic removal lemma in vector spaces of the type $\mathbb{F}_p^n$. Meanwhile, an interpretation of the slice rank in terms of lattice coverings was discovered by Sawin and Tao [34] and later used by Sauermann [34] to obtain new existence results on solutions to systems of equations in $\mathbb{F}_p^n$.

As for the partition rank, one direction that has been especially pursued has been the comparison with the previously mentioned notion of analytic rank. A long line of research has aimed to show that the partition rank and analytic rank are equivalent up to a constant. Lovett [26] and independently Kazhdan and Ziegler [23] proved that the analytic rank is at most the partition rank. In the other direction, the first general qualitative result was obtained by Green and Tao  [16] in 2009. That result was later quantitatively improved on by Janzer [20] and Milićević [23], and the current strongest two results by Moshkovitz and Cohen [29] and by Moshkovitz and Zhu [29] respectively obtain a linear equivalence between partition and analytic rank over large fields and a quasi-linear equivalence over all fields.

Yet outside of combinatorics and its surrounding areas, the ranks of tensors - and not only the tensor rank - have begun to have increasingly diverse applications in mathematics and in science more broadly. In computational complexity theory, limitations on the decoding of corrupted error correcting codes with $NC_+[\oplus]$ circuits have been obtained by Briët, Buhrman, Castro-Silva and Neumann [6], both in the classical setting and in the quantum setting, using arguments that rely in an essential way on the partition rank of tensors and the approximate equidistribution of tensors with high partition rank. A second area of application is quantum entanglement. Christandl, Lysikov and Zuiddam [10] obtained a description of bipartiteness notions for quantum entanglement in terms of an asymptotic of a weighted version of the slice rank. In neuroscience, a study by Pellegrino, Stein and Cayco-Gajic [32] published in Nature Neuroscience developed a slice rank component analysis method which they find to outperform preexisting methods in the detection of task-relevant structure in neural data for some tasks. The ranks of tensors have found significant applications in several more fields, including image compression, data mining, machine learning and signal processing. 

Difficulty sources and false properties

Despite the numerous applications of the ranks of tensors, their basic properties remain poorly understood. To give a surprisingly simple example, providing an explicit example of an $n \times n \times n$ tensor with tensor rank $\Theta(n^2)$, the order of magnitude of the highest possible tensor rank, is a famous open problem with known consequences in computational complexity theory. This situation sharply differs from the matrix case, where it is known that the $n \times n$ identity matrix has maximal rank $n$.

In terms of mathematical reasons why understanding the ranks of higher-order tensors is less straightforward than understanding the matrix rank, one can point to at least three phenomena. One reason is the complexity of computing the rank itself: it has been known since the work of Hastad [18] in 1990 that calculating the tensor rank of a given tensor is NP-hard over the rationals, and NP-complete over finite fields. A second reason is the relative absence of canonical forms: whereas every rank-$k$ matrix is equivalent, through two changes of basis of both rows and columns, to a $k \times k$ identity block completed with zeros, a counting argument shows that such a reduction cannot be hoped for in the case of tensors of order $3$ or higher. Indeed, the number of $n \times \dots \times n$ order-$d$ tensors over a finite field $\mathbb{F}$ is $|\mathbb{F}|^{n^d}$, whereas each equivalence class of tensors modulo changes of bases on each of the $d$ dimensions of the tensor has size at most $|\mathbb{F}|^{dn^2}$. Finally, a third reason is the behaviour of rank notions in terms of Zariski closure. For a given integer $k$, the set of matrices with rank at most $k$ is Zariski-closed for the matrix rank (as that property can be checked using $(k+1) \times (k+1)$ minors), but is believed to not be Zariski-closed for the partition rank, already in the case of order-$4$ tensors, as the analogous notion for polynomials (the strength) has been shown by Ballico, Bik, Oneto, and Ventura [1] to not be Zariski-closed.

Many of the basic properties that hold for matrix rank become false for the ranks of tensors when extended naively. For instance, the tensor product $A \otimes B$ of two matrices $A,B$ satisfies the multiplicativity property \[\operatorname{rk}(A \otimes B) = (\operatorname{rk} A) (\operatorname{rk}B),\] but the tensor rank (which we shall denote by $\operatorname{tr}$) only satisfies the submultiplicativity property \[\operatorname{tr} (T \otimes S) \le (\operatorname{tr} T) (\operatorname{tr} S).\] As another example, the matrix rank of a diagonal block matrix is known to be the sum of the ranks of its diagonal blocks, but the analogous property for the tensor rank, formerly a longstanding conjecture of Strassen, was disproved by a counterexample of Shitov [35] published in Acta Mathematica. 

Two kinds of rectified properties

Despite this situation, the naive extension of a property of matrix rank often has a rectification which, in addition to being true, is also simple to state, still in a spirit very close to that of the original property, and keeps a substantial part of the original property's strength. For instance, let us consider how much flexibility there is in writing a rank decomposition of a matrix with rank $k$. Decompositions of the type \[A(x,y) = f_1(x) g_1(y) + \dots + f_k(x) g_k(y)\] are strictly speaking not unique, as one can always make some change of basis on the functions $f_1,\dots,f_k$, but they are indeed unique up to this class of transformations. For the slice rank of order-$3$ tensors, where the general form of a decomposition is of the type \[T(x,y,z) = \sum_{i=1}^r a_i(x) b_i(y,z) + \sum_{j=1}^s c_j(y) d_j(x,z) + \sum_{k=1}^t e_k(z) f_k(x,y),\] the minimal-length decompositions inherit the base change flexibility from the matrix case, as each of the three parts of the decomposition may be viewed as a matrix with two axes collapsed together, but there is also another move that can be seen to yield new decompositions purely from the algebraic expressions. Choosing indices $i,j$ as well as a completely arbitrary function $e$ in the last coordinate, replacing $b_i$ by $b_i + c_j \otimes e$ and replacing $d_j$ by $d_j - a_i \otimes e$ provides a new slice rank decomposition with minimal length. The arbitrariness of the function $e$ shows that unlike in the matrix case, already over tensors of slice rank at most $2$ and over the field $\mathbb{F}_2$ the number of minimal-length decompositions is not bounded in general, even modulo base changes. Yet it was established in [21] that modulo this new transformation (together with the other two obtained from exchanging the roles of the $3$ coordinates) that number is bounded above by a function of the slice rank and of the field size, that furthermore has the same growth rate as the number of base changes for matrices.

In addition, a property of matrix rank that fails for the ranks of tensors in its original form can be restored to its full strength, or to close to its full strength, if one requires the statement to hold not for every single tensor, but for some important class of tensors (such as typical low-rank tensors). To continue the previous example, in generalising the property of having few different decompositions from matrix rank to slice rank, one may count the raw number of total decompositions, which, up to the new class of transformations, is similar for matrix rank and for slice rank, but one may also count up to changes of basis. With this viewpoint, the natural aim to mirror the matrix property then becomes the uniqueness - rather than merely boundedness - of the minimal-length slice rank decomposition modulo the two types of transformations: the new transformation above together with changes of basis. Such a statement fails anew: indeed a typical $n \times n \times n$ tensor has full slice rank $n$, and hence can be seen to have $3$ completely different slice rank decompositions with minimal length, by slicing the tensor according to each of the $3$ different directions and writing \[T(x,y,z) = \sum_{i=1}^n 1_{x=i} T(i,y,z)\] together with the two other analogous expressions. But the retort is that for a wide class of tensors that again admits a simple description, it was proved in [21] that the desired uniqueness does hold, and that class of tensors would appear to encompass random low-rank tensors.

 Let us finish by mentioning two more examples of adaptations of properties of matrix rank to the ranks of tensors. Briët and Castro-Silva {7] showed that for a large class of rank notions, a random restriction of a high-rank tensor has high rank, a result that plays a significant role in their later application [6] to the decoding of error-correcting codes. Chen and Ye [9] obtain results controlling the extent to which several ranks of tensors may change under an extension of the base field, providing a suitable generalisation of the well-known fact that the rank of a real matrix is the same over $\mathbb{R}$ and over $\mathbb{C}$. 

Last comments

It is worth emphasisng that in terms of techniques and tools, there is a rich study of the ranks of tensors using algebraic geometry and representation theory, next to all the progress that has been made involving linear algebra or combinatorics. To give an example of a sequence of such developments (among many), Bik, Draisma and Eggermont [3] have established a ‚'universality'property satisfied by the partition rank: if a non-trivial Zariski-closed condition is functorial in the underlying space, then that condition must imply boundedness of the partition rank. They also establish a similar result in the closely related setting of polynomials, which was then strengthened [22], before being extended by Bik, Danelon, Draisma, and Eggermont [2] to the more general setting of polynomial functors.

In the light of the rather accelerating developments both in their external applications and in the study of their basic properties, the ranks of tensors would therefore appear to be a subject meriting consideration and research effort.

Thomas Karam was previously a postdoctoral research associate in Oxford Mathematics and is currently a tenure-track Associate Professor at Shanghai Jiao Tong University.

References

 [1] Edoardo Ballico, Arthur Bik, Alessandro Oneto, and Emanuele Ventura, The set of forms with bounded strength is not closed, Comptes Rendus, Mathématiques, 360 (2022), 371-380. 

[2] Arthur Bik, Alessandro Danelon, Jan Draisma, Rob H. Eggermont, Universality of highstrength tensors, Vietnam Journal of Mathematics, 50 (2022), 557-580. 

[3] Arthur Bik, Jan Draisma, Rob H. Eggermont, Polynomials and tensors of bounded strength, Communications in Contemporary Mathematics, 21 (2019), 1850062. 

[4] Markus Bläser, Fast Matrix Multiplication, Theory of Computing Library Graduate Surveys 5 (2013), 1-60. 

[5] Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin, and Chris Umans, On Cap Sets and the Group-Theoretic Approach to Matrix Multiplication, Discrete Analysis (2017), 27pp.

 [6] Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels. M.P. Neumann, Noisy decoding by shallow circuits with parities: classical and quantum, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024).

[7] Jop Briët, Davi Castro-Silva, Random restrictions of high-rank tensors and polynomial maps, Discrete Analysis 9 (2024), 24 pp. 

[8] J. Douglas Carroll, Jih-Jie Chang, Analysis of individual differences in multidimensional scaling via an n-way generalization of ‘Eckart-Young’ decomposition, Psychometrika, 35 (1970), 283-319.

 [9] Qiyuan Chen, Ke Ye, Stability of ranks under field extensions, Discrete Analysis 27 (2025), 29 pp. 

[10] Matthias Christandl, Vladimir Lysikov, Jeroen Zuiddam, Weighted slice rank and a minimal correspondence to Strassen’s spectra, Journal de Mathématiques Pures et Appliquées, 172 (2023), 299-329. 

[11] Ernie Croot, Vsevolod Lev, Peter Pach, Progression-free sets in Z n 4 are exponentially small, Annals of Mathematics 185 (2017), 331-337. 

[12] Harm Derksen, The G-stable rank for tensors and the cap set problem, Algebra and Number Theory, 16 (2022), 1071-1097.