1.2.37 Tensor Rank Definition

Tensor rank measures the minimum number of rank-one tensors needed to express a given tensor, fundamental in multilinear algebra and applications.

Tensor Rank Definition is the characterization of the minimum number of decomposable, or simple, tensors whose sum equals a given tensor, generalizing the familiar notion of matrix rank to tensor product spaces built from three or more factors as well as two. Tensor rank measures how far a tensor is from being decomposable and serves as the fundamental invariant used to classify, compress, and compare tensors throughout multilinear algebra.

Formal Definition

Let $V_{1}, \dots, V_{k}$ be finite-dimensional vector spaces over a field $F$ , and let $T$ be an element of the tensor product space $V_{1} \otimes \dots \otimes V_{k}$ . The tensor rank of $T$ , written $rank (T)$ , is the smallest nonnegative integer $R$ such that $T$ can be written as

T = \sum_{α = 1}^{R} v_{1}^{α} \otimes \dots \otimes v_{k}^{α}

for some choice of vectors $v_{i}^{α} \in V_{i}$ . The zero tensor has rank zero by convention, and a nonzero decomposable tensor has rank exactly one. An expression achieving the minimum value $R$ is called a rank decomposition of $T$ .

Basic Bounds and Properties

Upper Bound from Basis Expansion

Any tensor in a finite-dimensional tensor product space admits some finite decomposition into decomposable tensors, since expanding each argument in a chosen basis and applying multilinearity of the canonical tensor product map produces such a sum. Consequently, tensor rank is always finite and bounded above by the number of nonzero coordinates of $T$ relative to any product basis, giving a crude but always-available upper bound.

Maximum Possible Rank

For a tensor product of finite-dimensional spaces of dimensions $n_{1}, \dots, n_{k}$ , the rank of any element is bounded above by

rank (T) \leq \min (\prod_{i \neq j}^{⋮} n_{i}, \dots)

More precisely, the rank never exceeds the product of any $k - 1$ of the $k$ dimensions, since a tensor can always be reorganized as a matrix by grouping all but one factor together and applying ordinary matrix rank bounds to that regrouping.

The Two-Factor Case Coincides with Matrix Rank

For a tensor product of exactly two factors, $V \otimes W$ , tensor rank coincides exactly with the ordinary rank of the matrix representing the tensor in coordinates. This follows because a decomposable tensor $v \otimes w$ corresponds to a rank-one matrix, the outer product of the coordinate vectors of $v$ and $w$ , and a sum of $R$ such rank-one matrices has matrix rank at most $R$ , with equality achievable by an optimal choice of terms — precisely the content of the singular value decomposition, which produces a rank decomposition using the minimal number of terms. This coincidence makes the two-factor case fully solved: tensor rank is efficiently computable, and a minimal decomposition is efficiently constructible, using standard linear algebra.

Higher-Order Tensor Rank

Divergence from Matrix-Based Intuition

For tensor products of three or more factors, tensor rank behaves in ways that have no analogue in the two-factor case. The rank of a higher-order tensor can exceed both of its "flattened" matrix ranks obtained by grouping factors together, and unlike matrices, higher-order tensors need not have a well-defined singular value decomposition that simultaneously minimizes rank across all groupings. The set of tensors of rank at most $R$ is, for $k \geq 3$ , generally not a closed set, meaning a tensor of rank $R$ can sometimes be approximated arbitrarily closely by tensors of strictly smaller rank without ever being reachable as an exact limit — a phenomenon with no two-factor analogue, and one that motivates the related notion of border rank.

Computational Difficulty

Determining the exact tensor rank of a given tensor of order three or higher is, in general, an NP-hard problem, and even the maximum possible rank achievable by tensors in a given tensor product space of three or more factors is not known exactly in most cases, in sharp contrast to the two-factor case where the maximum rank is simply the smaller of the two dimensions. This computational difficulty is one of the primary reasons higher-order tensor decomposition is treated as a distinct and substantially harder subject than matrix decomposition.

Applications of Low-Rank Tensor Decomposition

Expressing a tensor as a sum of few decomposable tensors, known as a canonical polyadic or CP decomposition, is a central technique for analyzing and compressing multidimensional data across signal processing, chemometrics, and machine learning. A famous application of tensor rank occurs in the analysis of matrix multiplication: the bilinear operation of multiplying two matrices can itself be encoded as a specific tensor, and the rank of that tensor determines the minimum number of scalar multiplications required by any algorithm for matrix multiplication, a connection that underlies fast matrix multiplication algorithms discovered by finding low-rank decompositions of the corresponding tensor.

Role Within Tensor Algebra

Tensor rank provides the natural stratification of a tensor product space by algebraic complexity, generalizing the role that matrix rank plays for two-factor tensor products. It quantifies precisely how far a tensor departs from the decomposable tensors that generate the space, connects the abstract structure of the tensor product to concrete computational and algorithmic questions, and marks one of the sharpest points of divergence between the well-understood two-factor theory and the substantially more intricate theory governing tensors built from three or more factors.