# A generalization of Kruskal’s theorem on tensor decomposition

Benjamin Lovitz emails<EMAIL_ADDRESS><EMAIL_ADDRESS>Fedor
Petrov

###### Abstract

Kruskal’s theorem states that a sum of product tensors constitutes a unique
tensor rank decomposition if the so-called k-ranks of the product tensors are
large. We prove a “splitting theorem” for sets of product tensors, in which
the k-rank condition of Kruskal’s theorem is weakened to the standard notion
of rank, and the conclusion of uniqueness is relaxed to the statement that the
set of product tensors splits (i.e. is disconnected as a matroid). Our
splitting theorem implies a generalization of Kruskal’s theorem. While several
extensions of Kruskal’s theorem are already present in the literature, all of
these use Kruskal’s original permutation lemma, and hence still cannot certify
uniqueness when the k-ranks are below a certain threshold. Our generalization
uses a completely new proof technique, contains many of these extensions, and
can certify uniqueness below this threshold. We obtain several other useful
results on tensor decompositions as consequences of our splitting theorem. We
prove sharp lower bounds on tensor rank and Waring rank, which extend
Sylvester’s matrix rank inequality to tensors. We also prove novel uniqueness
results for non-rank tensor decompositions.

###### Contents

  1. 1 Introduction
    1. 1.1 Kruskal’s theorem, and a generalization
    2. 1.2 A splitting theorem for product tensors
    3. 1.3 Further applications of the splitting theorem to tensor decompositions
  2. 2 Acknowledgments
  3. 3 Mathematical preliminaries
  4. 4 Proving the splitting theorem
  5. 5 Using our splitting theorem to generalize Kruskal’s theorem
  6. 6 The inequality appearing in our splitting theorem cannot be weakened
  7. 7 Interpolating between our generalization of Kruskal’s theorem and an offshoot of our splitting theorem
    1. 7.1 Low-rank tensors in the span of a set of product tensors
      1. 7.1.1 $s=1$ case of Theorem 15
      2. 7.1.2 $s=n-1$ case of Theorem 15
    2. 7.2 Uniqueness results for non-rank decompositions
      1. 7.2.1 $s=1$ case of Theorem 22
      2. 7.2.2 Modifying Theorem 22 to apply to reducible pairs of decompositions
      3. 7.2.3 $s=n-1$ case of Theorem 27
  8. 8 A lower bound on tensor rank
    1. 8.1 Our tensor rank lower bound is sharp
  9. 9 A uniqueness result for non-Waring rank decompositions
    1. 9.1 The inequality appearing in our uniqueness result is sharp
    2. 9.2 Applications of non-rank uniqueness results
  10. 10 Comparing our generalization of Kruskal’s theorem to the uniqueness criteria of Domanov, De Lathauwer, and Sørensen
    1. 10.1 Uniqueness below the k-rank threshold of DLS
    2. 10.2 Extending several uniqueness criteria of DLS
      1. 10.2.1 Conditions U, H, C, and S
      2. 10.2.2 Synthesizing the uniqueness criteria of DLS
    3. 10.3 Conjectural generalization of all uniqueness criteria of DLS
  11. 11 Appendix

##  1 Introduction

Let $[m]=\\{1,\dots,m\\}$ when $m$ is a positive integer, and let $[0]=\\{\\}$
be the empty set. For vector spaces $\mathcal{V}_{1},\dots,\mathcal{V}_{m}$
over a field $\mathbb{F}$, a product tensor in
$\mathcal{V}=\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}$ is a non-zero
tensor $z\in\mathcal{V}$ of the form ${z=z_{1}\otimes\dots\otimes z_{m}}$,
with $z_{j}\in\mathcal{V}_{j}$ for all $j\in[m]$. We refer to the spaces
$\mathcal{V}_{j}$ that make up the space $\mathcal{V}$ as subsystems. The
tensor rank (or rank) of a tensor $v\in\mathcal{V}$, denoted by
$\operatorname{rank}(v)$, is the minimum number $n$ for which $v$ is the sum
of $n$ product tensors. A decomposition of $v$ into a sum of
$\operatorname{rank}(v)$ product tensors is called a tensor rank decomposition
of $v$. An expression of $v$ as a sum of product tensors (not necessarily of
minimum number) is known simply as a decomposition of $v$. A decomposition of
$v$

$\displaystyle v=\sum_{a\in[n]}x_{a}$ (1)

into a sum of product tensors $\\{x_{a}:a\in[n]\\}$ is said to be the unique
tensor rank decomposition of $v$ if for any decomposition

$\displaystyle v=\sum_{a\in[r]}y_{a}$ (2)

of $v$ into the sum of $r\leq n$ product tensors $\\{y_{a}:a\in[r]\\}$, it
holds that $r=n$ and ${\\{x_{a}:a\in[n]\\}}={\\{y_{a}:a\in[n]\\}}$ as
multisets. The decomposition (1) is said to be unique in the $j$-th subsystem
if for any other decomposition (2), it holds that $r=n$ and there exists a
permutation $\sigma\in S_{n}$ such that
$x_{a,j}\in\operatorname{span}\\{y_{\sigma(a),j}\\}$ for all $a\in[n]$.
Kruskal’s theorem gives sufficient conditions for a given decomposition to
constitute a unique tensor rank decomposition [Kru77]. We refer to results of
this kind as uniqueness criteria.

Uniqueness criteria have found scientific applications in signal processing
and spectroscopy, among others [Lat11, Lan12, CMDL+15, SDLF+17]. In these
circles, subsystems are also referred to as factors and loadings, and the
tensor rank decomposition is also referred to as the canonical decomposition
(CANDECOMP), parallel factor (PARAFAC) model, canonical polyadic (CP)
decomposition, and topographic components model. Uniqueness of a tensor
decomposition is also referred to as specific identifiability, and uniqueness
criteria as identifiability criteria.

###  1.1 Kruskal’s theorem, and a generalization

For a finite set $S$, let $\lvert S\rvert$ be the size of $S$. The Kruskal-
rank (or k-rank) of a multiset of vectors $\\{u_{1},\dots,u_{n}\\}$, denoted
by ${\operatorname{k-rank}(u_{1},\dots,u_{n})}$, is the largest number $k$ for
which $\dim\operatorname{span}\\{u_{a}:a\in S\\}=k$ for every subset
$S\subseteq[n]$ of size $\lvert S\rvert=k$. Similarly, we call
$\dim\operatorname{span}\\{u_{a}:a\in[n]\\}$ the standard rank (or rank) of
$\\{u_{1},\dots,u_{n}\\}$. Kruskal’s theorem states that if a collection of
product tensors $\\{x_{a,1}\otimes\dots\otimes x_{a,m}:a\in[n]\\}$ has large
enough k-ranks $k_{j}=\operatorname{k-rank}(x_{1,j},\dots,x_{n,j})$, then
their sum constitutes a unique tensor rank decomposition. This theorem was
originally proven for $m=3$ subsystems over  [Kru77], was later extended to
more than three subsystems by Sidiropoulos and Bro [SB00], and then extended
to an arbitrary field by Rhodes [Rho10].

######  Theorem 1 (Kruskal’s theorem).

Let $n\geq 2$ and $m\geq 3$ be integers, let
${\mathcal{V}=\mathcal{V}_{1}\otimes\cdots\otimes\mathcal{V}_{m}}$ be a vector
space over a field $\mathbb{F}$, and let

$\displaystyle\\{{x_{a,1}}\otimes\dots\otimes
x_{a,m}:a\in[n]\\}\subseteq\mathcal{V}\setminus\\{0\\}$ (3)

be a multiset of product tensors. For each $a\in[n]$, let
$x_{a}={x_{a,1}}\otimes\dots\otimes x_{a,m}.$ For each $j\in[m]$, let

$\displaystyle k_{j}=\operatorname{k-rank}(x_{1,j},\dots,x_{n,j}).$ (4)

If ${2n\leq\sum_{j=1}^{m}(k_{j}-1)+1},$ then $\sum_{a\in[n]}x_{a}$ constitutes
a unique tensor rank decomposition.

In [Der13] it is shown that the inequality appearing in Kruskal’s theorem
cannot be weakened: there exist cases in which
${2n=\sum_{j=1}^{m}(k_{j}-1)+2}$ and the decomposition is not unique. While
Kruskal’s theorem gives sufficient conditions for uniqueness, necessary
conditions are obtained in [Kri93, Str83, LS01]. In [COV17a] it is shown that
Kruskal’s theorem is effective over  or $\mathbb{C}$ in the sense that it
certifies uniqueness on a dense open subset of the smallest semialgebraic set
containing the set of rank $n$ tensors. A robust form of Kruskal’s theorem is
proven in [BCV14].

Our main result in this work is a “splitting theorem,” which is not itself a
uniqueness criterion, but implies a criterion that generalizes Kruskal’s
theorem. In our splitting theorem, the k-rank condition in Kruskal’s theorem
is relaxed to a standard rank condition. In turn, the conclusion is also
relaxed to a statement describing the linear dependence of the product
tensors. Before stating our splitting theorem, we first introduce the
generalization of Kruskal’s theorem it implies.

######  Theorem 2 (Generalization of Kruskal’s theorem).

Let $n\geq 2$ and $m\geq 3$ be integers, let
$\mathcal{V}=\mathcal{V}_{1}\otimes\cdots\otimes\mathcal{V}_{m}$ be a vector
space over a field $\mathbb{F}$, and let

$\displaystyle\\{{x_{a,1}}\otimes\dots\otimes
x_{a,m}:a\in[n]\\}\subseteq\mathcal{V}\setminus\\{0\\}$ (5)

be a multiset of product tensors. For each $a\in[n]$, let
$x_{a}={x_{a,1}}\otimes\dots\otimes x_{a,m}$. For each subset $S\subseteq[n]$
and index $j\in[m]$, let

$\displaystyle d_{j}^{S}=\dim\operatorname{span}\\{x_{a,j}:a\in S\\}.$ (6)

If $\;2\lvert S\rvert\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1$ for every subset
$S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$, then $\sum_{a\in[n]}x_{a}$
constitutes a unique tensor rank decomposition.

Note that the computational cost of checking the conditions of our Theorem 2
is essentially the same as that of checking the conditions of Kruskal’s
theorem. In both cases, the quantities $d_{j}^{S}$ must be computed for all
$j\in[m]$ and $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$. To verify
Kruskal’s conditions, one uses these quantities to compute the Kruskal ranks,
and then checks the single inequality $2n\leq\sum_{j=1}^{m}(k_{j}-1)+1$. To
verify the conditions of our generalization, one checks a separate inequality
$\;2\lvert S\rvert\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1$ for every $S$.

To see that Theorem 2 contains Kruskal’s theorem, assume the conditions of
Kruskal’s theorem hold and note that for any subset $S\subseteq[n]$, the
multiset of product tensors $\\{x_{a}:a\in S\\}$ satisfies
$d_{j}^{S}\geq\min\\{k_{j},\lvert S\rvert\\}$. Using this fact, it is easy to
verify that ${2\lvert S\rvert\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1}$ for every
subset $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$.

In Section 10 we compare Theorem 2 to the uniqueness criteria of Domanov, De
Lathauwer, and Sørensen (DLS), which are the only known extensions of
Kruskal’s theorem that we are aware of [DL13a, DL13b, DL14, SL15, SDL15]. All
of these extensions rely on Kruskal’s original permutation lemma, and as a
result, still require the k-ranks to be above a certain threshold. Our
generalization uses a completely new proof technique, can certify uniqueness
below this threshold, and contains many of these extensions. The cited results
of DLS contain many similar but incomparable criteria, which can be difficult
to keep track of. For clarity and future reference, in Theorem 36 we
synthesize these criteria into a single statement. Using insight gained from
this synthesization and our generalization of Kruskal’s theorem, we propose a
conjectural uniqueness criterion that would contain and unify every uniqueness
criteria of DLS into a single, elegant statement.

For $m\geq 4$, Kruskal’s theorem can be “reshaped” by regarding multiple
subsystems as a single subsystem. In Section 5 we present an analogous
reshaping of Theorem 2, which has many more degrees of freedom to choose from
than the reshaped Kruskal’s theorem.

###  1.2 A splitting theorem for product tensors

We now state our splitting theorem, which we use in Section 5 to prove our
generalization of Kruskal’s theorem, and in Sections 7, 8, and 9 to obtain
further results on tensor decompositions. We first require a definition.

######  Definition 3.

Let $n\geq 2$ be an integer, and let $\mathcal{V}$ be a vector space over a
field $\mathbb{F}$. We say that a multiset of non-zero vectors
$\\{v_{1},\dots,v_{n}\\}\subseteq\mathcal{V}\setminus\\{0\\}$ splits, or is
disconnected, if there exists a subset $S\subseteq\\{v_{1},\dots,v_{n}\\}$
with $1\leq\lvert S\rvert\leq n-1$ for which

$\displaystyle\operatorname{span}\\{v_{1},\dots,v_{n}\\}=\operatorname{span}(S)\oplus\operatorname{span}(S^{c}),$
(7)

where $S^{c}:=\\{v_{1},\dots,v_{n}\\}\setminus S$. In this case, we say that
$S$ separates $\\{v_{1},\dots,v_{n}\\}$. If $\\{v_{1},\dots,v_{n}\\}$ does not
split, then we say it is connected.

Note that $\\{v_{1},\dots,v_{n}\\}$ splits if and only if it is disconnected
as a matroid [Oxl06]. We now state our main result.

######  Theorem 4 (Splitting theorem).

Let $n\geq 2$ and $m\geq 2$ be integers, let
$\mathcal{V}=\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}$ be a vector
space over a field $\mathbb{F}$, let

$\displaystyle E=\\{x_{a,1}\otimes\dots\otimes
x_{a,m}:a\in[n]\\}\subseteq\mathcal{V}\setminus\\{0\\}$ (8)

be a multiset of product tensors, and for each $j\in[m]$, let

$\displaystyle d_{j}=\dim\operatorname{span}\\{x_{a,j}:a\in[n]\\}.$ (9)

If $\dim\operatorname{span}(E)\leq\sum_{j=1}^{m}(d_{j}-1)$, then $E$ splits.

In Section 6 we use Derksen’s result [Der13] to prove that the inequality
appearing in Theorem 4 cannot be weakened.

We now give a rough sketch of how our splitting theorem implies Theorem 2,
which we formalize in Section 5. First, a direct consequence of Theorem 4 is
that $E$ splits whenever $n\leq\sum_{j=1}^{m}(d_{j}-1)+1$ (see Corollary 10).
To prove Theorem 2, let $\\{x_{a}:a\in[n]\\}$ be a multiset of product tensors
satisfying the assumptions of Theorem 2, and let $\\{y_{a}:a\in[r]\\}$ be a
multiset of $r\leq n$ product tensors for which
$\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$. Consider the multiset of $[n+r]$
product tensors

$\displaystyle E=\\{x_{a}:a\in[n]\\}\cup\\{-y_{a}:a\in[r]\\}.$ (10)

Since $2n\leq\sum_{j=1}^{m}(d_{j}^{[n]}-1)+1$, $E$ splits. Since
$\Sigma(E)=0$, it follows that $\Sigma(S)=\Sigma(S^{c})=0$ for any separator
$S$ of $E$. Now, continue applying the splitting theorem to $S$ and $S^{c}$,
until every multiset has size 2, and contains one element each of
${\\{x_{a}:a\in[n]\\}}$ and ${\\{-y_{a}:a\in[r]\\}}$.

###  1.3 Further applications of the splitting theorem to tensor
decompositions

In Sections 7, 8, and 9 we use the splitting theorem to prove further
uniqueness results and sharp lower bounds on tensor rank. In Section 7 we
prove a general statement that interpolates between our generalization of
Kruskal’s theorem and a natural offshoot of our splitting theorem (mentioned
above), obtaining uniqueness results for weaker notions of uniqueness. In
Section 8 we prove sharp lower bounds on tensor rank and Waring rank, a notion
of rank for symmetric tensors. In Sections 7 and 9 we obtain uniqueness
results for non-rank decompositions, a novel concept introduced in this work.
We close this introduction by reviewing these results in more detail.

It is known that if a multiset of product tensors ${\\{x_{a}:a\in[n]\\}}$
satisfies

$\displaystyle{n+r\leq\sum_{j=1}^{m}(k_{j}-1)+1}$ (11)

for $r=0$, then it is linearly independent, and if it satisfies (11) for
$r=1$, then the only product tensors in
$\operatorname{span}\\{x_{a}:a\in[n]\\}$ are scalar multiples of
$x_{1},\dots,x_{n}$ [HK15]. When ${r=n}$, it holds that $\sum_{a\in[n]}x_{a}$
constitutes a unique tensor rank decomposition, by Kruskal’s theorem. It is
natural to ask what happens for $r\in\\{0,1,\dots,n\\}$. In Section 7.1 we use
our splitting theorem to prove that when the inequality (11) holds, the only
rank ${\leq r}$ tensors in ${\operatorname{span}\\{x_{a}:a\in[n]\\}}$ are
those that can be written (uniquely) as a linear combination of ${\leq r}$
elements of $\\{x_{a}:a\in[n]\\}$, which interpolates between Kruskal’s
theorem for $r=n$, and the results of [HK15] for $r\in\\{0,1\\}$. We
generalize our interpolating statement in a similar manner to our
generalization of Kruskal’s theorem (Theorem 15). We also interpolate to
weaker notions of uniqueness, which are explained further at the end of this
introduction. We remark that the ${m=2,r=0}$ case of a result in this section
was proven by Pierpaola Santarsiero in unpublished work, using a different
proof technique.

The interpolating statement described in the previous paragraph immediately
implies the following lower bound on tensor rank:

$\displaystyle\operatorname{rank}\bigg{[}\sum_{a\in[n]}x_{a}\bigg{]}\geq\min\bigg{\\{}n,\sum_{j=1}^{m}(k_{j}-1)+2-n\bigg{\\}}.$
(12)

In Section 8 we use our splitting theorem to improve this bound. Namely,
provided that the k-ranks are sufficiently balanced, we prove that two of the
k-ranks $k_{i},k_{j}$ appearing in this bound can be replaced by standard
ranks $d_{i},d_{j}$, improving this bound when the ranks and k-ranks are not
equal. Our improved bound specializes to Sylvester’s matrix rank inequality
when $m=2$ [HJ13]. In Section 8.1 we prove that our improved bound is sharp in
a wide parameter regime.

