5.8.3 Tensor Decomposable Element Recognition

Tensor Decomposable Element Recognition is the problem of deciding, from the coordinates of a tensor, exterior power element, or symmetric power element presented relative to fixed bases, whether that element belongs to the decomposable locus — the algebraic variety of elements factoring as a single product, wedge product, or power of vectors — and the family of polynomial and numerical tests used to answer that question.

The Recognition Question in Each Setting

Decomposability recognition takes a slightly different concrete form depending on which multilinear construction the element lives in, though the underlying principle — testing membership in a variety defined by quadratic equations — is shared across all of them.

Plain Tensor Products

For an element t of V1 ⊗ V2 ⊗ ⋯ ⊗ Vn, recognition asks whether t equals a single product v1 ⊗ ⋯ ⊗ vn. This is tested by flattening t along each factor and checking that every resulting matrix has rank at most one, together with a consistency check across flattenings.

Exterior Powers

For an element ω of the p-th exterior power ⋀ᵖV, recognition asks whether ω equals a single wedge product w1 ∧ ⋯ ∧ wp. The test here is algebraically sharper than in the general tensor case: ω is decomposable exactly when its coordinates, relative to a basis, satisfy the Plücker relations,

a homogeneous quadratic system in the coordinates of ω, and equality here is a complete, purely algebraic recognition criterion.

Symmetric Powers

For an element of a symmetric power, identified with a homogeneous polynomial of degree p, recognition asks whether the polynomial is a perfect p-th power of a single linear form. The standard test uses the catalecticant matrix (a matrix built from the polynomial's coefficients acting as a linear map between spaces of lower-degree polynomials): the element is decomposable exactly when the appropriate catalecticant has rank one.

Two-Factor Case as the Foundational Model

The two-factor tensor product case underlies all the recognition criteria above, since it supplies the elementary rank-one test that flattenings and catalecticants ultimately reduce to.

Rank-One Matrix Test

Given a matrix M representing a two-factor tensor, M is decomposable exactly when every 2-by-2 minor vanishes, or equivalently when M has only one nonzero singular value. This is efficiently checkable by Gaussian elimination or singular value decomposition, and it forms the computational core that higher-order and structured recognition tests build upon.

Complexity of Recognition

Recognition, unlike the harder problem of computing exact rank for tensors of higher rank, remains computationally tractable across all the settings described.

Polynomial-Time Verifiability

Because decomposability is characterized by the vanishing of an explicit, fixed system of polynomial equations (rank-one minors, Plücker relations, or catalecticant rank conditions), checking a candidate element for decomposability is a polynomial-time computation in the dimension of the ambient space, independent of how the element was originally produced.

Contrast with General Rank Computation

Determining the exact tensor rank of an element that fails the decomposability test is, by contrast, NP-hard in general for tensors of three or more factors over generic fields. Recognition therefore occupies a comparatively easy corner of the broader landscape of tensor decomposition problems, precisely because it only asks about the smallest possible rank value.

Numerical Recognition in Practice

When elements arise from measurement or floating-point computation rather than exact algebraic construction, the polynomial recognition criteria rarely vanish exactly, and recognition becomes a matter of proximity rather than strict equality.

Tolerance-Based Testing

A practical recognition procedure evaluates the relevant rank-one or Plücker conditions and accepts decomposability when the resulting residual falls below a numerical tolerance, effectively testing whether the element lies close to the decomposable locus rather than exactly on it.

Nearest Decomposable Element

When strict recognition fails, computing the nearest decomposable element — the closest point on the decomposable variety to the given element, in a chosen norm — supplies a graded, quantitative answer in place of the binary yes-or-no recognition result, and is the standard fallback used throughout applied tensor decomposition.

Illustrative Diagram

Recognition tests whether a given point sits on the curved decomposable locus or off it, using the polynomial equations that define the locus as the practical test criterion.