5.9.4 Tensor Product Basis Ordering

Tensor Product Basis Ordering is the choice of linear sequence imposed on the multi-index tuples of an induced tensor product basis, converting the unordered Cartesian collection of paired basis tensors into a specific, positionally addressable list, and the family of standard conventions — lexicographic, colexicographic, and mode-specific unfolding orders — used to make that choice in a consistent, widely recognized way.

The Ordering Problem

The induced basis of V1 ⊗ V2 ⊗ ⋯ ⊗ Vn is indexed by tuples (k1, …, kn) drawn from {1,…,d1} × ⋯ × {1,…,dn}, a set with no inherent linear order. Basis ordering fixes a bijection

that assigns every multi-index a single position in a flat, one-dimensional list, so that a tensor's coefficients can be written and stored as an ordinary vector once a basis ordering has been fixed.

Standard Ordering Conventions

Several particular choices of π are used often enough to have standard names, each tied to a different area of application.

Lexicographic (Row-Major) Ordering

Lexicographic ordering varies the last index k_n fastest and the first index k1 slowest, matching the row-major storage convention of many programming languages and matching the natural reading order of nested loops with the innermost loop over kn.

Colexicographic (Column-Major) Ordering

Colexicographic ordering reverses the priority, varying the first index k1 fastest and the last index kn slowest, matching the column-major storage convention used in several numerical computing environments and in the classical definition of the Kronecker product for matrices.

Consistency with the Kronecker Product

The standard identification of a decomposable tensor v1 ⊗ v2 ⊗ ⋯ ⊗ vn with the Kronecker product v1 ⊗_K ⋯ ⊗_K vn of its coefficient vectors is only valid once a specific basis ordering — conventionally colexicographic, with the last factor varying fastest in the resulting long vector under one common convention, though sources differ — has been fixed; a mismatch between the assumed ordering and the ordering actually used in a computation is a frequent, avoidable source of transposition errors in applied tensor computation.

Ordering and Tensor Unfolding

Basis ordering becomes especially consequential when a tensor is matricized (unfolded) along a chosen grouping of its factors, since the unfolding's row and column indices are themselves flattened multi-indices requiring their own internal ordering.

Mode-n Unfolding

The mode-n unfolding of a tensor arranges the tensor's entries into a matrix whose rows are indexed by kn alone and whose columns are indexed by the flattened tuple of all remaining indices, ordered according to one of the standard conventions above. Different sources (and different software libraries) adopt different default conventions for this remaining-index ordering, so the exact numerical layout of a mode-n unfolding is only fully specified once the ordering convention is stated explicitly.

Practical Impact on Algorithms

Because algorithms such as the higher-order singular value decomposition and alternating least squares fitting operate directly on mode-n unfoldings, an inconsistent ordering convention between the unfolding step and the step that reassembles factors back into a full tensor will silently produce a permuted, incorrect result rather than an outright computational failure, making basis ordering a common and often underappreciated source of implementation bugs.

Ordering Invariance of Abstract Properties

Although the numerical position of any given coefficient depends on the chosen ordering, the abstract tensor and its intrinsic invariants do not.

Coordinate-Free Quantities

Quantities such as tensor rank, norm (under a compatible inner product), and the outcome of contractions with other tensors are independent of which basis ordering was used to store the coefficient array, since these quantities are properties of the underlying multilinear algebra, and the ordering is only a bookkeeping device layered on top for computational convenience.

Permutation Relating Two Orderings

Switching from one basis ordering to another applies a fixed permutation to the flattened coefficient vector, determined entirely by the two orderings' bijections π and π′ and independent of the particular tensor being reordered; this permutation matrix can be composed with any Kronecker-product-based change-of-basis transformation to move consistently between conventions.

Illustrative Diagram

The two grids illustrate how the same two-dimensional index set is numbered differently under lexicographic versus colexicographic ordering, producing two distinct but equally valid flattened index sequences.