In Section 9 we use our splitting theorem to prove uniqueness results for non-
Waring rank decompositions of symmetric tensors. (Our terminology for
symmetric tensor decompositions is analogous to that of general tensor
decompositions, and we refer the reader to Section 3 for a formal
introduction.) In particular, we prove a condition on a symmetric
decomposition $v=\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$ for which any
other symmetric decomposition must contain at least $r_{\min}$ terms, where
$r_{\min}$ depends on the rank and k-rank of $\\{v_{a}:a\in[n]\\}$. For
$r_{\min}\leq n$, this gives a Waring rank lower bound that is contained in
our lower bound described in the previous paragraph. For $r_{\min}=n+1$, this
gives a uniqueness result for symmetric tensors that is contained in Theorem
2, but is stronger than Kruskal’s theorem in a wide parameter regime. Our main
contribution in this section is the case $r_{\min}>n+1$, which produces an
even stronger statement than uniqueness: There are no symmetric decompositions
of $v$ into a linear combination of fewer than $r_{\min}$ terms, aside from
$v=\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$ (up to trivialities). This is an
example of what we call a uniqueness result for non-rank decompositions of a
tensor.

In Section 7.2 we prove further uniqueness results for non-rank decompositions
of (possibly non-symmetric) tensors. In particular, we give conditions on a
multiset of product tensors $\\{x_{a}:a\in[n]\\}$ for which whenever
$\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$ for some $r>n$ and multiset of
product tensors $\\{y_{a}:a\in[r]\\}$, there exist subsets $R\subseteq[n]$,
$Q\subseteq[r]$ such that $\lvert Q\rvert=\lvert R\rvert=q$ for some fixed
positive integer $q$, and $\\{x_{a}:a\in Q\\}=\\{y_{a}:a\in R\\}$. In contrast
to our non-rank uniqueness results of Section 9, which apply only to symmetric
decompositions of symmetric tensors, the results of this subsection apply to
arbitrary tensor decompositions.

In Section 9.2 we identify two potential applications of our uniqueness
results for non-rank decompositions: First, they allow us to define a natural
hierarchy of tensors in terms of “how unique” their decompositions are.
Second, any uniqueness result for non-rank decompositions can be turned around
to produce a result in the more standard setting, in which one starts with a
decomposition into $n$ terms, and wants to control the possible decompositions
into fewer than $n$ terms.

From the proof sketch of our generalization of Kruskal’s theorem that appears
at the end of the previous subsection, it is easy to surmise that if
$\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$, and
$2n\leq\sum_{j=1}^{m}(d_{j}^{[n]}-1)+1$, then there exist non-trvial subsets
$Q\subseteq[n]$ and $R\subseteq[r]$ for which $\sum_{a\in Q}x_{a}=\sum_{a\in
R}y_{a}$. This conclusion can be viewed as an extremely weakened form of
uniqueness, and it is natural to ask what statements can be made for notions
of uniqueness in between the standard one and this weakened one. We answer
this question in Sections 7.1 and 7.2.

We say that a set of non-zero vectors forms a circuit if it is linearly
dependent and any proper subset is linearly independent. As a special case of
our splitting theorem, in Corollary 21 we obtain an upper bound on the number
of subsystems $j\in[m]$ for which a circuit of product tensors can have
$d_{j}\geq 2$. This improves recent bounds obtained in [BBCG18, Bal20], and is
sharp.

##  2 Acknowledgments

BL thanks Edoardo Ballico, Luca Chiantini, Matthias Christandl, Harm Derksen,
Dragomir Đoković, Ignat Domanov, Timothy Duff, Joshua A. Grochow, Nathaniel
Johnston, Joseph M. Landsberg, Lieven De Lathauwer, Chi-Kwong Li, Daniel
Puzzuoli, Pierpaola Santarsiero, William Slofstra, Hans De Sterck, and John
Watrous for helpful discussions and comments on drafts of this manuscript. BL
thanks Luca Chiantini and Pierpaola Santarsiero for helpful feedback on
Sections 8 and 9. In previous work [Lov18], BL conjectured a (slightly weaker)
“non-minimal version” of Theorem 4. BL thanks Harm Derksen for suggesting the
splitting version that appears here. BL thanks Dragomir Đoković for first
suggesting a connection to Kruskal’s theorem, and for suggesting that these
results might hold over an arbitrary field. BL thanks Joshua A. Grochow for
first asking about uniqueness results for non-rank decompositions, which
inspired our results in Sections 7.2 and 9.

##  3 Mathematical preliminaries

Here we review some mathematical background for this work that was not covered
in the introduction. For vector spaces $\mathcal{V}_{1},\dots,\mathcal{V}_{m}$
over a field $\mathbb{F}$, we use
$\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$ to denote
the set of (non-zero) product tensors in
$\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}$. This set forms an
algebraic variety given by the affine cone over the Segre variety
$\mathrm{Seg}(\mathbb{P}\mathcal{V}_{1}\times\dots\times\mathbb{P}\mathcal{V}_{m})$,
with the point $0$ removed. We use symbols like $a,b$ to index tensors, and
symbols like $i,j$ to index subsystems. For vector spaces $\mathcal{V}$ and
$\mathcal{W}$, let $\mathrm{L}(\mathcal{V},\mathcal{W})$ denote the space of
linear maps from $\mathcal{V}$ to $\mathcal{W}$. We use the shorthand
$\mathrm{L}(\mathcal{V})=\mathrm{L}(\mathcal{V},\mathcal{V})$. For a vector
space $\mathcal{V}$ of dimension $d$, let $\\{e_{1},\dots,e_{d}\\}$ be a
standard basis for $\mathcal{V}$.

For a product tensor
$z\in\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$, the
vectors ${z_{j}\in\mathcal{V}_{j}}$ for which ${z=z_{1}\otimes\dots\otimes
z_{m}}$ are uniquely defined up to scalar multiples
$\alpha_{1}z_{1},\dots,\alpha_{m}z_{m}$ such that
$\alpha_{1}\cdots\alpha_{m}=1$. For positive integers $n$ and $m$, we
frequently define multisets of product tensors

$\displaystyle\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
(13)

without explicitly defining corresponding vectors $\\{x_{a,j}\\}$ such that

$\displaystyle x_{a}=x_{a,1}\otimes\dots\otimes x_{a,m}$ (14)

for all $a\in[n]$. In this case, we implicitly fix some such vectors, and
refer to them without further introduction.

We use the notation

$\displaystyle x_{a,\hat{j}}$ $\displaystyle=x_{a,1}\otimes\dots\otimes
x_{a,j-1}\otimes x_{a,j+1}\otimes\dots\otimes x_{a,m},$ (15)
$\displaystyle\mathcal{V}_{\hat{j}}$
$\displaystyle=\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{j-1}\otimes\mathcal{V}_{j+1}\otimes\dots\otimes\mathcal{V}_{m},$
(16)

so $x_{a,\hat{j}}\in\mathcal{V}_{\hat{j}}$. Note that
$\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}$ is naturally isomorphic to
$\mathrm{L}(\mathcal{V}_{j}^{*},\mathcal{V}_{\hat{j}})$ for any $j\in[m]$,
where $\mathcal{V}_{j}^{*}$ is the dual vector space to $\mathcal{V}_{j}$. The
rank of a tensor in $\mathcal{V}_{1}\otimes\mathcal{V}_{2}$ is equal to the
rank of the corresponding linear operator in
$\mathrm{L}(\mathcal{V}_{1}^{*},\mathcal{V}_{2})$. We denote the rank of a
tensor $v\in\mathcal{V}$, viewed as an element of
$\mathrm{L}(\mathcal{V}_{j}^{*},\mathcal{V}_{\hat{j}})$, by
$\operatorname{rank}_{j}(v)$. The flattening rank of $v$ is defined as
$\max\\{\operatorname{rank}_{1}(v),\dots,\operatorname{rank}_{m}(v)\\}$. Note
that the tensor rank of $v$ is lower bounded by the flattening rank of $v$.

We write $S\cup T$ to denote the union of two sets $S$ and $T$. If $S$ and $T$
happen to be disjoint, we often write $S\sqcup T$ instead to remind the reader
of this fact. For a positive integer $t$, we say that a collection of subsets
$S_{1},\dots,S_{t}\subseteq T$ partitions $T$ if $S_{p}\cap S_{q}=\\{\\}$ for
all $p\neq q\in[t]$, and $S_{1}\sqcup\dots\sqcup S_{t}=T$.

For a multiset of non-zero vectors
$E=\\{v_{1},\dots,v_{n}\\}\subseteq\mathcal{V}$, a connected component of $E$
is an inclusion-maximal connected subset of $E$. Any multiset of non-zero
vectors $E$ can be (uniquely, up to reordering) partitioned into disjoint
connected components ${T_{1}\sqcup\dots\sqcup T_{t}=E}$ [Oxl06, Proposition
4.1.2]. Observe that

$\displaystyle\operatorname{span}(E)=\bigoplus_{i\in[t]}\operatorname{span}(T_{i}),$
(17)

and note that $S\subseteq E$ separates $E$ if and only if

$\displaystyle\dim\operatorname{span}\\{v_{1},\dots,v_{n}\\}=\dim\operatorname{span}\\{v_{a}:a\in
S\\}+\dim\operatorname{span}\\{v_{a}:a\in S^{c}\\}$ (18)

if and only if

$\displaystyle\operatorname{span}\\{v_{a}:a\in
S\\}\cap\operatorname{span}\\{v_{a}:a\in S^{c}\\}=\\{0\\}$ (19)

(see [Oxl06, Proposition 4.2.1]).

In the remainder of this section, we formally introduce symmetric tensors and
symmetric tensor decompositions, which are natural analogues of tensors and
tensor decompositions. For a positive integer $m\geq 2$ and a vector space
$\mathcal{W}$ over a field $\mathbb{F}$ with $\mathrm{Char}(\mathbb{F})>m$ or
$\mathrm{Char}(\mathbb{F})=0$, we say that a tensor $v\in\mathcal{W}^{\otimes
m}$ is symmetric if it is invariant under permutations of the subsystems. The
Waring rank of a symmetric tensor $v$, denoted by $\mathrm{WaringRank}(v)$, is
the minimum number $n$ for which $v$ is equal to a linear combination of $n$
symmetric product tensors. A decomposition of $v$ into a linear combination of
$\mathrm{WaringRank}(v)$ symmetric product tensors is called a Waring rank
decomposition of $v$. A decomposition of $v$ into a linear combination of
symmetric product tensors (not necessarily of minimum number) is known simply
as a symmetric decomposition of $v$.

A symmetric decomposition of $v$

$\displaystyle v=\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$ (20)

is said to be the unique Waring rank decomposition of $v$ if for any non-
negative integer $r\leq n$, multiset of non-zero vectors
$\\{u_{a}:a\in[r]\\}\subseteq\mathcal{W}\setminus\\{0\\}$, and non-zero
scalars $\\{\beta_{a}:a\in[r]\\}\subseteq\mathbb{F}^{\times}$ for which

$\displaystyle v=\sum_{a\in[r]}\beta_{a}u_{a}^{\otimes m},$ (21)

it holds that $r=n$ and

$\displaystyle\\{\alpha_{a}v_{a}^{\otimes
m}:a\in[n]\\}=\\{\beta_{a}u_{a}^{\otimes m}:a\in[n]\\}.$ (22)

More generally, for a positive integer $\tilde{n}\geq n$, we say that the
symmetric decomposition (20) is the unique symmetric decomposition of $v$ into
at most $\tilde{n}$ terms if for any $r\leq\tilde{n}$ and symmetric
decomposition (21), either

$\displaystyle{\operatorname{k-rank}(u_{a}:a\in[r])=1},$ (23)

or $r=n$ and

$\displaystyle\\{\alpha_{a}v_{a}^{\otimes
m}:a\in[n]\\}=\\{\beta_{a}u_{a}^{\otimes m}:a\in[n]\\}.$ (24)

Note that (20) is the unique Waring rank decomposition of $v$ if and only if
it is the unique symmetric decomposition of $v$ into at most $n$ terms. We
refer to results that certify uniqueness of a symmetric decomposition into at
most $\tilde{n}>n$ terms as uniqueness results for non-Waring rank
decompositions. We present such results in Section 9.

Our assumption that $\mathrm{Char}(\mathbb{F})>m$ or
$\mathrm{Char}(\mathbb{F})=0$ in the symmetric case ensures that the symmetric
subspace is isomorphic to the space of homogeneous polynomials over
$\mathbb{F}$ of degree $m$ in $\dim(\mathcal{W})$ variables, and that every
symmetric tensor has finite Waring rank (see e.g. [IK99, Appendix A] and
[Lan12, Section 2.6.4]).

##  4 Proving the splitting theorem

In this section, we prove Theorem 4. We first observe the following basic
fact.

######  Proposition 5.

Let $n\geq 2$ be an integer, let
$\mathcal{V}=\mathcal{V}_{1}\otimes\mathcal{V}_{2}$ be a vector space over a
field $\mathbb{F}$, and let

$\displaystyle E=\\{x_{a}\otimes
y_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\mathcal{V}_{2}\right)$
(25)

be a multiset of product tensors. If $E$ is connected, then
$\\{x_{a}:a\in[n]\\}$ and $\\{y_{a}:a\in[n]\\}$ are both connected.

###### Proof.

Suppose toward contradiction that $E$ is connected and $\\{x_{a}:a\in[n]\\}$
splits, i.e.

$\displaystyle\dim\operatorname{span}\\{x_{a}:a\in[n]\\}=\operatorname{span}\\{x_{a}:a\in
S\\}\oplus\operatorname{span}\\{x_{a}:a\in S^{c}\\}$ (26)

for some non-empty proper subset $S\subseteq[n]$. Since $E$ is connected,
there exists a non-zero vector

$\displaystyle v\in\operatorname{span}\\{x_{a}\otimes y_{a}:a\in
S\\}\cap\operatorname{span}\\{x_{a}\otimes y_{a}:a\in S^{c}\\}.$ (27)

Let $f\in\mathcal{V}_{2}^{*}$ be any linear functional such that
$(\mathds{1}\otimes f)v\neq 0.$ Then $(\mathds{1}\otimes f)v$ is a non-zero
element of

$\displaystyle\operatorname{span}\\{x_{a}:a\in
S\\}\cap\operatorname{span}\\{x_{a}:a\in S^{c}\\},$ (28)

contradicting (26). The result is obviously symmetric under permutation of
$\mathcal{V}_{1}$ and $\mathcal{V}_{2}$. ∎

It is not difficult to see that Theorem 4 follows directly from the $m=2$ case
of Theorem 4, Proposition 5, and an inductive argument (we omit this proof).
We therefore need only prove the $m=2$ case of Theorem 4, which we now
explicitly state for clarity.

######  Theorem 6 ($m=2$ case of Theorem 4).

Let $n\geq 2$ be an integer, let
$\mathcal{V}=\mathcal{V}_{1}\otimes\mathcal{V}_{2}$ be a vector space over a
field $\mathbb{F}$, and let

$\displaystyle E=\\{x_{a}\otimes
y_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\mathcal{V}_{2}\right)$
(29)

be a multiset of product tensors. Let

$\displaystyle d_{1}=\dim\operatorname{span}\\{x_{a}:a\in[n]\\}$ (30)

and

$\displaystyle d_{2}=\dim\operatorname{span}\\{y_{a}:a\in[n]\\}.$ (31)

If $E$ is connected, then $\dim\operatorname{span}(E)\geq d_{1}+d_{2}-1$.

To prove Theorem 6, we require a matroid-theoretic construction called the ear
decomposition of a connected matroid (see, e.g. [CH96]). For completeness, we
review the construction here. We refer the reader to [Oxl06] for the basic
matroid-theoretic arguments used in this proof.

######  Lemma 7 (Ear decomposition).

Let $n\geq 2$ be an integer, let $\mathcal{V}$ be a vector space over a field
$\mathbb{F}$, and let
$E=\\{v_{1},\dots,v_{n}\\}\subseteq\mathcal{V}\setminus\\{0\\}$ be a multiset
of non-zero vectors. If $E$ is connected, then there exists a collection of
circuits $C_{1},\dots,C_{t}\subseteq E$ such that

$\displaystyle E=C_{1}\cup C_{2}\cup\dots\cup C_{t},$ (32)

and for each $p\in[t]$, the multisets $C_{p}$ and $E_{p}:=C_{1}\cup\dots\cup
C_{p}$ satisfy the following two properties:

  1. 1.

$C_{p}\cap E_{p-1}\neq\\{\\}$

  2. 2.

$\dim\operatorname{span}(E_{p})-\dim\operatorname{span}(E_{p-1})=|E_{p}\setminus
E_{p-1}|-1$

###### Proof.

Let $C_{1}\subseteq E$ be an arbitrary circuit, which must exist because $E$
is non-empty and connected, and assume by induction that $C_{1},\dots,C_{p}$
have already been constructed to satisfy properties 1 and 2. Let $B\subseteq
E_{p}$ be a basis for $\operatorname{span}(E_{p})$, and choose vectors
$u_{1},u_{2},\dots\in E\setminus E_{p}$ sequentially such that at each step
$q$, $\\{u_{1},\dots,u_{q}\\}$ is linearly independent. Terminate when

$\displaystyle\dim\operatorname{span}\\{B\cup\\{u_{1},\dots,u_{q}\\}\\}=\lvert
B\rvert+q-1.$ (33)

Note that this process must terminate, otherwise $E$ would split. Fixing $q$
to be the terminating step of this process, note that if $u_{q}$ is removed
from $B\cup\\{u_{1},\dots,u_{q}\\}$, then the resulting multiset is linearly
independent, so $B\cup\\{u_{1},\dots,u_{q}\\}$ contains a unique circuit
containing $u_{q}$. Call this circuit $C_{p+1}$, and observe that properties 1
and 2 hold for ${E_{p+1}:=C_{1}\cup\dots\cup C_{p+1}}$. The lemma follows by
repeating this process until the circuits cover $E$. ∎

Now we prove Theorem 6.

###### Proof of Theorem 6.

For a subset $S\subseteq[n]$, let

$\displaystyle d^{S}$ $\displaystyle=\dim\operatorname{span}\\{x_{a}\otimes
y_{a}:a\in S\\},$ (34) $\displaystyle d_{1}^{S}$
$\displaystyle=\dim\operatorname{span}\\{x_{a}:a\in S\\},$ (35) $\displaystyle
d_{2}^{S}$ $\displaystyle=\dim\operatorname{span}\\{y_{a}:a\in S\\}.$ (36)

In a slight change of notation from Lemma 7, let
$C_{1},\dots,C_{t}\subseteq[n]$ be the index sets corresponding to an ear
decomposition of $E$, and let $E_{p}=C_{1}\cup\dots\cup C_{p}\subseteq[n]$ for
each $p\in[t]$. The theorem follows from the following two claims

######  Claim 8.

$d^{E_{1}}\geq d^{E_{1}}_{1}+d^{E_{1}}_{2}-1.$

######  Claim 9.

For each $p\in\\{2,\dots,t\\}$,

$\displaystyle\lvert E_{p}\setminus E_{p-1}\rvert-1\geq
d_{1}^{E_{p}}-d_{1}^{E_{p-1}}+d_{2}^{E_{p}}-d_{2}^{E_{p-1}}.$ (37)

Before proving these claims, let us first use them to complete the proof. Note
that

