5.7.3 Tensor Simple Element Recognition

Tensor Simple Element Recognition is the problem, together with the set of tests used to solve it, of deciding whether a given element of a tensor product space is simple (pure, decomposable) — that is, whether it can be written as a single product of one vector from each factor space, rather than requiring a genuine sum of several such products.

Statement of the Recognition Problem

Given vector spaces V1, V2, …, Vn over a field F, their tensor product T = V1 ⊗ V2 ⊗ ⋯ ⊗ Vn, and an element t of T presented in coordinates, the recognition problem asks whether there exist vectors v1, …, vn with

The recognition problem has a yes-or-no answer, distinguishing it from the related but harder task of factor separation, which additionally demands producing the vectors v1, …, vn once the answer is affirmative.

Recognition in the Two-Factor Case

When n equals two, recognition reduces to a classical and completely solved question in linear algebra.

The Rank Criterion for Matrices

Identifying t with a matrix M via chosen bases of V1 and V2, t is simple exactly when M has rank at most one. Rank can be checked by row reduction, or equivalently by verifying that every 2-by-2 minor of M vanishes:

for all choices of indices i, j, k, l. This criterion is both necessary and sufficient, and it can be checked in polynomial time using standard linear algebra routines such as Gaussian elimination or singular value decomposition, where simplicity corresponds to all but the largest singular value being zero.

Recognition for Three or More Factors

Beyond two factors, recognition remains decidable but requires checking rank-one conditions on several different associated matrices rather than a single one.

Flattening-Based Necessary Conditions

Each of the n possible flattenings (matricizations) of t — obtained by grouping one factor's index against the combined indices of all remaining factors — must itself have rank at most one if t is simple. Checking all n flattenings gives a set of necessary conditions that are efficiently testable.

Sufficiency and Consistency

Rank-one flattenings in every direction are necessary but require an additional consistency check to be sufficient: the rank-one vectors recovered independently from each flattening must combine, via the tensor product, to reproduce t exactly. When this consistency check passes, simplicity is confirmed and a separation is obtained as a byproduct; when the recovered product fails to match t, the tensor is not simple even though each individual flattening looked rank-one.

Recognition Via Symmetric and Antisymmetric Structure

In tensor spaces built with additional algebraic structure, such as symmetric or exterior powers of a single vector space, recognition of simple elements takes on specialized characterizations.

Symmetric Tensors and the Veronese Variety

For symmetric tensors, arising as elements of the symmetric power of a vector space, the simple elements correspond to points of the Veronese variety, and recognition can be phrased as testing whether the associated homogeneous polynomial factors as a perfect power of a single linear form — a condition checkable via the vanishing of a catalecticant matrix's rank exceeding one.

Antisymmetric Tensors and Decomposability

For antisymmetric tensors, arising in the exterior power of a vector space, a simple (decomposable) element corresponds to representing a k-dimensional subspace via its Plücker coordinates. The recognition condition here is given by the Plücker relations, a specific system of quadratic equations that the coordinates of t must satisfy for t to correspond to an actual subspace rather than a formal antisymmetric combination with no such geometric meaning.

Numerical and Approximate Recognition

In floating-point or noisy settings, exact vanishing of the rank-one conditions is rarely observed even when a tensor is theoretically close to simple, so recognition in practice becomes a question of degree rather than a strict binary test.

Thresholded Rank Tests

A practical recognition procedure computes the relevant flattenings' singular values and checks whether the ratio of the second-largest to the largest singular value falls below a chosen tolerance, treating the tensor as effectively simple if so. This approach trades the exact algebraic criterion for a numerically stable approximate one, appropriate when t arises from measurement or floating-point computation rather than exact algebraic construction.

Best Rank-One Approximation as a Fallback

When a tensor fails recognition, the best rank-one approximation — the simple tensor closest to t in a chosen norm — is often computed regardless, giving a practically useful answer ("how close is t to being simple, and what is the nearest simple tensor") even though the strict recognition question returns a negative answer.

Complexity Considerations

While two-factor recognition is a standard, efficient linear-algebra computation, higher-order recognition and the related problem of determining exact tensor rank become computationally much harder in general, with exact tensor rank computation known to be NP-hard over general fields for tensors of three or more factors. Simple element recognition itself, being the special rank-one case, remains tractable because the necessary flattening conditions are efficiently checkable, but the broader family of related decomposition questions escalates sharply in difficulty as soon as rank exceeds one.

Illustrative Diagram

The recognition pipeline takes a tensor, runs the rank-one conditions on its flattenings, and produces a binary answer as to whether the tensor is simple.