Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

Abstract

Abstract A three-way array X (or three-dimensional matrix) is an array of numbers xijk subscripted by three indices. A triad is a multiplicative array, xijk = aibjck. Analogous to the rank and the row rank of a matrix, we define rank (X) to be the minimum number of triads whose sum is X, and dim1(X) to be the dimensionality of the space of matrices generated by the 1-slabs of X. (Rank and dim1 may not be equal.) We prove several lower bounds on rank. For example, a special case of Theorem 1 is that rank(X)⩾dim 1 (UX) + rank(XW) − dim 1 (UXW) , where U and W are matrices; this generalizes a matrix theorem of Frobenius. We define the triple product [A, B, C] of three matrices to be the three-way array whose (i, j, k) element is given by ⩞rairbjrckr; in other words, the triple product is the sum of triads formed from the columns of A, B, and C. We prove several sufficient conditions for the factors of a triple product to be essentially unique. For example (see Theorem 4a), suppose [A, B, C] = [ A , B , C ] , and each of the matrices has R columns. Suppose every set of rank (A) columns of A are independent, and similar conditions hold for B and C. Suppose rank (A) + rank (B) + rank (C) ⩾ 2R + 2. Then there exist diagonal matrices Λ, M, N and a permutation matrix P such that A = APΛ, B = BP M , C = CP N . Our results have applications to arithmetic complexity theory and to statistical models used in three-way multidimensional scaling.