$\displaystyle d^{E_{2}}$ $\displaystyle=d^{E_{1}}+\lvert E_{2}\setminus
E_{1}\rvert-1$ (38) $\displaystyle\geq d^{E_{1}}_{1}+d^{E_{1}}_{2}-1+\lvert
E_{2}\setminus E_{1}\rvert-1$ (39) $\displaystyle\geq
d^{E_{2}}_{1}+d^{E_{2}}_{2}-1.$ (40)

The first line is a property of the ear decomposition, the second line follows
from Claim 8, and the third line follows from Claim 9. So Claim 8 holds with
$E_{1}$ replaced with $E_{2}$. Repeating this process inductively gives
$d^{[n]}\geq d^{[n]}_{1}+d^{[n]}_{2}-1$, which is what we wanted to prove.
This completes the proof, modulo proving the claims.

###### Proof of Claim 8.

By permuting $[n]$, we may assume that $C_{1}=[q]$ for some $q\in[n]$, and
that $\\{x_{a}:a\in[d_{1}^{[q]}]\\}$ is a basis for
$\operatorname{span}\\{x_{a}:a\in[q]\\}$. Let $s=d_{1}^{[q]}$.

Suppose that there exists $b\in[s]$ such that
$y_{b}\notin\operatorname{span}\\{y_{a}:a\in[q]\setminus[s]\\}$. Let
$f\in\mathcal{V}_{1}^{*}$, $g\in\mathcal{V}_{2}^{*}$ be linear functionals
such that $f(x_{b})=g(y_{b})=1$, $f(x_{a})=0$ for all
$a\in[s]\setminus\\{b\\}$, and $g(y_{a})=0$ for all $a\in[q]\setminus[s]$. So

$\displaystyle(f\otimes g)(x_{a}\otimes y_{a})=\begin{cases}1,&a=b\\\ 0,&a\neq
b\end{cases}.$ (41)

It follows that $x_{b}\otimes y_{b}\notin\operatorname{span}\\{x_{a}\otimes
y_{a}:a\in[q]\setminus\\{b\\}\\}$, contradicting the fact that $C_{1}$ indexes
a circuit. So
$\\{y_{a}:a\in[s]\\}\subseteq\operatorname{span}\\{y_{a}:a\in[q]\setminus[s]\\}$,
which implies

$\displaystyle d_{2}^{C_{1}}$ $\displaystyle\leq q-s$ (42)
$\displaystyle=d^{C_{1}}+1-d_{1}^{C_{1}},$ (43)

completing the proof. ∎

Now we prove Claim 9.

###### Proof of Claim 9.

Let $B\subseteq E_{p-1}$ be such that $\\{x_{a}:a\in B\\}$ is a basis for
${\operatorname{span}\\{x_{a}:a\in E_{p-1}\\}}$. By permuting $[n]$, we may
assume that $E_{p}\setminus E_{p-1}=[q]$ for some $q\in[n]$, and that
${B\cup\\{x_{a}:a\in[s]\\}}$ is a basis for $\operatorname{span}\\{x_{a}:a\in
E_{p}\\}$, where $s=d^{E_{p}}-d^{E_{p-1}}$. If there exists $b\in[s]$ for
which $y_{b}\notin\operatorname{span}\\{y_{a}:a\in[q]\setminus[s]\\}$, then,
as in the proof of Claim 8,

$\displaystyle x_{b}\otimes y_{b}\notin\operatorname{span}\\{x_{a}\otimes
y_{a}:a\in E_{p}\setminus\\{b\\}\\}.$ (44)

But this contradicts connectedness of $E$, a contradiction. It follows that
$d_{2}^{E_{p}\setminus E_{p-1}}\leq q-s$, so

$\displaystyle d_{2}^{E_{p}}-d_{2}^{E_{p-1}}$ $\displaystyle\leq
d_{2}^{C_{p}}-d_{2}^{C_{p}\cap E_{p-1}}$ (45) $\displaystyle\leq
d_{2}^{C_{p}\setminus(C_{p}\cap E_{p-1})}-1$ (46)
$\displaystyle=d_{2}^{E_{p}\setminus E_{p-1}}-1$ (47) $\displaystyle\leq
q-s-1$ (48) $\displaystyle=\lvert E_{p}\setminus
E_{p-1}\rvert-(d_{1}^{E_{p}}-d_{1}^{E_{p-1}})-1.$ (49)

The first line is easy to verify (in matroid-theoretic terms, this is
submodularity of the rank function). The second line follows from the fact
that $\\{y_{a}:a\in C_{p}\\}$ is connected. The third line is obvious, the
fourth line we proved above, and the fifth line follows from our definitions.
This completes the proof. ∎

The proofs of Claims 8 and 9 complete the proof of the theorem. ∎

##  5 Using our splitting theorem to generalize Kruskal’s theorem

In this section we use our splitting theorem (Theorem 4) to prove our
generalization of Kruskal’s theorem (Theorem 2). We then introduce a reshaped
version of Theorem 2, which has many more degrees of freedom than the standard
reshaping of Kruskal’s theorem.

To prove Theorem 2, we first observe the following useful corollary to our
splitting theorem.

######  Corollary 10.

Let $n\geq 2$ and $m\geq 2$ be integers, let
$\mathcal{V}=\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}$ be a vector
space over a field $\mathbb{F}$, let

$\displaystyle
E=\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
(50)

be a multiset of product tensors, and for each $j\in[m]$, let

$\displaystyle d_{j}=\dim\operatorname{span}\\{x_{a,j}:a\in[n]\\}.$ (51)

If $n\leq\sum_{j=1}^{m}(d_{j}-1)+1$, then $E$ splits.

###### Proof.

If $E$ is linearly independent, then it obviously splits. Otherwise,

$\displaystyle{\dim\operatorname{span}(E)\leq n-1},$ (52)

and the result follows immediately from our splitting theorem. ∎

Now we use this corollary to prove our generalization of Kruskal’s theorem.

###### Proof of Theorem 2.

Let $x_{a}=x_{a,1}\otimes\dots\otimes x_{a,m}$ for each $a\in[n]$, and suppose
that ${\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}}$ for some non-negative integer
$r\leq n$ and multiset of product tensors
$\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$.
For notational convenience, for each $a\in[r]$ let $x_{n+a}=-y_{a}$, so that
$\sum_{a\in[n+r]}x_{a}=0$. Let $T_{1}\sqcup\dots\sqcup T_{t}=[n+r]$ be the
index sets of the connected components of $\\{x_{a}:a\in[n+r]\\}$. Since
$\sum_{a\in[n+r]}x_{a}=0$, it follows that $\sum_{a\in T_{p}}x_{a}=0$ for all
$p\in[t]$, so $\lvert T_{p}\rvert\geq 2$ for all $p\in[t]$.

For each $p\in[t]$, if

$\displaystyle\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\geq\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert},$
(53)

then it must hold that

$\displaystyle\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}=\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}=1,$
(54)

otherwise $\\{x_{a}:a\in T_{p}\\}$ would split by Corollary 10, a
contradiction. Since $r\leq n$ and the inequality (53) can never be strict, it
follows that $r=n$ and (54) holds for all $p\in[t]$. This completes the proof.
∎

For $m\geq 4$, both Kruskal’s theorem and our Theorem 2 can be “reshaped” by
regarding multiple subsystems as a single subsystem, to give potentially
stronger uniqueness criteria. It is worth noting that the reshaped version of
Theorem 2 has quite a different flavour from the reshaped version of Kruskal’s
theorem; in particular, there are many more degrees of freedom to choose from.
We omit the proof of the following reshaped version of Theorem 2, because it
is similar to the proof of Theorem 2.

######  Theorem 11 (Reshaped generalization of Kruskal’s theorem).

Let $n\geq 2$ and $m\geq 3$ be integers, let
$\mathcal{V}=\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}$ be a vector
space over a field $\mathbb{F}$, and let

$\displaystyle\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
(55)

be a multiset of product tensors. For each $S\subseteq[n]$ and
$J\subseteq[m]$, let

$\displaystyle d_{J}^{S}=\dim\operatorname{span}\Big{\\{}\bigotimes_{j\in
J}x_{a,j}:a\in S\Big{\\}}.$ (56)

If for every subset $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$ there
exists a partition $J_{1}\sqcup\dots\sqcup J_{t}=[m]$ (which may depend on
$S$) such that $2\lvert S\rvert\leq\sum_{i\in[t]}(d_{J_{i}}^{S}-1)+1$, then
$\sum_{a\in[n]}x_{a}$ constitutes a unique tensor rank decomposition.

It is instructive to compare Theorem 11 to the standard reshaping of Kruskal’s
theorem:

######  Theorem 12 (Reshaped Kruskal’s theorem).

Let $n\geq 2$ and $m\geq 3$ be integers, let
${\mathcal{V}=\mathcal{V}_{1}\otimes\cdots\otimes\mathcal{V}_{m}}$ be a vector
space over a field $\mathbb{F}$, and let

$\displaystyle\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
(57)

be a multiset of product tensors. For each $J\subseteq[m]$, let

$\displaystyle k_{J}=\operatorname{k-rank}(\bigotimes_{j\in
J}x_{a,j}:a\in[n]).$ (58)

If there exists a partition of $[m]$ into three disjoint subsets $J\sqcup
K\sqcup L=[m]$ such that ${2n\leq k_{J}+k_{K}+k_{L}-2},$ then
$\sum_{a\in[n]}x_{a}$ constitutes a unique tensor rank decomposition.

Theorem 12 clearly follows from our Theorem 11. In Theorem 12, one could of
course consider more general partitions of $[m]$ into more than three subsets,
but since the k-rank satisfies $k_{J\cup K}\geq\min\\{n,k_{J}+k_{K}-1\\}$ for
any disjoint subsets $J,K\subseteq[m]$ (See Lemma 1 in [SB00]), it suffices to
consider tripartitions $J\sqcup K\sqcup L=[m]$. In contrast, it is not clear
that one can restrict to tripartitions in Theorem 11. There is another major
difference between these two theorems: In Theorem 12, one chooses a single
partition of $[m]$, whereas in Theorem 11, one is free to choose a different
partition of $[m]$ for every $S$.

We remark that many other statements in this work (for example, the splitting
theorem itself) can be reshaped similarly to Theorem 11. We do not explicitly
state these reshapings.

##  6 The inequality appearing in our splitting theorem cannot be weakened

In this section, we find a connected multiset of product tensors
$E=\\{x_{a}:a\in[n]\\}$ that satisfies
${\dim\operatorname{span}(E)=\sum_{j=1}^{m}(d_{j}-1)+1}$. In fact, we prove
that this multiset of product tensors forms a circuit, which is stronger than
being connected. This proves that the bound in Corollary 21, and the
inequality $\dim\operatorname{span}(E)\leq\sum_{j=1}^{m}(d_{j}-1)$ appearing
in Theorem 4, cannot be weakened. The example we use is Derksen’s [Der13],
which he used to prove that the inequality appearing in Kruskal’s theorem
cannot be weakened.

######  Fact 13.

For any field $\mathbb{F}$ with $\mathrm{Char}(\mathbb{F})=0$, and positive
integers $d_{1},\dots,d_{m}$ with ${n-1=\sum_{j=1}^{m}(d_{j}-1)+1}$, there
exist vector spaces $\mathcal{V}_{1},\dots,\mathcal{V}_{m}$ over $\mathbb{F}$
and a multiset of product tensors
$\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\cdots:\mathcal{V}_{m}\right)$
that forms a circuit, and satisfies

$\displaystyle\dim\operatorname{span}\\{x_{a,j}:a\in[n]\\}\geq d_{j}$ (59)

for all $a\in[n]$.

We note that if $d_{1}=\dots=d_{m}$, then the multiset of product tensors
$\\{x_{a}:a\in[n]\\}$ can be taken to be symmetric in the sense introduced in
Section 3 (this is obvious from Derksen’s construction [Der13]). As a result,
our splitting theorem is also sharp for symmetric product tensors. We use this
fact in Sections 8 and 9 to prove optimality of our results on symmetric
decompositions. We remark that the assumption $\mathrm{Char}(\mathbb{F})=0$
can be weakened, see [Der13].

###### Proof of Fact 13.

By Theorem 2 of [Der13], there exist vector spaces
$\mathcal{V}_{1},\dots,\mathcal{V}_{m}$ over $\mathbb{F}$, a positive integer
$\tilde{n}\leq n$, and product tensors
$\\{x_{a}:a\in[\tilde{n}]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\cdots:\mathcal{V}_{m}\right)$
with k-ranks $d_{j}=\operatorname{k-rank}(x_{1,j},\dots,x_{\tilde{n},j})$ such
that ${\sum_{a\in[\tilde{n}]}x_{a}=0}$. If $\tilde{n}<n$, then
${\tilde{n}\leq\sum_{j=1}^{m}(d_{j}-1)+1}$, which implies
$\\{x_{a}:a\in[\tilde{n}]\\}$ is linearly independent by Corollary 18 (or
Proposition 3.1 in [HK15]). But this contradicts
$\sum_{a\in[\tilde{n}]}x_{a}=0$, so $\tilde{n}=n$. The equality
$n=\sum_{j=1}^{m}(d_{j}-1)+2$ implies that $d_{j}\leq n-1$ for all $j\in[m]$.
It follows that for any subset $S\subseteq[n]$ of size $\lvert S\rvert=n-1$,
it holds that ${\operatorname{k-rank}(x_{a,j}:a\in S)\geq d_{j}}$. Since
$n-1=\sum_{j=1}^{m}(d_{j}-1)+1$, then by Corollary 18, ${\\{x_{a}:a\in S\\}}$
is linearly independent. It follows that $\\{x_{a}:a\in[n]\\}$ is a circuit. ∎

##  7 Interpolating between our generalization of Kruskal’s theorem and an
offshoot of our splitting theorem

For the entirety of this section, we fix non-negative integers $n\geq 2$ and
$m\geq 2$, a vector space
$\mathcal{V}=\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}$ over a field
$\mathbb{F}$, and a multiset of product tensors
${\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)}$.
For each subset $S\subseteq[n]$ and index $j\in[m]$, we define

$\displaystyle d_{j}^{S}=\dim\operatorname{span}\\{x_{a,j}:a\in S\\},$ (60)

and use the shorthand $d_{j}=d_{j}^{[n]}$ for all $j\in[m]$.

As a consequence of our splitting theorem, if
$n\leq\sum_{j=1}^{m}(d_{j}-1)+1$, then ${\\{x_{a}:a\in[n]\\}}$ splits
(Corollary 10). Our generalization of Kruskal’s theorem states that if
$2\lvert S\rvert\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1$ for every subset
$S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$, then $\sum_{a\in[n]}x_{a}$
constitutes a unique tensor rank decomposition. It is natural to ask what
happens when other, similar inequalities hold. In particular, suppose that

$\displaystyle{\lvert S\rvert+\mathcal{R}(\lvert
S\rvert)\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1}$ (61)

for all $S\subseteq[n]$ with $s+1\leq\lvert S\rvert\leq n$, for some
$s\in[n-1]$ and function $\mathcal{R}:[n]\setminus[s]\rightarrow\mathbb{Z}$.
What can be said about the tensors
$v\in\operatorname{span}\\{x_{a}:a\in[n]\\}$?

In this section, we use our splitting theorem to answer this question for
choices of $s$ and $\mathcal{R}$ that produce useful results on tensor
decompositions. In Section 7.1 we prove uniqueness results for low-rank
tensors in $\operatorname{span}\\{x_{a}:a\in[n]\\}$. These results can be
viewed as an interpolation between the two extreme choices of parameters in
Corollary 10 (where $s=n-1$ and $\mathcal{R}(n)=n$) and our generalization of
Kruskal’s theorem (where $s=1$ and $\mathcal{R}=\mathds{1}$). We use this
interpolation to extend several recent results in [HK15, BBCG18, Bal20]. In
Section 7.2 we prove uniqueness results for non-rank decompositions of
$\sum_{a\in[n]}x_{a}$ (i.e., decompositions into a non-minimal number of
product tensors), which appear to be the first known results of this kind.

We will make use of the following terminology.

######  Definition 14.

For positive integers $n$ and $r$, multisets of product tensors

$\displaystyle\\{x_{a}:a\in[n]\\},\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right),$
(62)

and non-zero scalars

$\displaystyle\\{\alpha_{a}:a\in[n]\\},\\{\beta_{a}:a\in[r]\\}\subseteq\mathbb{F}^{\times},$
(63)

for which

$\displaystyle\sum_{a\in[n]}\alpha_{a}x_{a}=\sum_{a\in[r]}\beta_{a}y_{a},$
(64)

we say that the (ordered) pair of decompositions
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$ has an
$(s,l)$-subpartition for some positive integers $s$ and $l$ if there exist
pairwise disjoint subsets $Q_{1},\dots,Q_{l}\subseteq[n]$ and pairwise
disjoint subsets ${R_{1},\dots,R_{l}\subseteq[r]}$ for which

$\displaystyle\max\\{1,\lvert R_{p}\rvert\\}\leq\lvert Q_{p}\rvert\leq s$ (65)

and $\sum_{a\in Q_{p}}\alpha_{a}x_{a}=\sum_{a\in R_{p}}\beta_{a}y_{a}$ for all
$p\in[l]$. We say that the pair
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$ has an
$(s,l)$-partition if the sets $Q_{1},\dots,Q_{l}\subseteq[n]$ and
$R_{1},\dots,R_{l}\subseteq[r]$ can be chosen to partition $[n]$ and $[r]$,
respectively.

We say that the pair
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$ is reducible if
there exist subsets $Q\subseteq[n]$ and $R\subseteq[r]$ for which $\lvert
Q\rvert>\lvert R\rvert$ and $\sum_{a\in Q}\alpha_{a}x_{a}=\sum_{a\in
R}\beta_{a}y_{a}$. We say that the pair is irreducible if it is not reducible.

(Technically, the linear combinations appearing in the pair
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$ should be
regarded formally, so that they contain the data of the decompositions, and
the linear combinations appearing elsewhere should be regarded as standard
linear combinations in $\mathcal{V}$.)

For brevity, we will often abuse notation and say that
$\sum_{a\in[n]}\alpha_{a}x_{a}=\sum_{a\in[r]}\beta_{a}y_{a}$ has an
$(s,l)$-subpartition (or is reducible) to mean that
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$ has an
$(s,l)$-subpartition (or is reducible). Note that the properties of
$(s,l)$-subpartitions and reducibility are not symmetric with respect to
permutation of the first and second decompositions. Typically, the first
decomposition $\sum_{a\in[n]}\alpha_{a}x_{a}$ will be known, and the second
decomposition $\sum_{a\in[r]}\beta_{a}y_{a}$ will be some unknown
decomposition that we want to control.

