Tensor & Multilinear Algebra

tensor rank

The rank of a tensor T is the smallest number r of simple tensors whose sum equals T. For an order-3 tensor that means the fewest terms in a decomposition T = sum over k=1..r of a_k (x) b_k (x) c_k. It directly generalizes the fact that a matrix of rank r is a sum of r terms u_k*v_k^T, each a rank-1 piece.

Everything you trust about matrix rank breaks for tensors of order 3 or higher. Rank can depend on whether you work over the real or the complex numbers: the very same real tensor can need more real rank-1 terms than complex ones. The maximal rank can exceed the obvious dimension bounds, and rank is not lower-semicontinuous, so a sequence of rank-2 tensors can converge to a tensor of rank 3.

That last failure forces a second notion, border rank: the smallest r such that T is a LIMIT of tensors of rank at most r. Border rank can be strictly smaller than rank, and it is what governs fast matrix-multiplication algorithms, where shaving the exponent depends on the border rank of a specific small tensor.

Be warned: computing tensor rank exactly is NP-hard over the rationals, and even deciding it over the reals is delicate. This is a genuine cliff between matrices, where rank is one Gaussian elimination away, and tensors, where rank is among the hardest invariants to pin down. Treat any clean 'rank' claim about a 3-way array with suspicion until you know which notion is meant.

T = sum_{k=1}^{r} a_k (x) b_k (x) c_k , rank(T) = min such r

Tensor rank is the fewest rank-1 (simple) terms needed to reconstruct T exactly.

A famous concrete case: the 2x2x2 matrix-multiplication tensor has rank 7 (Strassen) but border rank 7 as well; the 2x2 commutator-type tensor W = e1(x)e1(x)e2 + ... is rank 3 with border rank 2 — the textbook example that rank is not closed.

Also called
CP rankrank of a tensor