# Upper bound CP tensor rank

I have a question about CP tensor ranks. In the following, $$\mathcal X \in \mathbb R^{n_1 \times n_2 \times n_3}$$ is a third-order tensor of CP rank $$R$$, i.e., there exist vectors $$a_i$$, $$b_i$$ and $$c_i$$ for $$i = 1, \ldots, R$$ of appropriate dimensions such that $$\mathrm{vec}(\mathcal X) = c_1 \otimes b_1 \otimes a_1 + \ldots + c_R \otimes b_R \otimes a_R.$$

The following theorem holds.

Theorem. Let $$R_\mu$$ be the rank of the matricization $$X^{(\mu)}$$ of $$\mathcal X$$ for $$\mu = 1, 2, 3$$. Then $$\max\{R_1,R_2, R_3\} \leq R \leq \min\{R_1R_2, R_1R_3, R_2R_3\}.$$

While I have no issues with the lower bound (i.e., left), I can neither prove nor find a reference for the proof of the upper bound. I can prove that $$R \leq \min\{n_1n_2, n_1n_3, n_2n_3\}$$, but that is not enough, as $$R_\mu \leq n_\mu$$ for $$\mu = 1, 2, 3$$.

EDIT: Proof of $$R \leq \min\{n_1n_2, n_1n_3, n_2n_3\}$$

(w.l.o.g. prove $$R \leq n_1 n_2$$.) Consider $$X^{(1)} \in \mathbb R^{n_1\times n_2n_3}$$ the first matricization of $$\mathcal X$$, and write $$X^{(1)} = [x_1, \ldots, x_{n_2n_3}]$$ Then we have for the canonical basis vectors $$e_i \in \mathbb{R}^{n_2n_3}$$ $$X^{(1)} = \sum_{i = 1}^{n_2 n_3} x_i e_i^\top$$ And by vectorization $$\mathrm{vec}(\mathcal X) = \mathrm{vec}(X^{(1)}) = \sum_{i = 1}^{n_2 n_3} e_i \otimes x_i,$$ which implies that $$R \leq n_2 n_3$$ by constructing vectors $$g_i$$ and $$h_i$$ such that $$g_i \otimes h_i = e_i$$.

We first note that vectors $$c_1\otimes a_1,\ldots,c_R\otimes a_R$$ are linearly independent. Otherwise, after reordering if necessary, there would exist scalars $$\beta_1,\ldots,\beta_{R-1}$$ such that $$c_R\otimes a_R = \sum_{k=1}^{R-1}\beta_k(c_k\otimes a_k)\,.$$ Using definition and linearity of Kronecker product, this would lead to \begin{align} \operatorname{vec}(\mathcal{X}) &= \sum_{k=1}^{R-1}c_k\otimes b_k\otimes a_k + c_R\otimes b_R\otimes a_R\\ &= \sum_{k=1}^{R-1}c_k\otimes (b_k+\beta_kb_R)\otimes a_k\,, \end{align} which is in contradiction with $$\mathcal{X}$$ having CP rank $$R$$.
Said differently, matrix $$C\odot A=\begin{bmatrix}c_1\otimes a_1 & \cdots & c_R\otimes a_R\end{bmatrix},$$ where $$\odot$$ denotes Kathri-Rao product, has rank $$R$$. The second matricization of $$\mathcal{X}$$ can be written as $$X^{(2)}=B(C\odot A)^T\,.$$ Since $$C\odot A$$ is of full column rank, it follows that $$R_2=\operatorname{rank}(X^{(2)}) = \operatorname{rank}(B)\,.$$
We can repeat all of the observations above for the first and the third matricization of $$\mathcal{X}$$ to conclude $$R = \operatorname{rank}(C\odot B) = \operatorname{rank}(C\odot A) = \operatorname{rank}(B\odot A)$$ and $$R_1=\operatorname{rank}(A),\quad R_2=\operatorname{rank}(B),\quad R_3=\operatorname{rank}(C)\,.$$
Now, we have $$R = \operatorname{rank}(C\odot B) \leq \operatorname{rank}(C\otimes B) = \operatorname{rank}(B)\operatorname{rank}(C)=R_2R_3\,,$$ where inequality holds because each column of $$C\odot B$$ appears as a column of $$C\otimes B$$. Repeating this for matrices $$C\odot A$$ and $$B\odot A$$ proves the theorem.