An immediate consequence of Corollary 10 is that if
$\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$ for some $r\leq n$, and the
inequality (61) holds for $s=n-1$ and $\mathcal{R}(n)=r$, then this pair of
decompositions has an $(n-1,1)$-subpartition (see Corollary 20 for a slight
extension of this statement). By comparison, our generalization of Kruskal’s
theorem states that if $r\leq n$, and (61) holds for $s=1$ and
$\mathcal{R}=\mathds{1}$, then $r=n$ and this pair of decompositions has a
$(1,n)$-subpartition. In Section 7.1 we prove statements on the existence of
$(s,l)$-subpartitions for $r\leq n$, which interpolate between these two
statements by trading stronger assumptions for stronger notions of uniqueness.
In Section 7.2 we prove a similar family of statements for $r\geq n+1$,
obtaining novel uniqueness results for non-rank decompositions.

We conclude the introduction to this section by making a few notes about our
definitions of $(s,l)$-subpartitions and reducibility. It may seem a bit
strange at first that the inequality $\lvert R_{p}\rvert\leq\lvert
Q_{p}\rvert$ appears in our definition of an $(s,l)$-subpartition. We have
chosen to include this inequality because we typically want to reduce the
number of product tensors that appear a decomposition. Our definition of
reducibility captures a similar idea: If $n\leq r$ and
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$ is reducible,
then these decompositions can easily be combined to produce a decomposition
into fewer than $n$ product tensors. (When $r\leq n$, reducibility of
$(\sum_{a\in[r]}\beta_{a}y_{a},\sum_{a\in[n]}\alpha_{a}x_{a})$ captures a
similar idea.) Assuming irreducibility will allow us to avoid certain
pathological cases. Note that if $\sum_{a\in[n]}\alpha_{a}x_{a}$ is a tensor
rank decomposition, then
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$ is
automatically irreducible.

Note that when $(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[r]}\beta_{a}y_{a})$
is irreducible, the existence of an $(s,l)$-subpartition is equivalent to the
existence of pairwise disjoint subsets $Q_{1},\dots,Q_{l}\subseteq[n]$ and
pairwise disjoint subsets $R_{1},\dots,R_{l}\subseteq[r]$ for which

$\displaystyle 1\leq\lvert R_{p}\rvert=\lvert Q_{p}\rvert\leq s$ (66)

and $\sum_{a\in Q_{p}}\alpha_{a}x_{a}=\sum_{a\in R_{p}}\beta_{a}y_{a}$ for all
$p\in[l]$. When $s=1$, these statements are equivalent even without the
irreducibility assumption.

###  7.1 Low-rank tensors in the span of a set of product tensors

In this subsection, we prove statements about low-rank tensors in
$\operatorname{span}\\{x_{a}:a\in[n]\\}$. Most of our results in this section
are consequences of Theorem 15, which is a somewhat complicated statement on
the existence of $(s,l)$-partitions. For $s=1$, and any
${r\in\\{0,1,\dots,n\\}}$ we obtain a condition on $\\{x_{a}:a\in[n]\\}$ for
which the only rank $\leq r$ tensors in
$\operatorname{span}\\{x_{a}:a\in[n]\\}$ are those that can be written
(uniquely) as a linear combination of $\leq r$ elements of
$\\{x_{a}:a\in[n]\\}$. For $s=1,r=0$ we obtain a sufficient condition for
linear independence of $\\{x_{a}:a\in[n]\\}$. For $s=1,r=1$ we obtain a
sufficient condition for the only product tensors in
$\operatorname{span}\\{x_{a}:a\in[n]\\}$ to be scalar multiples of
$x_{1},\dots,x_{n}$. These generalize Proposition 3.1 and Theorem 3.2 in
[HK15], respectively. The case $s=1,r=n$ reproduces our generalization of
Kruskal’s theorem. For $s=n-1$, we strengthen recent results in [BBCG18,
Bal20] on circuits of product tensors.

Most of the statements in this subsection are consequences of the following
theorem, which is complicated to state, but easy to prove with our splitting
theorem.

######  Theorem 15.

Let $s\in[n-1]$, and $r\in\\{0,1,\dots,n\\}$ be integers. Suppose that for
every subset $S\subseteq[n]$ with $s+1\leq\lvert S\rvert\leq n,$ it holds that

$\displaystyle\min\\{2\lvert S\rvert,\lvert
S\rvert+r\\}\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1.$ (67)

Then for any $v\in\operatorname{span}\\{x_{a}:a\in[n]\\}$ with
$\operatorname{rank}(v)\leq r$, and any decomposition
${v=\sum_{a\in[\tilde{r}]}y_{a}}$ of $v$ into $\tilde{r}\leq r$ product
tensors
$\\{y_{a}:a\in[\tilde{r}]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$,
the following holds: For any subset $S\subseteq[n]$ for which $\lvert
S\rvert\geq s+1$, and non-zero scalars $\\{\alpha_{a}:a\in
S\\}\subseteq\mathbb{F}^{\times}$ for which it holds that

$\displaystyle\sum_{a\in S}\alpha_{a}x_{a}=\sum_{a\in[\tilde{r}]}y_{a}$ (68)

and $(\sum_{a\in[\tilde{r}]}y_{a},\sum_{a\in S}\alpha_{a}x_{a})$ is
irreducible, the pair of decompositions
$(\sum_{a\in[n]}\alpha_{a}x_{a},\sum_{a\in[\tilde{r}]}y_{a})$ has an
$(s,l)$-partition, for $l=\lceil\lvert S\rvert/s\rceil$.

###### Proof.

For each $a\in[\tilde{r}]$, let $x_{n+a}=-y_{a}$, and let
$E=S\cup([n+\tilde{r}]\setminus[n])\subseteq[n+\tilde{r}]$. Let
${T_{1}\sqcup\dots\sqcup T_{t}=E}$ be a partition of $E$ into index sets
corresponding to the connected components of $\\{x_{a}:a\in E\\}$. Since
$(\sum_{a\in[\tilde{r}]}y_{a},\sum_{a\in S}\alpha_{a}x_{a})$ is irreducible,
it must hold that

$\displaystyle\bigl{\lvert}T_{p}\cap
S\bigr{\rvert}\geq\bigl{\lvert}T_{p}\cap(E\setminus S)\bigr{\rvert}$ (69)

for all $p\in[t]$, and hence

$\displaystyle\lvert T_{p}\rvert\leq\min\big{\\{}2\bigl{\lvert}T_{p}\cap
S\bigr{\rvert},\bigl{\lvert}T_{p}\cap S\bigr{\rvert}+r\big{\\}}.$ (70)

If $\lvert T_{p}\cap S\rvert\geq s+1,$ then $\\{x_{a}:a\in T_{p}\\}$ splits by
(67) and Corollary 10, a contradiction. So it must hold that ${\lvert
T_{p}\cap S\rvert\leq s}$ for all $p\in[t]$. It follows that
$t\geq\lceil\lvert S\rvert/s\rceil$ by the pigeonhole principle, and one can
take $Q_{p}=T_{p}\cap S$ and

$\displaystyle R_{p}=\\{a\in[\tilde{r}]:n+a\in T_{p}\cap(E\setminus S)\\}$
(71)

for all $p\in[t]$ to conclude. ∎

####  7.1.1 $s=1$ case of Theorem 15

The $s=1$ case of Theorem 15 gives a sufficient condition for which the only
tensor rank $\leq r$ elements of $\operatorname{span}\\{x_{a}:a\in[n]\\}$ are
those which can be written (uniquely) as a linear combination of $\leq r$
elements of $\operatorname{span}\\{x_{a}:a\in[n]\\}$. In this subsection, we
state this case explicitly, and observe several consequences of this case. In
particular, we observe a lower bound on tensor rank and a sufficient condition
for a set of product tensors to be linearly independent.

######  Corollary 16 ($s=1$ case of Theorem 15).

Let $r\in\\{0,1,\dots,n\\}$ be an integer. Suppose that for every subset
$S\subseteq[n]$ such that $2\leq\lvert S\rvert\leq n$, it holds that

$\displaystyle\lvert S\rvert+\min\\{\lvert
S\rvert,r\\}\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1.$ (72)

Then any non-zero linear combination of more than $r$ elements of
$\\{x_{a}:a\in[n]\\}$ has tensor rank greater than $r$, and every tensor
$v\in\operatorname{span}\\{x_{a}:a\in[n]\\}$ of tensor rank at most $r$ has a
unique tensor rank decomposition into a linear combination of elements of
$\\{x_{a}:a\in[n]\\}$.

Note that a sufficient condition for the inequality (72) to hold is that

$\displaystyle n+r\leq\sum_{j=1}^{m}(k_{j}-1)+1,$ (73)

where $k_{j}=\operatorname{k-rank}(x_{1,j},\dots,x_{n,j})$ for all $j\in[m]$.
This recovers Proposition 3.1 and Theorem 3.2 in [HK15] in the $r=0$ and $r=1$
cases, respectively, and interpolates between Kruskal’s theorem and these
results. For clarity, we will explicitly state the $r=0$ and $r=1$ cases of
Corollary 16 at the end of this subsection.

###### Proof of Corollary 16.

Let $S\subseteq[n]$ be a subset, let $\\{\alpha_{a}:a\in
S\\}\subseteq\mathbb{F}^{\times}$ be a multiset of non-zero scalars, let
$\tilde{r}=\operatorname{rank}[\sum_{a\in S}\alpha_{a}x_{a}]$, and let
$\\{y_{a}:a\in[\tilde{r}]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
be such that $\sum_{a\in S}\alpha_{a}x_{a}=\sum_{a\in[\tilde{r}]}y_{a}$. If
$\tilde{r}\leq r$, then by the $s=1$ case of Theorem 15, this pair of
decompositions has a $(1,\lvert S\rvert)$-partition. It follows that $\lvert
S\rvert=\tilde{r}$. Hence, every linear combination of more than $r$ elements
of $\\{x_{a}:a\in[n]\\}$ has tensor rank greater than $r$.

Let $v\in\operatorname{span}\\{x_{a}:a\in[n]\\}$ have tensor rank
$\tilde{r}\leq r$. Then ${v=\sum_{a\in Q}\alpha_{a}x_{a}}$ for some set
$Q\subseteq[n]$ of size $\lvert Q\rvert=\tilde{r}$ and non-zero scalars
$\\{\alpha_{a}:a\in Q\\}$. It follows from (72) and Theorem 2 that this is the
unique tensor rank decomposition of $v$. ∎

Corollary 16 immediately implies the following lower bound on
$\operatorname{rank}[\sum_{a\in[n]}x_{a}]$.

######  Corollary 17.

If for every subset $S\subseteq[n]$ for which $2\leq\lvert S\rvert\leq n,$ it
holds that

$\displaystyle\lvert S\rvert+\min\\{\lvert
S\rvert,r\\}\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1,$ (74)

then $\operatorname{rank}[\sum_{a\in[n]}x_{a}]\geq r+1$.

In particular, Corollary 17 implies that

$\displaystyle\operatorname{rank}\bigg{[}\sum_{a\in[n]}x_{a}\bigg{]}\geq\min\bigg{\\{}n,\sum_{j=1}^{m}(k_{j}-1)+2-n\bigg{\\}}.$
(75)

In Section 8 we prove that when the Kruskal ranks are sufficiently balanced,
two of the k-ranks $k_{i},k_{j}$ appearing in the bound (75) can be replaced
with standard ranks $d_{i},d_{j}$ (Theorem 28). Our Theorem 28 is independent
of the bound in Corollary 17 (see Example 29).

We close this subsection by stating the $r=0$ and $r=1$ cases of Corollary 16,
which generalize Proposition 3.1 and Theorem 3.2 in [HK15], respectively. We
remark that the $m=2$ subcase of Corollary 18 was proven by Pierpaola
Santarsiero in unpublished work, using a different proof technique.

######  Corollary 18 ($s=1$, $r=0$ case of Theorem 15).

If for every subset $S\subseteq[n]$ for which $2\leq\lvert S\rvert\leq n,$ it
holds that

$\displaystyle\lvert S\rvert\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1,$ (76)

then $\\{x_{a}:a\in[n]\\}$ is linearly independent.

######  Corollary 19 ($s=1$, $r=1$ case of Theorem 15).

If for every subset $S\subseteq[n]$ for which $2\leq\lvert S\rvert\leq n,$ it
holds that

$\displaystyle\lvert S\rvert\leq\sum_{j=1}^{m}(d_{j}^{S}-1),$ (77)

then

$\displaystyle\operatorname{span}\\{x_{a}:a\in[n]\\}\cap\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)=\mathbb{C}^{\times}x_{1}\sqcup\dots\sqcup\mathbb{C}^{\times}x_{n}.$
(78)

####  7.1.2 $s=n-1$ case of Theorem 15

In this subsection we state a slight adaptation of the $s=n-1$ case of Theorem
15, which gives sufficient conditions for a pair of decompositions to have an
$(n-1,1)$-subpartition. After stating this case, we observe that the subcase
$r=1$ improves recent results in [BBCG18, Bal20] concerning circuits of
product tensors. We then remark on applications of this special case in
quantum information theory.

######  Corollary 20 ($s=n-1$ case of Theorem 15).

Let $r\in\\{0,1,\dots,n\\}$ be an integer. If
${n+r\leq\sum_{j=1}^{m}(d_{j}-1)+1}$, then for any non-negative integer
$\tilde{r}\leq r$ and multiset of product tensors
$\\{y_{a}:a\in[\tilde{r}]\\}$ for which
$\sum_{a\in[n]}x_{a}=\sum_{a\in[\tilde{r}]}y_{a}$, the pair of decompositions
$(\sum_{a\in[n]}x_{a},\sum_{a\in[\tilde{r}]}y_{a})$ has an
$(n-1,1)$-subpartition.

Moreover, if ${n+r\leq\sum_{j=1}^{m}(d_{j}-1)+1}$,
$\tilde{r}=\operatorname{rank}[\sum_{a\in[n]}x_{a}]$, and
$1\leq\tilde{r}\leq\min\\{r,n-1\\}$, then there exists a subset
$S\subseteq[n]$ with $\tilde{r}\leq\lvert S\rvert\leq n-1$ for which

$\displaystyle\operatorname{rank}\bigg{[}\sum_{a\in
S}x_{a}\bigg{]}<\tilde{r}.$ (79)

###### Proof.

The statement of the first paragraph is slightly different from the $s=n-1$
case of Theorem 15, and it follows easily from Corollary 10. To prove the
statement of the second paragraph, let
$\\{z_{a}:a\in[\tilde{r}]\\}\in\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
be any multiset of product tensors for which
$\sum_{a\in[n]}x_{a}=\sum_{a\in[\tilde{r}]}z_{a}$, and let $Q\subseteq[n]$,
$R\subseteq[\tilde{r}]$ be subsets for which

$\displaystyle\max\\{\lvert R\rvert,1\\}\leq\lvert Q\rvert\leq n-1$ (80)

and $\sum_{a\in Q}x_{a}=\sum_{a\in R}z_{a}$. If $\lvert R\rvert<\lvert
Q\rvert$ and $\lvert Q\rvert\geq\tilde{r}$, then we can take $S=Q$. If $\lvert
R\rvert<\lvert Q\rvert$ and $\lvert Q\rvert\leq\tilde{r}-1$, then we can take
$S\subseteq[n]$ to be any subset for which $S\supseteq Q$ and $\lvert
S\rvert=\tilde{r}$. It remains to consider the case $\lvert R\rvert=\lvert
Q\rvert$. In this case, it must hold that $\bigl{\lvert}[\tilde{r}]\setminus
R\bigr{\rvert}<\bigl{\lvert}[n]\setminus Q\bigr{\rvert},$ so we can find $S$
using the same arguments as in the case $\lvert R\rvert<\lvert Q\rvert$. ∎

A special case of the $r=1$ case of Corollary 20 gives an upper bound of $n-2$
on the number of subsystems $j\in[m]$ for which a circuit of product tensors
can have $d_{j}>1$. This bound improves those obtained in [Bal20, Theorem 1.1]
and [BBCG18, Lemma 4.5], and is sharp (see Section 6).

######  Corollary 21.

If $\\{{x_{a}}:a\in[n]\\}$ forms a circuit, then ${d_{j}>1}$ for at most $n-2$
indices $j\in[m]$.

###### Proof.

This follows immediately from Corollary 10, since circuits are connected.
Alternatively, this follows from the second paragraph in the statement of
Corollary 20, since for any circuit it holds that $\sum_{a\in S}x_{a}\neq 0$
for all $S\subseteq[n]$ with $1\leq\lvert S\rvert\leq n-1$. ∎

As an immediate consequence of Corollary 21, a sum of two product tensors is
again a product tensor if and only if $d_{j}>1$ for at most a single subsystem
index $j\in[m]$ (see Corollary 15 in [Lov20]). This statement is well-known.
In particular, it was used in [Wes67, Joh11] to characterize the invertible
linear operators that preserve the set of product tensors. In [Lov21, Lov20]
the first author used this statement to study decomposable correlation
matrices, and observed that it directly provides an elementary proof of a
recent result in quantum information theory [BLM17] (see Corollary 16 in
[Lov20]).

###  7.2 Uniqueness results for non-rank decompositions

In this subsection we prove uniqueness results for decompositions of
$\sum_{a\in[n]}x_{a}$ into ${r\geq n+1}$ product tensors. Namely, we provide
conditions on $\\{x_{a}:a\in[n]\\}$ for which whenever
$\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$ for some multiset of product tensors
$\\{y_{a}:a\in[r]\\}$, this pair of decompositions has an
$(s,l)$-subpartition. In particular, for $s=1$ we obtain sufficient conditions
for the existence of subsets $Q\subseteq[n]$, $R\subseteq[r]$ of size $\lvert
Q\rvert=\lvert R\rvert=l$ for which $\\{x_{a}:a\in Q\\}=\\{y_{a}:a\in R\\}$.
We refer the reader also to Section 9, in which we prove uniqueness results on
non-Waring rank decompositions of symmetric tensors, and identify applications
of our non-rank uniqueness results.

In Theorem 22 we give sufficient conditions for which whenever
$(\sum_{a\in[n]}x_{a},\sum_{a\in[r]}y_{a})$ is irreducible, it has an
$(s,l)$-subpartition. We then observe that for $s=1$ we can drop the
irreducibility assumption and obtain the result described in the previous
paragraph. We then prove a modified version of Theorem 22, which drops the
irreducibility assumption for arbitrary $s\in[n-1]$. At the end of this
subsection, we review these statements in the $s=n-1$ case.

######  Theorem 22.

Let $n\geq 2$, $q\in[n-1]$, $s\in[q]$, and $r$ be positive integers for which

$\displaystyle n+1\leq r\leq n+\Bigl{\lceil}\frac{n-q}{s}\Bigr{\rceil},$ (81)

and let $l=\lfloor q/s\rfloor$. If for every subset $S\subseteq[n]$ for which
$s+1\leq\lvert S\rvert\leq n,$ it holds that

$\displaystyle 2\lvert
S\rvert+\max\left\\{0,(r-n)-\biggl{\lceil}\frac{n-q+s}{\lvert
S\rvert}\biggr{\rceil}+1\right\\}\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1,$ (82)

then for any multiset of product tensors
$\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
for which ${\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}}$ and
$(\sum_{a\in[n]}x_{a},\sum_{a\in[r]}y_{a})$ is irreducible, this pair of
decompositions has an $(s,l)$-subpartition.

One may be concerned about whether the complicated collection of inequalities
(82) can ever be satisfied. The answer is yes, simply because the righthand
side can depend on $m$, whereas the lefthand side does not. So for $m$ large
enough, one can always find $\\{x_{a}:a\in[n]\\}$ that satisfies these
inequalities. In fact, they can even be satisfied non-trivially for $m=3$, as
we observe in Example 26.

###### Proof of Theorem 22.

For each $a\in[r]$, let $x_{n+a}=-y_{a}$, and let $T_{1}\sqcup\dots\sqcup
T_{t}=[n+r]$ be the index sets of the decomposition of $\\{x_{a}:a\in[n+r]\\}$
into connected components. Note that for each $p\in[t]$, it must hold that

$\displaystyle\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}\geq\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert},$
(83)

otherwise we would contradict irreducibility. For each $p\in[t]$, if

$\displaystyle\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}=\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert},$
(84)

then $\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\leq s$, otherwise $\\{x_{a}:a\in
T_{p}\\}$ would split by (82) and Corollary 10. Assume without loss of
generality that

$\displaystyle\bigl{\lvert}T_{1}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{1}\cap[n+r]\setminus[n]\bigr{\rvert}$
$\displaystyle\geq\bigl{\lvert}T_{2}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{2}\cap[n+r]\setminus[n]\bigr{\rvert}$
(85) $\displaystyle\;\;\vdots$ (86)
$\displaystyle\geq\bigl{\lvert}T_{{t}}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{{t}}\cap[n+r]\setminus[n]\bigr{\rvert}.$
(87)

If

$\displaystyle\bigl{\lvert}T_{1}\cap[n]\bigr{\rvert}=\bigl{\lvert}T_{1}\cap[n+r]\setminus[n]\bigr{\rvert},$
(88)

then let $\tilde{l}\in[t]$ be the largest integer for which

$\displaystyle\bigl{\lvert}T_{\tilde{l}}\cap[n]\bigr{\rvert}=\bigl{\lvert}T_{\tilde{l}}\cap[n+r]\setminus[n]\bigr{\rvert}.$
(89)

Otherwise, let $\tilde{l}=0$. Then for all $p\in[t]\setminus[\tilde{l}]$ it
holds that

$\displaystyle\lvert T_{p}\cap[n]\rvert<\lvert
T_{p}\cap[n+r]\setminus[n]\rvert$ (90)

(recall that we define $[0]=\\{\\}$). To complete the proof, we will show that
$\tilde{l}\geq l$, for then we can take $Q_{p}=T_{p}\cap[n]$ and
$R_{p}=T_{p}\cap[n+r]\setminus[n]$ for all $p\in[l]$ to conclude.

Suppose toward contradiction that $\tilde{l}<l$. We require the following two
claims:

######  Claim 23.

It holds that $\tilde{l}<t$,
$\bigl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\bigr{\rceil}\geq s+1$, and
there exists $p\in[t]\setminus[\tilde{l}]$ for which

$\displaystyle\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\geq\biggl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\biggr{\rceil}.$
(91)

######  Claim 24.

For all $p\in[t]\setminus[\tilde{l}]$, it holds that

$\displaystyle\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}\leq\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+r-n+\tilde{l}-t+1$
(92)

Before proving these claims, we first use them to complete the proof of the
theorem. Let $p\in[t]\setminus[\tilde{l}]$ be as in Claim 23. Then,

$\displaystyle\lvert T_{p}\rvert$
$\displaystyle=\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}$
(93) $\displaystyle\leq
2\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+r-n+\tilde{l}-t+1$ (94)
$\displaystyle\leq
2\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+r-n-\biggl{\lceil}\frac{n-s\tilde{l}}{\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}}\biggr{\rceil}+1$
(95) $\displaystyle\leq
2\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+r-n-\biggl{\lceil}\frac{n-q+s}{\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}}\biggr{\rceil}+1$
(96) $\displaystyle\leq\sum_{j=1}^{m}(d_{j}^{T_{p}\cap[n]}-1)+1,$ (97)

where the first line is obvious, the second follows from Claim 24, the third
follows from Claim 23, the fourth follows from $\tilde{l}<l$, and the fifth
follows from (82) and the fact that
$\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\geq s+1$. So $\\{x_{a}:a\in T_{p}\\}$
splits, a contradiction. This completes the proof, modulo proving the claims.

###### Proof of Claim 23.

To prove the claim, we first observe that $n>st$. Indeed, if $n\leq st$ then

$\displaystyle r$
$\displaystyle=\sum_{p=1}^{t}\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}$
(98) $\displaystyle\geq n+t-\tilde{l}$ (99) $\displaystyle\geq
n+\frac{n-q}{s}+1,$ (100)

where the first line is obvious, the second follows from (89) and (90), and
the third follows from $n\leq st$ and $\tilde{l}<l$. This contradicts (81), so
it must hold that $n>st$.

Note that $\tilde{l}<t$, for otherwise we would have $n\leq st$ by the fact
that $\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\leq s$ for all $p\in[\tilde{l}]$.
To verify that $\bigl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\bigr{\rceil}\geq
s+1$, it suffices to prove $\frac{n-s\tilde{l}}{t-\tilde{l}}>s,$ which follows
from $n>st$. To verify (224), since
$\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\leq s$ for all $p\in[\tilde{l}]$, by
the pigeonhole principle there exists $p\in[t]\setminus[\tilde{l}]$ for which

$\displaystyle\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\geq\biggl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\biggr{\rceil}.$
(101)

This proves the claim. ∎

###### Proof of Claim 24.

Suppose toward contradiction that the inequality (92) does not hold for some
$\tilde{p}\in[t]\setminus[\tilde{l}]$. Then

$\displaystyle r$
$\displaystyle=\sum_{p=1}^{t}\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}$
(102)
$\displaystyle\geq\sum_{p\neq\tilde{p}}\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}+\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}+(r-n)+\tilde{l}-t+2$
(103) $\displaystyle\geq r+1,$ (104)

where the first two lines are obvious, and the last line follows from (89) and
(90), a contradiction. ∎

The proofs of Claims 23 and 24 complete the proof of the theorem. ∎

####  7.2.1 $s=1$ case of Theorem 22

In the $s=1$ case of Theorem 22, we can drop the assumption that the pair of
decompositions is irreducible. This is because the other assumptions already
imply that $\sum_{a\in[n]}x_{a}$ constitutes a (unique) tensor rank
decomposition by Theorem 2, so $\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$ will
automatically be irreducible (see the discussion at the beginning of Section
7).

######  Corollary 25 ($s=1$ case of Theorem 22).

Let $q\in[n-1]$ and $r$ be positive integers for which $n+1\leq r\leq 2n-q$.
If for every subset $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$ it holds
that

$\displaystyle 2\lvert
S\rvert+\max\left\\{0,(r-n)-\biggl{\lceil}\frac{n-q+1}{\lvert
S\rvert}\biggr{\rceil}+1\right\\}\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1,$ (105)

then for any multiset of product tensors
$\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
for which $\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$, there exist subsets
$Q\subseteq[n]$ and $R\subseteq[r]$ of size $\lvert Q\rvert=\lvert R\rvert=q$
for which ${\\{x_{a}:a\in Q\\}=\\{y_{a}:a\in R\\}}$ (in other words, this pair
of decompositions has a $(1,q)$-subpartition).

It is worth noting that although the assumptions of Corollary 25 require
$\sum_{a\in[n]}x_{a}$ to constitute a unique tensor rank decomposition, this
result can also be applied to arbitrary decompositions $\sum_{a\in[n]}x_{a}$,
provided that $\sum_{a\in S}x_{a}$ constitutes a unique tensor rank
decomposition for some subset $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq
n$, as one can simply apply Corollary 25 to the pair of decompositions
$(\sum_{a\in S}x_{a},\sum_{a\in[r]}y_{a}-\sum_{a\in[n]\setminus S}x_{a})$. It
is not difficult to produce explicit examples in which Corollary 25 can be
applied in this way (for instance, by modifying Example 26).

As an example, we now use Corollary 25 to prove uniqueness of non-rank
decompositions of the identity tensor $\sum_{a\in[n]}e_{a}^{\otimes 3}$.

######  Example 26.

Let $n\geq 2$, $q\in[n-1],$ and $r$ be positive integers for which $n+1\leq
r\leq 2n-q$ and

$\displaystyle q\leq n+1-\frac{1}{4}\left((r-n+2)^{2}+1\right).$ (106)

If

$\displaystyle\sum_{a\in[n]}e_{a}^{\otimes 3}=\sum_{a\in[r]}y_{a}$ (107)

for some multiset of product tensors
$\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\mathcal{V}_{2}:\mathcal{V}_{3}\right)$,
then there exist subsets $Q\subseteq[n]$ and $R\subseteq[n+r]$ of sizes
$\lvert Q\rvert=\lvert R\rvert=q$ such that ${\\{x_{a}:a\in
Q\\}={\\{y_{a}:a\in R\\}}}$. For example, if $r=n+1$ then we can take $q=n-2$
for any $n\geq 3$.

To verify Example 26, it suffices to show that the inequality (105) holds for
all $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$. This reduces to proving
that

$\displaystyle\lvert S\rvert(r-n+2-\lvert S\rvert)-(n-q+1)<0,$ (108)

which occurs whenever the polynomial in $\lvert S\rvert$ on the lefthand side
has no real roots, i.e. whenever

$\displaystyle(r-n+2)^{2}\leq 4(n-q+1)-1.$ (109)

####  7.2.2 Modifying Theorem 22 to apply to reducible pairs of decompositions

A drawback to Theorem 22 is that it only applies to irreducible pairs of
decompositions. We now present a modification of this result, which can
certify the existence of an $(s,l)$-subpartition even for reducible
decompositions, at the cost of stricter assumptions. We defer this proof to
the appendix, as it is very similar to that of Theorem 22.

######  Theorem 27.

Let $q\in[n-1]$, $s\in[q]$, and $r$ be positive integers for which

$\displaystyle n+1\leq
r\leq\biggl{\lceil}\left(\frac{s+1}{s}\right)(n-q+s)\biggr{\rceil}-1,$ (110)

and let $l=\lfloor q/s\rfloor$. If for every subset $S\subseteq[n]$ for which
$s+1\leq\lvert S\rvert\leq n,$ it holds that

$\displaystyle 2\lvert
S\rvert+\max\left\\{0,(r-n+q-s)-\biggl{\lceil}\frac{n-q+s}{\lvert
S\rvert}\biggr{\rceil}+1\right\\}\leq\sum_{j=1}^{m}(d_{j}^{S}-1)+1,$ (111)

then for any multiset of product tensors
$\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
for which $\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$, this pair of
decompositions has an $(s,l)$-subpartition.

####  7.2.3 $s=n-1$ case of Theorem 27

When $s=n-1$, then it necessarily holds that $r=n+1$ and $q=n-1$, and Theorem
27 simply says that if $2n+1\leq\sum_{j=1}^{m}(d_{j}-1)+1$, then
$\sum_{a\in[n]}x_{a}=\sum_{a\in[n+1]}y_{a}$ has an $(n-1,1)$-subpartition.
Theorem 22 yields a weaker statement.

##  8 A lower bound on tensor rank

In Section 7.1.1 we saw that for a multiset of product tensors
$\\{x_{a}:a\in[n]\\}$ with k-ranks
$k_{j}=\operatorname{k-rank}(x_{a,j}:a\in[n])$, it holds that

$\displaystyle\operatorname{rank}\bigg{[}\sum_{a\in[n]}x_{a}\bigg{]}\geq\min\bigg{\\{}n,\sum_{j=1}^{m}(k_{j}-1)+2-n\bigg{\\}}.$
(112)

In this section, we prove that when the k-ranks are sufficiently balanced, two
of the k-ranks $k_{i},k_{j}$ appearing in this bound can be replaced with
standard ranks $d_{i},d_{j}$, which improves this bound when the k-ranks and
ranks are not equal, and specializes to Sylvester’s matrix rank inequality
when $m=2$. We prove that this improved bound is independent of a different
lower bound on tensor rank that we observed in Corollary 17. We furthermore
observe that this improved bound is sharp in a wide parameter regime. As a
consequence, we obtain a lower bound on Waring rank, which we also prove is
sharp.

######  Theorem 28 (Tensor rank lower bound).

Let $n\geq 2$ and $m\geq 2$ be integers, let
${\mathcal{V}=\mathcal{V}_{1}\otimes\dots\otimes\mathcal{V}_{m}}$ be a vector
space over a field $\mathbb{F}$, and let

$\displaystyle{E=\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)}$
(113)

be a multiset of product tensors. For each index $j\in[m]$, let
$k_{j}=\operatorname{k-rank}(x_{a,j}:a\in[n])$ and
${d_{j}=\dim\operatorname{span}\\{x_{a,j}:a\in[n]\\}}$. Define

$\displaystyle\mu=\max_{\begin{subarray}{c}i,j\in[m]\\\ i\neq
j\end{subarray}}\\{d_{i}-k_{i}+d_{j}-k_{j}\\}.$ (114)

If for every index $i\in[m]$ it holds that

$\displaystyle k_{i}\leq\sum_{\begin{subarray}{c}j\in[m]\\\ j\neq
i\end{subarray}}(k_{j}-1)+1,$ (115)

then

$\displaystyle\operatorname{rank}\bigg{[}\sum_{a\in[n]}x_{a}\bigg{]}\geq\min\bigg{\\{}n,\mu+\sum_{j=1}^{m}(k_{j}-1)+2-n\bigg{\\}}.$
(116)

Intuitively, the condition (115) ensures that the k-ranks are sufficiently
balanced. This inequality is satisfied, for example, when the product tensors
are symmetric. While we are unaware whether the precise inequality (115) is
necessary for the lower bound (116) to hold, the following example illustrates
that some inequality of this form must hold:

######  Example 29.

The set of product tensors

$\displaystyle E=\\{e_{1}^{\otimes 3},e_{2}^{\otimes 3},e_{3}^{\otimes
3},e_{4}^{\otimes 3},e_{5}\otimes(e_{1}+e_{2})^{\otimes
2},e_{6}\otimes(e_{1}-e_{2})^{\otimes 2}\\}$ (117)

does not satisfy (116). Indeed,

$\displaystyle\operatorname{rank}[\Sigma(E)]$ $\displaystyle=5$ (118)
$\displaystyle<q+k_{1}+k_{2}+k_{3}-1-n$ (119) $\displaystyle=d_{2}+d_{3}-1$
(120) $\displaystyle=7.$ (121)

This example illustrates that in order for the bound (116) to hold, the
k-ranks must be sufficiently “balanced” in order to avoid cases such as this.
In particular, some inequality resembling (115) is necessary. We remark that
this example can be extended to further parameter regimes using Derksen’s
example [Der13], and similar arguments as in Sections 8.1 and 9.1.

Note that when $m=2$, Theorem 28 states that

$\displaystyle\operatorname{rank}\bigg{[}\sum_{a\in[n]}x_{a}\bigg{]}\geq
d_{1}+d_{2}-n,$ (122)

provided that $k_{1}=k_{2}$. This is Sylvester’s matrix rank inequality
(although Sylvester’s result holds also when $k_{1}\neq k_{2}$) [HJ13].

The following example demonstrates that our two lower bounds on tensor rank in
Theorem 28 and Corollary 17 are independent.

######  Example 30.

By Theorem 28, the sum of the set of product tensors

$\displaystyle\\{e_{1}^{\otimes 3},e_{2}^{\otimes 3},(e_{1}+e_{2})^{\otimes
2}\otimes e_{3},e_{3}^{\otimes 2}\otimes(e_{1}+e_{2}+e_{3})\\}$ (123)

has tensor rank $4$. Note that this bound cannot be achieved with the
flattening rank lower bound, nor with Corollary 17, as the first three vectors
do not satisfy (74). Many more such examples can be obtained using the
construction in Section 8.1.

Conversely, the sum of the set of product tensors

$\displaystyle\\{$ $\displaystyle e_{1}^{\otimes 3},e_{2}^{\otimes
3},e_{3}^{\otimes 3},e_{4}^{\otimes
3},(e_{2}+e_{3})\otimes(e_{2}+e_{4})\otimes(e_{1}+e_{4})\\}$ (124)

has tensor rank 5 by Corollary 17, while Theorem 28 only certifies that this
sum has tensor rank at least $4$.

Now we prove Theorem 28.

###### Proof of Theorem 28.

Let $r=\operatorname{rank}[\sum_{a\in[n]}x_{a}]$, and let
$\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\dots:\mathcal{V}_{m}\right)$
be a multiset of product tensors for which
$\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$ is a tensor rank decomposition. We
need to prove that $r$ satisfies the inequality (116). For each $a\in[r]$, let
$x_{n+a}=-y_{a}$, and let ${T_{1}\sqcup\dots\sqcup T_{t}=[n+r]}$ be the index
sets of the connected components of ${\\{x_{a}:a\in[n+r]\\}}$. For each subset
${S\subseteq[n]}$ and index $j\in[m]$, let

$\displaystyle d_{j}^{S}=\dim\operatorname{span}\\{x_{a,j}:a\in S\\}.$ (125)

We first consider the case $t=1$, i.e. $\\{x_{a}:a\in[n+r]\\}$ is connected.
By the splitting theorem, it holds that

$\displaystyle n+r$ $\displaystyle\geq\sum_{j=1}^{m}(d_{j}-1)+2$ (126)
$\displaystyle\geq\mu+\sum_{j=1}^{m}(k_{j}-1)+2,$ (127)

completing the proof in this case.

We proceed by induction on $t$. Suppose the theorem holds whenever the number
of connected components is less than $t$. Assume without loss of generality
that

$\displaystyle\bigl{\lvert}T_{1}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{1}\cap[n+r]\setminus[n]\bigr{\rvert}$
$\displaystyle\geq\bigl{\lvert}T_{2}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{2}\cap[n+r]\setminus[n]\bigr{\rvert}$
(128) $\displaystyle\;\;\vdots$ (129)
$\displaystyle\geq\bigl{\lvert}T_{{t}}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{{t}}\cap[n+r]\setminus[n]\bigr{\rvert}$
(130) $\displaystyle\geq 0,$ (131)

where the last line follows from the fact that $\sum_{a\in[r]}y_{a}$ is a
tensor rank decomposition. If

$\displaystyle\bigl{\lvert}T_{1}\cap[n]\bigr{\rvert}=\bigl{\lvert}T_{1}\cap[n+r]\setminus[n]\bigr{\rvert},$
(132)

then $r=n$ and we are done. Otherwise,

$\displaystyle\bigl{\lvert}T_{[t-1]}\cap[n]\bigr{\rvert}>\bigl{\lvert}T_{[t-1]}\cap[n+r]\setminus[n]\bigr{\rvert},$
(133)

where $T_{[t-1]}=T_{1}\sqcup\dots\sqcup T_{t-1}$.

Observe that $k_{j}<\bigl{\lvert}T_{[t-1]}\cap[n]\bigr{\rvert}$ for all
$j\in[m]$. Indeed, since

$\displaystyle\operatorname{rank}\bigg{[}\sum_{a\in
T_{[t-1]}\cap[n]}x_{a}\bigg{]}<\bigl{\lvert}T_{[t-1]}\cap[n]\bigr{\rvert},$
(134)

it must hold that

$\displaystyle
2\bigl{\lvert}T_{[t-1]}\cap[n]\bigr{\rvert}-1\geq\sum_{j=1}^{m}\bigg{(}\min\big{\\{}\bigl{\lvert}T_{[t-1]}\cap[n]\bigr{\rvert},k_{j}\big{\\}}-1\bigg{)}+2,$
(135)

by (112). If $k_{i}\geq\bigl{\lvert}T_{{[t-1]}}\cap[n]\bigr{\rvert}$ for some
$i\in[m]$, then this inequality implies that
${k_{j}<\bigl{\lvert}T_{{[t-1]}}\cap[n]\bigr{\rvert}}$ for all $j\neq i$, and
hence

$\displaystyle
k_{i}\geq\bigl{\lvert}T_{{[t-1]}}\cap[n]\bigr{\rvert}\geq\sum_{\begin{subarray}{c}j\in[m]\\\
j\neq i\end{subarray}}(k_{j}-1)+2,$ (136)

contradicting (115). So $k_{j}<\bigl{\lvert}T_{{[t-1]}}\cap[n]\bigr{\rvert}$
for all $j\in[m]$.

Since $k_{j}<\bigl{\lvert}T_{{[t-1]}}\cap[n]\bigr{\rvert}$ for all $j\in[m]$,
the k-ranks of $\\{x_{a}:a\in T_{[t-1]}\cap[n]\\}$ satisfy (115), so by the
induction hypothesis,

$\displaystyle\bigl{\lvert}T_{[t-1]}\bigr{\rvert}\geq\mu^{T_{[t-1]}\cap[n]}+\sum_{j=1}^{m}(k_{j}-1)+2,$
(137)

where

$\displaystyle\mu^{T_{[t-1]}\cap[n]}=\max_{\begin{subarray}{c}i,j\in[m]\\\
i\neq
j\end{subarray}}\bigg{\\{}d_{i}^{T_{[t-1]}\cap[n]}-k_{i}+d_{j}^{T_{[t-1]}\cap[n]}-k_{j}\bigg{\\}}.$
(138)

To complete the proof, we will show that

$\displaystyle\bigl{\lvert}T_{[t-1]}\bigr{\rvert}+\lvert
T_{t}\rvert\geq\mu+\sum_{j=1}^{m}(k_{j}-1)+2.$ (139)

Let $i,i^{\prime}\in[m]$ be such that
$\mu=d_{i}-k_{i}+d_{i^{\prime}}-k_{i^{\prime}}$. Then

$\displaystyle\bigl{\lvert}T_{[t-1]}\bigr{\rvert}+\lvert T_{t}\rvert$
$\displaystyle\geq
d_{i}^{T_{[t-1]}\cap[n]}-k_{i}+d_{i^{\prime}}^{T_{[t-1]}\cap[n]}-k_{i^{\prime}}+\sum_{j=1}^{m}(k_{j}-1)+\sum_{j=1}^{m}(d_{j}^{T_{t}\cap[n]}-1)+4$
(140) $\displaystyle\geq
d_{i}^{T_{[t-1]}\cap[n]}-k_{i}+d_{i^{\prime}}^{T_{[t-1]}\cap[n]}-k_{i^{\prime}}+\sum_{j=1}^{m}(k_{j}-1)+d_{i}^{T_{t}\cap[n]}+d_{i^{\prime}}^{T_{t}\cap[n]}+2$
(141) $\displaystyle\geq
d_{i}-k_{i}+d_{i^{\prime}}-k_{i^{\prime}}+\sum_{j=1}^{m}(k_{j}-1)+2$ (142)
$\displaystyle=\mu+\sum_{j=1}^{m}(k_{j}-1)+2,$ (143)

where the first line follows from (137) and the fact that $\\{x_{a}:a\in
T_{t}\\}$ is connected, the second is obvious, the third is easy to verify (in
matroid-theoretic terms, this is submodularity of the rank function), and the
fourth is by definition. This completes the proof. ∎

As an immediate corollary to Theorem 28, we obtain the following lower bound
on the Waring rank of a symmetric tensor, in terms of a known symmetric
decomposition.

######  Corollary 31 (Waring rank lower bound).

Let $n\geq 2$, and $m\geq 2$ be integers, let $\mathcal{W}$ be a vector space
over a field $\mathbb{F}$ with $\mathrm{Char}(\mathbb{F})=0$ or
$\mathrm{Char}(\mathbb{F})>m$, and let
${\\{v_{a}:a\in[n]\\}\subseteq\mathcal{W}\setminus\\{0\\}}$ be a multiset of
non-zero vectors. Let

$\displaystyle k={\operatorname{k-rank}(v_{a}:a\in[n])}$ (144)

and

$\displaystyle{d=\dim\operatorname{span}\\{v_{a}:a\in[n]\\}}.$ (145)

Then for any multiset of non-zero scalars

$\displaystyle\\{\alpha_{a}:a\in[n]\\}\subseteq\mathbb{F}^{\times},$ (146)

it holds that

$\displaystyle\mathrm{WaringRank}\bigg{[}\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes
m}\bigg{]}\geq\min\\{n,2d+(m-2)(k-1)-n\\}.$ (147)

###  8.1 Our tensor rank lower bound is sharp

In this subsection, we observe that, in a wide parameter regime, the
inequalities (116) and (147) appearing in Theorem 28 and Corollary 31 cannot
be improved.

Let $\mathbb{F}$ be a field with $\mathrm{Char}(\mathbb{F})=0$, let $n\geq 2$,
${m\geq 2}$,

$\displaystyle 2\leq d_{1},\dots,d_{m}\leq n,$ (148)

and

$\displaystyle{k_{1}\leq d_{1},\dots,k_{m}\leq d_{m}}$ (149)

be positive integers, and let

$\displaystyle\lambda=\sum_{j=1}^{m}(k_{j}-1)+2.$ (150)

Suppose that the following conditions hold:

  1. 1.

${\mu=2(d_{i}-k_{i})}$ for some index $i\in[m]$, where $\mu$ is defined as in
(114).

  2. 2.

$\max\\{k_{j}:j\in[m]\\}+d_{i}-k_{i}+1\leq n\leq d_{i}-k_{i}+\lambda$

  3. 3.

The inequality (115) is satisfied.

Then there exists a multiset of product tensors $E$ corresponding to these
choices of parameters that satisfies (116) with equality. Indeed, the bound
$\operatorname{rank}[\Sigma(E)]\geq n$ is trivial to attain with equality, and
the bound

$\displaystyle\operatorname{rank}[\Sigma(E)]\geq 2(d_{i}-k_{i})+\lambda-n$
(151)

can be attained with equality as follows. Let

$\displaystyle\\{x_{a}:a\in[\lambda]\\}\subseteq\mathrm{Prod}\left(\mathbb{F}^{d_{1}}:\dots:\mathbb{F}^{d_{m}}\right)$
(152)

be a multiset of product tensors that forms a circuit and satisfies

$\displaystyle\dim\operatorname{span}\\{x_{a,j}:a\in[\lambda]\\}=\operatorname{k-rank}(x_{a,j}:a\in[\lambda])=k_{j}$
(153)

for all $j\in[m]$. An example of such a circuit is presented in [Der13], and
reviewed in Section 6. Now, let

$\displaystyle\\{x_{a}:a\in[\lambda+d_{i}-k_{i}]\setminus[\lambda]\\}\subseteq\mathrm{Prod}\left(\mathbb{F}^{d_{1}}:\dots:\mathbb{F}^{d_{m}}\right)$
(154)

be any multiset of product tensors for which

$\displaystyle\dim\operatorname{span}\\{x_{a,j}:a\in[\lambda+d_{i}-k_{i}]\\}=d_{j}$
(155)

and

$\displaystyle\operatorname{k-rank}(x_{a,j}:a\in[\lambda+d_{i}-k_{i}])=k_{j}$
(156)

for all $j\in[m]$, which is guaranteed to exist since $\mathbb{F}$ is
infinite. Let

$\displaystyle
E=\\{x_{a}:a\in[n-d_{i}+k_{i}]\\}\sqcup\\{x_{a}:a\in[\lambda+d_{i}-k_{i}]\setminus[\lambda]\\}$
(157)

and

$\displaystyle
F=\\{x_{a}:a\in[\lambda]\setminus[n-d_{i}+k_{i}]\\}\sqcup\\{x_{a}:a\in[\lambda+d_{i}-k_{i}]\setminus[\lambda]\\}.$
(158)

Recall that $n\leq d_{i}-k_{i}+\lambda$ by assumption, so the set
$[\lambda]\setminus[n-d_{i}+k_{i}]$ that appears in the definition of $F$ is
well-defined. Since $n-d_{i}+k_{i}\geq k_{j}+1$ for all $j\in[m]$, $E$ has
k-ranks $k_{1},\dots,k_{m},$ as desired. It is also clear that $E$ has ranks
$d_{1},\dots,d_{m}$, by (153) and (155). Since $\\{x_{a}:a\in[\lambda]\\}$
forms a circuit, some non-zero linear combination of $E$ is equal to a non-
zero linear combination of $F$. Since $\lvert F\rvert$ is equal to the right
hand side of (151), this completes the proof.

Out of the three conditions required for our construction,
$\mu=2(d_{i}-k_{i})$ seems the most restrictive. Unfortunately, our methods
appear to require this condition. A nearly identical construction shows that
the inequality (147) appearing in Corollary 31 cannot be improved (and our
restrictive condition on $\mu$ is automatically satisfied in this case). The
only difference in the construction is to choose the product tensors
$\\{x_{a}:a\in[\lambda+d_{i}-k_{i}]\\}$ to be symmetric in this case, which
can always be done (in particular, the product tensors appearing in Derksen’s
example can be taken to be symmetric).

##  9 A uniqueness result for non-Waring rank decompositions

In this section, we prove a sufficient condition on a symmetric decomposition

$\displaystyle v=\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$ (159)

under which any distinct decomposition
$v=\sum_{a\in[r]}\beta_{a}u_{a}^{\otimes m}$ must have $r$ lower bounded by
some quantity, which we call $r_{\min}$ for now. When $r_{\min}\leq n$, this
yields a lower bound on $\mathrm{WaringRank}(v)$ that is contained in
Corollary 31. When ${r_{\min}=n+1}$, this yields a uniqueness criterion for
symmetric decompositions that is contained in Theorem 2, but improves
Kruskal’s theorem in a wide parameter regime. The main result in this section
is the case ${r_{\min}>n+1}$, where we obtain an even stronger statement than
uniqueness: Every symmetric decomposition of $v$ into less than $r_{\min}$
terms must be equal to $\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$ (in the
language introduced in Section 3, $\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$
is the unique symmetric decomposition of $v$ into less than $r_{\min}$ terms).
In Section 9.1 we prove that our bound $r_{\min}$ cannot be improved. In
Section 9.2 we identify potential applications of our non-rank uniqueness
results.

Our results in this section were inspired by, and generalize, Theorem 6.8 and
Remark 6.14 in [Chi19]. Our results in this section should be compared with
those of Section 7.2 on uniqueness of non-rank decompositions of tensors that
are not necessarily symmetric.

######  Theorem 32.

Let $n\geq 2$ and $m\geq 2$ be integers, let $\mathcal{W}$ be a vector space
over a field $\mathbb{F}$ with $\mathrm{Char}(\mathbb{F})=0$ or
$\mathrm{Char}(\mathbb{F})>m$, let
$E={\\{v_{a}:a\in[n]\\}\subseteq\mathcal{W}\setminus\\{0\\}}$ be a multiset of
non-zero vectors with ${\operatorname{k-rank}(v_{a}:a\in[n])\geq 2}$, and let

$\displaystyle{d=\dim\operatorname{span}\\{v_{a}:a\in[n]\\}}.$ (160)

Then for any non-negative integer $r\geq 0$, multiset of non-zero vectors
${F={\\{u_{a}:a\in[r]\\}\subseteq\mathcal{W}\setminus\\{0\\}}}$ with
${\operatorname{k-rank}(u_{a}:a\in[r])\geq\min\\{2,r\\}}$, and multisets of
non-zero scalars

$\displaystyle\\{\alpha_{a}:a\in[n]\\},\\{\beta_{a}:a\in[r]\\}\subseteq\mathbb{F}^{\times}$
(161)

for which

$\displaystyle\\{\alpha_{a}v_{a}^{\otimes
m}:a\in[n]\\}\neq\\{\beta_{a}u_{a}^{\otimes m}:a\in[r]\\}$ (162)

and

$\displaystyle\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes
m}=\sum_{a\in[r]}\beta_{a}u_{a}^{\otimes m},$ (163)

it holds that

$\displaystyle n+r\geq m+2d-2.$ (164)

In the language of the introduction to this section, $r_{\min}=m+2d-2-n$. For
comparison, the result we have referred to in [Chi19] asserts that, under the
condition $n\leq m$, it holds that $n+r\geq m+d$, which is weaker than our
bound (164).

###### Proof of Theorem 32.

By subtracting terms from both sides of (163), and combining parallel product
tensors into single terms (or to zero), it is clear that it suffices to prove
the statement when $E$ is linearly independent (so $d=n$).

Note that $r\geq n$ by Kruskal’s theorem. For each $a\in[r]$, let
$v_{n+a}=u_{a}$, and let ${T_{1}\sqcup\dots\sqcup T_{t}=[n+r]}$ be the index
sets of the connected components of ${\\{v_{a}^{\otimes m}:a\in[n+r]\\}}$.
Assume without loss of generality that
$\bigl{\lvert}T_{1}\cap[n]\bigr{\rvert}\geq\dots\geq\bigl{\lvert}T_{t}\cap[n]\bigr{\rvert}$,
and let $\tilde{t}\in[t]$ be the largest integer for which
$\bigl{\lvert}T_{\tilde{t}}\cap[n]\bigr{\rvert}\geq 1$. By (162), there must
exist $\tilde{p}\in[\tilde{t}]$ for which $\lvert T_{\tilde{p}}\rvert\geq 3$.
Note that

$\displaystyle\dim\operatorname{span}\\{v_{a}:a\in
T_{\tilde{p}}\\}\geq\max\left\\{2,\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}\right\\}.$
(165)

Since $\\{v_{a}^{\otimes m}:a\in T_{\tilde{p}}\\}$ is connected, it follows
from our splitting theorem that

$\displaystyle\lvert T_{\tilde{p}}\rvert\geq
m(\max\left\\{2,\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}\right\\}-1)+2.$
(166)

Now,

$\displaystyle n+r$ $\displaystyle\geq\sum_{p\in[\tilde{t}]}\lvert
T_{p}\rvert$ (167)
$\displaystyle\geq\sum_{p\neq\tilde{p}}\big{[}m\left(\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}-1\right)+2\big{]}+m\left(\max\left\\{2,\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}\right\\}-1\right)+2$
(168) $\displaystyle=m\left(n-\lvert
T_{\tilde{p}}\cap[n]\rvert\right)-(m-2)\left(\tilde{t}-1\right)+m\left(\max\left\\{2,\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}\right\\}-1\right)+2$
(169) $\displaystyle\geq m\left(n-\lvert
T_{\tilde{p}}\cap[n]\rvert\right)-(m-2)\left(n-\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}\right)+m\left(\max\left\\{2,\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}\right\\}-1\right)+2$
(170)
$\displaystyle=2n-2\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}+m\left(\max\left\\{2,\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}\right\\}-1\right)+2$
(171) $\displaystyle\geq 2n+m-2.$ (172)

The first line is obvious, the second follows from (166) and the fact that
every multiset $\\{v_{a}^{\otimes m}:a\in T_{p}\\}$ is connected, the third is
algebra, the fourth uses the fact that
$\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\geq 1$ for all $p\in[\tilde{t}]$, and
the rest is algebra. This completes the proof. ∎

Theorem 32 immediately implies the following uniqueness result for non-Waring
rank decompositions.

######  Corollary 33 (Uniqueness result for non-Waring rank decompositions).

Let $n\geq 2$ and $m\geq 2$ be integers, let $\mathcal{W}$ be a vector space
over a field $\mathbb{F}$ with $\mathrm{Char}(\mathbb{F})=0$ or
$\mathrm{Char}(\mathbb{F})>m$, let
${\\{v_{a}:a\in[n]\\}\subseteq\mathcal{W}\setminus\\{0\\}}$ be a multiset of
non-zero vectors with ${\operatorname{k-rank}(v_{a}:a\in[n])\geq 2}$, let
$\\{\alpha_{a}:a\in[n]\\}\subseteq\mathbb{F}^{\times}$ be a multiset of non-
zero scalars, and let ${d=\dim\operatorname{span}\\{v_{a}:a\in[n]\\}}$. If

$\displaystyle 2n+1\leq m+2d-2,$ (173)

then $\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$ constitutes a unique Waring
rank decomposition. More generally, if

$\displaystyle n+r+1\leq m+2d-2,$ (174)

for some $r\geq n$, then $\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes m}$ is the
unique symmetric decomposition of this tensor into at most $r$ terms.

Note that the $r=n$ case of Corollary 33 improves Kruskal’s theorem for
symmetric decompositions as soon as $2d>m(k-2)+4$, where
$k=\operatorname{k-rank}(v_{a}:a\in[n])$. This case of Corollary 33 is in fact
contained in our generalization of Kruskal’s theorem (Theorem 2), since for
every subset $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$, it holds that

$\displaystyle 2\lvert S\rvert$ $\displaystyle=2n-2\bigl{\lvert}[n]\setminus
S\bigr{\rvert}$ (175) $\displaystyle\leq m+2d-2\bigl{\lvert}[n]\setminus
S\bigr{\rvert}-3$ (176) $\displaystyle\leq m+2d^{S}-3$ (177)
$\displaystyle\leq m(d^{S}-1)+1,$ (178)

where $d^{S}=\dim\operatorname{span}\\{v_{a}:a\in S\\}$. This demonstrates
that our generalization of Kruskal’s theorem is stronger than Kruskal’s
theorem, even for symmetric tensor decompositions.

Our main result in this section is the $r>n$ case of Corollary 33, which
yields uniqueness results for non-Waring rank decompositions of
$\sum_{a\in[n]}\alpha_{a}v_{a}^{\otimes n}$. The following example illustrates
this case in practice.

######  Example 34.

It follows from Corollary 33 that for any positive integers $m\geq 3$ and
$n\geq 2$, $\sum_{a\in[n]}e_{a}^{\otimes m}$ is the unique symmetric
decomposition of this tensor into at most $m+n-3$ terms.

It is natural to ask if Corollary 33 can be improved under further
restrictions on $\operatorname{k-rank}(v_{a}:a\in[n])$. At the end of Section
9.1 we prove that this cannot be done, at least in a particular parameter
regime.

###  9.1 The inequality appearing in our uniqueness result is sharp

In this subsection we prove that the inequality (164) that appears in Theorem
32 cannot be improved, by constructing explicit multisets of symmetric product
tensors that satisfy this bound with equality.

Let $\mathbb{F}$ be a field with $\mathrm{Char}(\mathbb{F})=0$. We will prove
that for any choice of positive integers $m\geq 2$, $d\geq 2$, $r\geq d-2$,
and $n\geq d$ for which $n+r=m+2d-2$, there exist multisets of non-zero
vectors $E$ and $F$ that satisfy the assumptions of Theorem 32. Note that the
inequality ${r\geq d-2}$ automatically holds when $r\geq n$, so this
assumption does not restrict the parameter regime in which the inequality
appearing in our uniqueness result (Corollary 33) is sharp as a consequence.

We first consider the case $d=2$. Let $\\{v_{a}^{\otimes
m}:a\in[m+2]\\}\subseteq\mathrm{Prod}\left(\mathbb{F}^{2}:\dots:\mathbb{F}^{2}\right)$
be a circuit of symmetric product tensors for which

$\displaystyle\operatorname{k-rank}(v_{a}:a\in[m+2])=2.$ (179)

An example of such a circuit is given in [Der13], and reviewed in Section 6.
So there exist non-zero scalars
$\\{\alpha_{a}:a\in[m+2]\\}\subseteq\mathbb{F}^{\times}$ for which
$\sum_{a\in[m+2]}\alpha_{a}v_{a}^{\otimes m}=0,$ and we can take the multisets
$E=\\{v_{a}:a\in[n]\\}$ and $F=\\{v_{a}:a\in[m+2]\setminus[n]\\}$ to conclude.

For $d\geq 3$, let $\\{v_{a}^{\otimes
m}:a\in[m+2]\\}\subseteq\mathrm{Prod}\left(\mathbb{F}^{d}:\dots:\mathbb{F}^{d}\right)$
be the same multiset of symmetric product tensors as above, embedded in a
larger space. Let

$\displaystyle\\{v_{a}:a\in[d+m]\setminus[m+2]\\}\subseteq\mathbb{F}^{d}\setminus\\{0\\}$
(180)

be any multiset of non-zero vectors for which

$\displaystyle\dim\operatorname{span}\\{v_{a}:a\in[d+m]\\}=d$ (181)

and

$\displaystyle\operatorname{k-rank}\\{v_{a}:a\in[d+m]\\}\geq 2,$ (182)

which is guaranteed to exist since $\mathbb{F}$ is infinite. Since $r\geq
d-2$, we can take the multisets

$\displaystyle
E=\\{v_{a}:a\in[n-d+2]\\}\sqcup\\{v_{a}:a\in[d+m]\setminus[m+2]\\}$ (183)

and

$\displaystyle
F=\\{v_{a}:a\in[m+2]\setminus[n-d+2]\\}\sqcup\\{v_{a}:a\in[d+m]\setminus[m+2]\\}$
(184)

to conclude.

Somewhat surprisingly, the inequality (164) is very nearly sharp even when the
k-rank condition is tightened to ${\operatorname{k-rank}(v_{a}:a\in[n])\geq
k}$ for some $k\geq 3$, under certain parameter constraints. More
specifically, for any $k\in\\{3,4,\dots,d-1\\}$, it is almost sharp under the
choice $n=d+1$ and $r=m+d-1$. Let

$\displaystyle
E=\\{v_{a}:a\in[d+m]\setminus[m]\\}\sqcup\bigg{\\{}\sum_{a\in[k]}v_{a}\bigg{\\}},$
(185)

and

$\displaystyle
F=\\{v_{a}:a\in[m]\\}\sqcup\\{v_{a}:a\in[d+m]\setminus[m+2]\\}\sqcup\bigg{\\{}\sum_{a\in[k]}v_{a}\bigg{\\}}.$
(186)

Here, $\lvert E\rvert+\lvert F\rvert=2d+m,$ exceeding our lower bound by 2.
When $k=d$, take the same multisets $E$ and $F$, with $\sum_{a\in[d]}v_{a}$
removed, to observe that our bound is sharp under the choice $n=d$ and
$r=m+d-2$. Note that the k-rank is brought down to $k$ because of a single
vector in the multiset. This is a concrete demonstration of the fact that the
k-rank is a very crude measure of genericity. We emphasize that this
construction relies on the particular choice of parameters $n=d+1$, and
$r=m+d-1$. It is possible that the inequality (164) could be significantly
stengthened for other choices of $n$ and $r$. Indeed, we have exhibited such
an improvement for $r\leq n$ in Corollary 31.

###  9.2 Applications of non-rank uniqueness results

In this subsection, we identify potential applications of our results on
uniqueness of non-rank decompositions. For concreteness, we focus on the
symmetric case and our non-Waring rank uniqueness result in Corollary 33,
however similar comments can be applied to our analogous results in Section
7.2 in the non-symmetric case.

We say a symmetric tensor $v$ is identifiable if it has a unique Waring rank
decomposition. For the purposes of this discussion, we will say that $v$ is
$r$-identifiable for some ${r\geq\operatorname{rank}(v)}$ if the Waring rank
decomposition of $v$ is the unique symmetric decomposition of $v$ into at most
$r$ terms (see Section 3). Corollary 33 provides a sufficient condition for a
symmetric tensor $v$ to be $r$-identifiable for $r>\operatorname{rank}(v)$,
and Example 34 demonstrates the existence of symmetric tensors satisfying this
condition. We can thus define a hierarchy of identifiable symmetric tensors
(of some fixed rank), where those that are $r$-identifiable for larger $r$ can
be thought of as “more identifiable.” We suggest that studying this hierarchy
could be a useful tool for studying symmetric tensor decompositions. For
example, although most symmetric tensors of sub-generic rank are identifiable,
it is notoriously difficult to find the rank decomposition of such tensors
[Lan12, BCMV14, COV17b]. Perhaps one can leverage the additional structure of
$r$-identifiable symmetric tensors to find efficient decompositions.

In applications, one often has a symmetric decomposition of a tensor, and
wants to control the possible symmetric decompositions with fewer terms.
Uniqueness results for non-rank decompositions can be turned around to apply
in this setting: Suppose we know that if a symmetric decomposition into $n$
terms satisfies some condition, call it $C$, then it is the unique symmetric
decomposition into at most $r$ terms, for some $r>n$. Then if one starts with
a symmetric decomposition of a symmetric tensor $v$ into $r$ terms, she knows
that there are no symmetric decompositions of $v$ into $n<r$ terms that
satisfies condition $C$. In this way, one can use a non-rank uniqueness result
to control the possible decompositions of $v$ into fewer than $r$ symmetric
product tensors. Applying this reasoning to our Corollary 33 simply yields a
special case of Theorem 32. However, applying analogous reasoning to Corollary
25 in the non-symmetric case seems to produce new results.

##  10 Comparing our generalization of Kruskal’s theorem to the uniqueness
criteria of Domanov, De Lathauwer, and Sørensen

In this section we compare our generalization of Kruskal’s theorem to
uniqueness criteria obtained by Domanov, De Lathauwer, and Sørensen (DLS) in
the case of three subsystems [DL13a, DL13b, DL14, SL15, SDL15], which are the
only previously known extensions of Kruskal’s theorem that we are aware of. A
drawback to the uniqueness criteria of DLS is that, similarly to Kruskal’s
theorem, they require the k-ranks to be above a certain threshold. In Section
10.1 we make this statement precise, and show by example that our
generalization of Kruskal’s theorem can certify uniqueness below this
threshold. Moreover, in Section 10.2 we observe that our generalization of
Kruskal’s theorem contains many of the uniqueness criteria of DLS. The
uniqueness criteria of DLS are spread across five papers, and can be difficult
to keep track of. For clarity and future reference, in Theorem 36 we combine
all of these criteria into a single statement. In Section 10.3 we use insight
gained from this synthesization and our Theorem 2 as evidence to support a
conjectural uniqueness criterion that would contain and unify every uniqueness
criteria of DLS into a single, elegant statement.

For the remainder of this section, we fix a vector space
$\mathcal{V}=\mathcal{V}_{1}\otimes\mathcal{V}_{2}\otimes\mathcal{V}_{3}$ over
a field $\mathbb{F}$, and a multiset of product tensors

$\displaystyle\\{x_{a}:a\in[n]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\mathcal{V}_{2}:\mathcal{V}_{3}\right)$
(187)

with k-ranks $k_{j}=\operatorname{k-rank}(x_{a,j}:a\in[n])$ for each
$j\in[3]$. For each subset $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$
and index $j\in[3]$, we let

$\displaystyle d_{j}^{S}=\dim\operatorname{span}\\{x_{a,j}:a\in[n]\\}.$ (188)

We also let $d_{j}=d_{j}^{[n]}$ for all $j\in[3]$.

###  10.1 Uniqueness below the k-rank threshold of DLS

All of the uniqueness criteria of DLS require the k-ranks to be above a
certain threshold. In this subsection, we show by example that our
generalization of Kruskal’s theorem can certify uniqueness below this
threshold.

Making this threshold precise, the uniqueness criteria of DLS cannot be
applied whenever

$\displaystyle\min\\{k_{2},k_{3}\\}\leq n-d_{1}+1,$ and
$\displaystyle\min\\{k_{1},k_{3}\\}\leq n-d_{2}+1,$ and
$\displaystyle\min\\{k_{1},k_{2}\\}\leq n-d_{3}+1.$ (189)

For example, if $k_{2}=k_{3}=2$, then the uniqueness criteria of DLS can only
certify uniqueness if $d_{1}=n$. The following example shows that our
generalization of Kruskal’s theorem (Theorem 2) can certify uniqueness even if
(10.1) holds.

######  Example 35.

Consider the multiset of product tensors

$\displaystyle\\{$ $\displaystyle\alpha_{1}e_{1}^{\otimes
3},\alpha_{2}e_{2}^{\otimes 3},\alpha_{3}e_{3}^{\otimes
3},\alpha_{4}e_{4}^{\otimes
3},\alpha_{5}(e_{2}+e_{3})\otimes(e_{2}+e_{4})\otimes(e_{1}+e_{4})\\}\quad\text{for}\quad\alpha_{1},\dots,\alpha_{5}\in\mathbb{F}^{\times}.$
(190)

In this example, $k_{1}=k_{2}=k_{3}=2$, $d_{1}=d_{2}=d_{3}=4$, and
$n-d_{j}+2=3$ for all $j\in[3]$, so (10.1) holds. Nevertheless, for arbitrary
$\alpha_{1},\dots,\alpha_{5}\in\mathbb{F}^{\times}$, our generalization of
Kruskal’s theorem certifies that the sum of these product tensors constitutes
a unique tensor rank decomposition. We note that uniqueness for
$\alpha_{2}=\dots=\alpha_{5}=1$ was proven in [DL13b, Example 5.2], using a
proof specific to this case, in order to demonstrate that their uniqueness
criteria are not also necessary for uniqueness.

Example 35 shows that Theorem 2 is strictly stronger than Kruskal’s theorem,
and is independent of the uniqueness criteria of DLS. It is natural to ask if
Theorem 2 is stronger than Kruskal’s theorem even for symmetric tensor
decompositions. We have observed in Section 9 that this is indeed the case.

###  10.2 Extending several uniqueness criteria of DLS

In this subsection, we observe that several of the uniqueness criteria of DLS
are contained in our generalization of Kruskal’s theorem, and prove a further,
independent uniqueness criterion. The uniqueness criteria of DLS are numerous,
and can be difficult to keep track of. To more easily analyze these criteria,
in Theorem 36 we combine them all into a single statement.

####  10.2.1 Conditions U, H, C, and S

Here we introduce several different conditions on multisets of product
tensors, which will make the uniqueness criteria of DLS easier to state, and
also make them easier to relate to our generalization of Kruskal’s theorem. We
first recall Conditions U, H, and C from [DL13a, DL13b]. For notational
convenience, we have changed these definitions slightly from [DL13a, DL13b].
For example, our Condition U is their Condition $U_{n-d_{1}+2}$, with the
added condition that $k_{1}\geq 2$. After reviewing Conditions U, H, and C, we
introduce Condition S, which captures the conditions of our generalization of
Kruskal’s theorem in the case ${m=3}$. Unlike Conditions U, H, and C, our
Condition S does not appear in [DL13a, DL13b], nor anywhere else that we are
aware of.

For a vector $\alpha\in\mathbb{F}^{n}$, we let $\omega(\alpha)$ denote the
number of non-zero entries in $\alpha$.

  * Condition U. It holds that $k_{1}\geq 2$, and for all $\alpha\in\mathbb{F}^{n}$,

$\displaystyle\operatorname{rank}\Big{[}\sum_{a\in[n]}\alpha_{a}x_{a,2}\otimes
x_{a,3}\Big{]}\geq\min\\{\omega(\alpha),n-d_{1}+2\\}.$ (191)

  * Condition H. It holds that $k_{1}\geq 2$, and

$\displaystyle d_{2}^{S}\\!+d_{3}^{S}\\!-\lvert S\rvert\geq\min\\{\lvert
S\rvert,n-d_{1}\\!+2\\}$ (192)

for all $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$.

Condition C takes a bit more work to describe. We use coordinates for this
condition, in order to avoid having to introduce further multilinear algebra
notation. For positive integers $q,r,$ and $t$, and matrices

$\displaystyle
Y=(y_{1},\dots,y_{t})\in\mathrm{L}(\mathbb{F}^{t},\mathbb{F}^{q})$ (193)
$\displaystyle
Z=(z_{1},\dots,z_{t})\in\mathrm{L}(\mathbb{F}^{t},\mathbb{F}^{r}),$ (194)

let

$\displaystyle Y\odot Z=(y_{1}\otimes z_{1},\dots,y_{t}\otimes
z_{t})\in\mathrm{L}(\mathbb{F}^{t},\mathbb{F}^{qr})$ (195)

denote the Khatri-Rao product of $Y$ and $Z$. Suppose
$\mathcal{V}_{j}=\mathbb{F}^{d_{j}}$ for each $j\in[3]$, and consider the
matrices

$\displaystyle
X_{j}=(x_{1,j},\dots,x_{n,j})\in\mathrm{L}(\mathbb{F}^{n},\mathbb{F}^{d_{j}})$
(196)

for $j\in[3]$. For a positive integer $s\leq d_{j}$, let
$\mathcal{C}_{s}(X_{j})$ be the $\binom{d_{j}}{s}\times\binom{n}{s}$ matrix of
$s\times s$ minors of $X_{j}$, with rows and columns arranged according to the
lexicographic order on the size $s$ subsets of $[d_{j}]$ and $[n]$,
respectively. Define the matrix

$\displaystyle
C_{s}=\mathcal{C}_{s}(X_{2})\odot\mathcal{C}_{s}(X_{3})\in\mathrm{L}(\mathbb{F}^{\binom{n}{s}},\mathbb{F}^{q}),$
(197)

where $q=\big{(}\begin{subarray}{c}d_{2}\\\
s\end{subarray}\big{)}\big{(}\begin{subarray}{c}d_{3}\\\
s\end{subarray}\big{)}$. Now we can state Condition C.

  * Condition C. It holds that $k_{1}\geq 2$, $\min\\{d_{2},d_{3}\\}\geq n-d_{1}+2$, and

$\displaystyle\operatorname{rank}(C_{n-d_{1}+2})=\left(\begin{subarray}{c}n\\\
n-d_{1}+2\end{subarray}\right).$ (198)

To more easily compare our generalization of Kruskal’s theorem to the
uniqueness criteria of DLS, we give a name (Condition S) to the condition of
our Theorem 2 in the case $m=3$.

  * Condition S. It holds that

$\displaystyle 2\lvert S\rvert\leq d_{1}^{S}+d_{2}^{S}+d_{3}^{S}-2$ (199)

for all $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$.

These conditions are related to each other as follows:

Condition HCondition CCondition UCondition S (200)

All of the implications in (200) except (Condition H $\Rightarrow$ Condition
S) were proven in [DL13a]. To see that Condition H $\Rightarrow$ Condition S,
note that for any subset $S\subseteq[n]$ with $2\leq\lvert S\rvert\leq n$, the
condition $k_{1}\geq 2$ implies

$\displaystyle d_{1}^{S}\geq\max\\{2,d_{1}-(n-\lvert S\rvert)\\},$ (201)

so by Condition H,

$\displaystyle d_{1}^{S}+d_{2}^{S}+d_{3}^{S}$
$\displaystyle\geq\max\\{2,d_{1}-(n-\lvert S\rvert)\\}+\lvert
S\rvert+\min\\{\lvert S\rvert,n-d_{1}+2\\}$ (202) $\displaystyle\geq 2\lvert
S\rvert+2,$ (203)

and Condition S holds. It is easy to find examples that certify Condition C
$\not\Rightarrow$ Condition S. By Example 35, Condition S $\not\Rightarrow$
Condition U. In [DL13a] it is asked whether Condition H $\Rightarrow$
Condition C. Condition U is theoretically computable, as it can be phrased as
an ideal membership problem, however we are unaware of an efficient
implementation. By comparison, Conditions C, H, and S are easy to check.

In the case of three subsystems, our Theorem 2 states that Condition S implies
uniqueness. Since Condition H $\Rightarrow$ Condition S, then a corollary to
Theorem 2 is that Condition H implies uniqueness. Similarly, Theorem 36 below
states that Condition U + extra assumptions implies uniqueness. By (200), this
implies that Condition H + the same extra assumptions implies uniqueness, and
similarly, Condition C + the same extra assumptions implies uniqueness. Since
we have proven that Condition H alone implies uniqueness, it is natural to ask
whether Conditions C or U alone imply uniqueness. We reiterate this line of
reasoning in Section 10.3, and pose this question formally.

####  10.2.2 Synthesizing the uniqueness criteria of DLS

The following theorem contains every uniqueness criterion of DLS for which we
are aware of an efficient implementation. This theorem is stated in terms of
Condition U to maintain generality, however only the implied statements in
which Condition U is replaced by Conditions H or C have an efficient
implementation. Note that our Theorem 2 generalizes the Condition H version of
this theorem, to the statement that Condition S alone implies uniqueness (so
in particular, Condition H alone implies uniqueness).

######  Theorem 36.

Suppose that Condition U holds, and any one of the following conditions holds:

  1. 1.

$k_{1}+\min\\{k_{2},k_{3}-1\\}\geq n+1.$

  2. 2.

It holds that $k_{2}\geq 2$ and for all $\alpha\in\mathbb{F}^{n}$,

$\displaystyle\mathrm{rank}\Big{[}\sum_{a\in[n]}\alpha_{a}x_{a,1}\otimes
x_{a,3}\Big{]}\geq\min\\{\omega(\alpha),n-d_{2}+2\\}.$ (204)

(Note that this is just Condition U with the first subsystem replaced by the
second).

  3. 3.

There exists a subset $S\subseteq[n]$ with $0\leq|S|\leq d_{1}$ such that the
following three conditions hold:

    1. (a)

$d_{1}^{S}=|S|.$

    2. (b)

$d_{2}^{[n]\setminus S}=n-|S|.$

    3. (c)

For any linear map $\Pi\in\mathrm{L}(\mathcal{V}_{1})$ with
${\ker(\Pi)=\operatorname{span}\\{x_{a,1}:a\in S\\}}$, scalars
$\alpha_{1},\dots,\alpha_{n}\in\mathbb{F}$, and index $b\in[n]\setminus S$
such that

$\displaystyle\sum_{a\in[n]\setminus S}\alpha_{a}$ $\displaystyle\Pi
x_{a,1}\otimes x_{a,3}=\Pi x_{b,1}\otimes z$ (205)

for some $z\in\mathcal{V}_{\sigma(3)}$, it holds that $\omega(\alpha)\leq 1$.

  4. 4.

There exists a permutation $\tau\in S_{n}$ for which the matrix

$\displaystyle X_{1}^{\tau}=(x_{\tau(1),1},\dots,x_{\tau(n),n})$ (206)

has reduced row echelon form

$\displaystyle Y=\left[\begin{array}[]{@{}c | c@{}}\begin{matrix}1&&\\\ &\ddots&\\\ &&1\end{matrix}&\begin{matrix}&&\\\ &{\Huge Z}&\\\ &&\end{matrix}\end{array}\right],$ (208)

where $Z\in\mathrm{L}(\mathbb{F}^{n-d_{1}},\mathbb{F}^{d_{1}})$ and the blank
entries are zero. Furthermore, for each $a\in[d_{1}-1]$, the columns of the
submatrix of $Y$ with row index $\\{a,a+1,\dots,d_{1}\\}$ and column index
$\\{a,a+1,\dots,n\\}$ have k-rank at least two.

  5. 5.

$k_{1}=d_{1}.$

  6. 6.

For all $\alpha\in\mathbb{F}^{n}$,

$\displaystyle\mathrm{rank}\Big{[}\sum_{a\in[n]}\alpha_{a}x_{a,2}\otimes
x_{a,3}\Big{]}\geq\min\\{\omega(\alpha),n-k_{1}+2\\}.$ (209)

(Note that this is a stronger statement than Condition U, as it replaces the
quantity ${n-d_{1}+2}$ with the possibly larger quantity $n-k_{1}+2$.)

Then $\sum_{a\in[n]}x_{a}$ constitutes a unique tensor rank decomposition.

For each $i\in[5]$, we will refer to Theorem 36.i as the statement that
Condition U and the $i$-th condition appearing in Theorem 36 imply uniqueness.
Theorems 36.1 and 36.2 are Corollary 1.23 and Proposition 1.26 in [DL13b,
DL14]. The Condition C version of Theorem 36.3 is stated in Theorem 2.2 in
[SDL15], although the proof is contained in [DL13a, DL13b, SL15]. Condition 3b
in Theorem 36 can be formulated as checking the rank of a certain matrix (see
[SDL15]). Theorem 36.4 is a new result that we will prove (see Proposition 37
for a coordinate-free statement). The Condition C version of Theorems 36.5 and
36.6 are Theorems 1.6 and 1.7 in [DL14]. It is easy to see that our Theorem
36.4 contains Theorem 36.5, which in turn contains Theorem 36.6, by the
arguments used in [DL14].

Most of these statements have previously only been formulated for
$\mathbb{F}=\real$ or $\mathbb{F}=\mathbb{C}$, however in all of these cases
the proof can be adapted to hold over an arbitrary field. The first step in
proving all of these statements is to show that Condition U implies uniqueness
in the first subsystem. This is Proposition 4.3 in [DL13a], and it is proven
using Kruskal’s permutation lemma [Kru77] (the proof of the permutation lemma
in [Lan12] holds word-for-word over an arbitrary field). In fact, uniqueness
in the first subsystem holds even with the assumption $k_{1}\geq 2$ removed
from Condition U [DL13a].

A less-restrictive condition than Condition U, which we would call Condition
W, also appears in [DL13a, DL13b], and is the same as Condition U except that
it only requires (191) to hold when ${\alpha=(f(x_{1,1}),\dots,f(x_{n,1}))}$
for some linear functional $f\in\mathcal{V}_{1}^{*}$. We note that Theorem 36
also holds with Condition U replaced by Condition W. Although the Condition W
version of Theorem 36 is slightly stronger than the Condition U version, we
are not aware of an efficient algorithm to check either Condition U or
Condition W, and the existence of such an algorithm seems unlikely.

We conclude this subsection by proving Theorem 36.4. For this we require the
following proposition, which restates Condition 4 in a coordinate-free manner.

######  Proposition 37.

Condition 4 in Theorem 36 holds if and only if there exists a permutation
$\tau\in S_{n}$ such that for each $a\in[d_{1}-1]$ there is a linear operator
$\Pi_{a}\in\mathrm{L}(\mathcal{V}_{1})$ for which

$\displaystyle\Pi_{a}(x_{\tau(b),1})=0$ (210)

for all $b\in[a-1]$, and

$\displaystyle\operatorname{k-rank}(\Pi_{a}x_{\tau(a),1},\dots,\Pi_{a}x_{\tau(n),1})\geq
2.$ (211)

###### Proof.

Assume without loss of generality that $\mathcal{V}_{1}=\mathbb{F}^{d_{1}}$.
To see that the first statement implies the second, for each $a\in[d_{1}-1]$
let $\Pi_{a}=D_{a}P$, where $P\in\mathrm{L}(\mathbb{F}^{d_{1}})$ is the
invertible matrix for which $PX_{1}^{\tau}=Y$, and
$D_{a}\in\mathrm{L}(\mathbb{F}^{d_{1}})$ is the diagonal matrix with the first
$a-1$ entries zero and the remaining entries $1$. It is easy to verify that
(211) holds.

Conversely, suppose that the reduced row echelon form of $X_{1}^{\tau}$, given
by $PX_{1}^{\tau}$ for some invertible matrix
$P\in\mathrm{L}(\mathbb{F}^{d_{1}})$, does not have the specified form. Then
there exists ${a\in[d_{1}-1]}$ for which the columns of $D_{a}PX_{1}^{\tau}$
have k-rank at most one. Any matrix $\Pi_{a}\in\mathrm{L}(\mathbb{F}^{d_{1}})$
for which $\Pi_{a}(x_{\tau(b),1})=0$ for all $b\in[a-1]$ satisfies

$\displaystyle\Pi_{a}=\Pi_{a}P^{-1}D_{a}P.$ (212)

Since the k-rank is non-increasing under matrix multiplication from the left,
(211) does not hold. ∎

With Proposition 37 in hand, we can now prove Theorem 36.4.

###### Proof of Theorem 36.4.

The question of whether or not the decomposition $\sum_{a\in[n]}x_{a}$
constitutes a unique tensor rank decomposition is invariant under permutations
$\tau\in S_{n}$ of the tensors, so it suffices to prove the statement under
the assumption that the permutation $\tau$ appearing in Condition 4 is
trivial. We prove the statement by induction on $d_{1}$. If $d_{1}=2$, then
Condition U implies $k_{2}=k_{3}=n$, so uniqueness follows from Kruskal’s
theorem. For $d_{1}>2$, suppose $\sum_{a\in[n]}x_{a}=\sum_{a\in[r]}y_{a}$ for
some non-negative integer $r\leq n$ and multiset of product tensors

$\displaystyle\\{y_{a}:a\in[r]\\}\subseteq\mathrm{Prod}\left(\mathcal{V}_{1}:\mathcal{V}_{2}:\mathcal{V}_{3}\right).$
(213)

By Proposition 4.3 in [DL13a] (or rather, the extension of this result to an
arbitrary field), $r=n$, and there exists a permutation $\sigma\in S_{n}$ and
nonegative integers $\alpha_{1},\dots,\alpha_{n}\in\mathbb{F}^{\times}$ such
that $\alpha_{a}x_{a,1}=y_{\sigma(a),1}$ for all $a\in[n]$. Let
$\Pi_{1}\in\mathrm{L}(\mathcal{V}_{1})$ be any operator for which
${\ker(\Pi_{1})=\operatorname{span}\\{x_{a,1}\\}}$ and (211) holds (recall
that $\tau$ is trivial). Then

$\displaystyle\sum_{a\in[n]\setminus\\{1\\}}(\Pi_{1}x_{a,1})\otimes
x_{a,2}\otimes
x_{a,3}=\sum_{a\in[n]\setminus\\{1\\}}(\alpha_{a}\Pi_{1}x_{a,1})\otimes
y_{\sigma(a),2}\otimes y_{\sigma(a),3}.$ (214)

Now,
$\dim\operatorname{span}\\{\Pi_{1}x_{a,1}:a\in[n]\setminus\\{1\\}\\}=d_{1}-1$,
and Condition U again holds for the multiset of product tensors

$\displaystyle\\{(\Pi_{1}x_{a,1})\otimes x_{a,2}\otimes
x_{a,3}:a\in[n]\setminus\\{1\\}\\}.$ (215)

Furthermore, these product tensors again satisfy Condition 4 of Theorem 36, so
by the induction hypothesis

$\displaystyle(\Pi_{1}x_{a,1})\otimes x_{a,2}\otimes
x_{a,3}=(\alpha_{a}\Pi_{1}x_{a,1})\otimes y_{\sigma(a),2}\otimes
y_{\sigma(a),3}\quad\text{for all}\quad a\in[n]\setminus\\{1\\}.$ (216)

It follows that $x_{a}=y_{\sigma(a)}$ for all $a\in[n]\setminus\\{1\\}$, so
$x_{1}=y_{\sigma(1)}$. This completes the proof. ∎

###  10.3 Conjectural generalization of all uniqueness criteria of DLS

In the case of three subsystems, our generalization of Kruskal’s theorem
states that Condition S implies uniqueness. Since Condition H $\Rightarrow$
Condition S, then a corollary to Theorem 2 is that Condition H implies
uniqueness. Similarly, Theorem 36 above states that Condition U + extra
assumptions implies uniqueness, which implies that Condition H + the same
extra assumptions implies uniqueness. Since we have proven that Condition H
alone implies uniqueness, it is natural to ask whether Condition U alone
implies uniqueness. We now state this question formally. A positive answer to
Question 38 would generalize and unify all of the uniqueness criteria of DLS
(synthesized in Theorem 36) into a single, elegant statement.

######  Question 38.

Does Condition U imply that $\sum_{a\in[n]}x_{a}$ constitutes a unique tensor
rank decomposition?

##  11 Appendix

In this appendix we prove Theorem 27. The proof is very similar to that of
Theorem 22.

###### Proof of Theorem 27.

For each $a\in[r]$, let $x_{n+a}=-y_{a}$, and let $T_{1}\sqcup\dots\sqcup
T_{t}=[n+r]$ be the index sets of the decomposition of $\\{x_{a}:a\in[n+r]\\}$
into connected components. Note that for each $p\in[t]$, if

$\displaystyle\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}\leq\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert},$
(217)

then $\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\leq s$, otherwise $\\{x_{a}:a\in
T_{p}\\}$ would split. Assume without loss of generality that

$\displaystyle\bigl{\lvert}T_{1}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{1}\cap[n+r]\setminus[n]\bigr{\rvert}$
$\displaystyle\geq\bigl{\lvert}T_{2}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{2}\cap[n+r]\setminus[n]\bigr{\rvert}$
(218) $\displaystyle\;\;\vdots$ (219)
$\displaystyle\geq\bigl{\lvert}T_{{t}}\cap[n]\bigr{\rvert}-\bigl{\lvert}T_{{t}}\cap[n+r]\setminus[n]\bigr{\rvert},$
(220)

If

$\displaystyle\bigl{\lvert}T_{1}\cap[n]\bigr{\rvert}\geq\bigl{\lvert}T_{1}\cap[n+r]\setminus[n]\bigr{\rvert},$
(221)

then let $\tilde{l}\in[t]$ be the largest integer for which

$\displaystyle\bigl{\lvert}T_{\tilde{l}}\cap[n]\bigr{\rvert}\geq\bigl{\lvert}T_{\tilde{l}}\cap[n+r]\setminus[n]\bigr{\rvert}.$
(222)

Otherwise, let $\tilde{l}=0$. Then for all $p\in[t]\setminus[\tilde{l}]$ it
holds that

$\displaystyle\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}<\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}.$
(223)

To complete the proof, we will show that $\tilde{l}\geq l$, for then we can
take $Q_{p}=T_{p}\cap[n]$ and $R_{p}=T_{p}\cap[n+r]\setminus[n]$ for all
$p\in[l]$ to conclude.

Suppose toward contradiction that $\tilde{l}<l$. We will require the following
two claims:

######  Claim 39.

It holds that $\tilde{l}<t$,
$\bigl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\bigr{\rceil}\geq s+1$, and
there exists $p\in[t]\setminus[\tilde{l}]$ for which

$\displaystyle\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\geq\biggl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\biggr{\rceil}.$
(224)

######  Claim 40.

For all $p\in[t]\setminus[\tilde{l}]$, it holds that

$\displaystyle\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}\leq\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+(r-n)+(s+1)\tilde{l}-t+1.$
(225)

Before proving these claims, we first use them to complete the proof of the
theorem. Let $p\in[t]\setminus[\tilde{l}]$ be as in Claim 39. Then,

$\displaystyle\lvert T_{p}\rvert$
$\displaystyle=\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}$
(226) $\displaystyle\leq
2\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+r-n+(s+1)\tilde{l}-t+1$ (227)
$\displaystyle\leq
2\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+r-n+s\tilde{l}-\biggl{\lceil}\frac{n-s\tilde{l}}{\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}}\biggr{\rceil}+1$
(228) $\displaystyle\leq
2\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+(r-n+q-s)-\biggl{\lceil}\frac{n-q+s}{\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}}\biggr{\rceil}+1$
(229) $\displaystyle\leq\sum_{j=1}^{m}(d_{j}^{T_{p}\cap[n]}-1)+1,$ (230)

where the first line is obvious, the second follows from Claim 40, the third
follows from Claim 39, the fourth follows from $\tilde{l}<l$, and the fifth
follows from the assumptions of the theorem and the fact that $\lvert
T_{p}\cap[n]\rvert\geq s+1$. So $\\{x_{a}:a\in T_{p}\\}$ splits, a
contradiction. This completes the proof, modulo proving the claims.

###### Proof of Claim 23.

To prove the claim, we first observe that $n>st$. Indeed, if $n\leq st$, then

$\displaystyle r$
$\displaystyle\geq\sum_{p=\tilde{l}+1}^{t}\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}$
(231)
$\displaystyle\geq\sum_{p=\tilde{l}+1}^{t}\left(\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+1\right)$
(232) $\displaystyle=n-\bigl{\lvert}(T_{1}\sqcup\dots\sqcup
T_{\tilde{l}})\cap[n]\bigr{\rvert}+t-\tilde{l}$ (233) $\displaystyle\geq
n+t-(s+1)\tilde{l}$ (234) $\displaystyle\geq
n+\biggl{\lceil}\frac{n}{s}-(s+1)(q/s-1)\biggr{\rceil}$ (235)
$\displaystyle=\biggl{\lceil}\left(\frac{s+1}{s}\right)(n-q+s)\biggr{\rceil},$
(236)

where the first line is obvious, the second follows from (90), the third is
obvious, the fourth follows from $\lvert T_{p}\cap[n]\rvert\leq s$ for all
$p\in[\tilde{l}]$, the fifth follows from $n\leq st$ and $\tilde{l}<l$, and
the sixth is algebra. This contradicts the assumptions of the theorem, so it
must hold that $n>st$.

Note that $\tilde{l}<t$, for otherwise we would have $n\leq st$ by the fact
that $\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\leq s$ for all $p\in[\tilde{l}]$.
To verify that $\bigl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\bigr{\rceil}\geq
s+1$, it suffices to prove $\frac{n-s\tilde{l}}{t-\tilde{l}}>s,$ which follows
from $n>st$. To verify (224), since $\lvert T_{p}\cap[n]\rvert\leq s$ for all
$p\in[\tilde{l}]$, by the pigeonhole principle there exists
$p\in[t]\setminus[\tilde{l}]$ for which

$\displaystyle\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}\geq\biggl{\lceil}\frac{n-s\tilde{l}}{t-\tilde{l}}\biggr{\rceil}.$
(238)

This proves the claim. ∎

###### Proof of Claim 40.

Suppose toward contradiction that the inequality (225) does not hold for some
$\tilde{p}\in[t]\setminus[\tilde{l}]$. Then

$\displaystyle r$
$\displaystyle\geq\sum_{p=\tilde{l}+1}^{t}\bigl{\lvert}T_{p}\cap[n+r]\setminus[n]\bigr{\rvert}$
(239)
$\displaystyle\geq\sum_{p\neq\tilde{p}}\big{(}\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+1\big{)}+\bigl{\lvert}T_{\tilde{p}}\cap[n]\bigr{\rvert}+(r-n)+(s+1)\tilde{l}-t+2$
(240)
$\displaystyle=\sum_{p=\tilde{l}+1}^{t}\bigl{\lvert}T_{p}\cap[n]\bigr{\rvert}+(r-n)+s\tilde{l}+1$
(241) $\displaystyle\geq r+1,$ (242)

where the first three lines are obvious, and the fourth follows from (222), a
contradiction. ∎

The proofs of Claims 39 and 40 complete the proof of the theorem. ∎

## References

  * [Bal20] Edoardo Ballico.  Linearly dependent and concise subsets of a Segre variety depending on k factors.  arXiv preprint, math.AG/2002.09720, 2020.
  * [BBCG18] Edoardo Ballico, Alessandra Bernardi, Luca Chiantini, and Elena Guardo.  Bounds on the tensor rank.  Annali di Matematica Pura ed Applicata (1923 -), 197(6):1771–1785, 2018.
  * [BCMV14] Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan.  Open problem: Tensor decompositions: Algorithms up to the uniqueness threshold?  In Conference on Learning Theory, pages 1280–1282. Proceedings of Machine Learning Research, 2014.
  * [BCV14] Aditya Bhaskara, Moses Charikar, and Aravindan Vijayaraghavan.  Uniqueness of tensor decompositions with applications to polynomial identifiability.  In Conference on Learning Theory, pages 742–778. Proceedings of Machine Learning Research, 2014.
  * [BLM17] Michel Boyer, Rotem Liss, and Tal Mor.  Geometry of entanglement in the Bloch sphere.  Physical Review A, 95:032308, 2017.