TAOCP 4.6.4 Exercise 61
\text{Let } r_k(T)=\operatorname{rank}_k(T).
Section 4.6.4: Evaluation of Polynomials
Exercise 61. [**] [M26] Let $(t_{ijk})$ be a tensor over an arbitrary field. We define $\text{rank}0(t{ijk})$ as the minimum value of $r$ such that there is a realization of the form
$$\sum_{s=1}^{r} a_s(u) b_s(v) c_s(w) \epsilon_{ijk}(u) = t_{ijk} u^v + O(u^{v+1}),$$
where $a_s(u)$, $b_s(u)$, $c_s(u)$ are polynomials in $u$ over the field. Thus $\text{rank}_0$ is the ordinary rank of a tensor. Prove that
a) $\text{rank}{k+1}(t{ijk}) \le \text{rank}k(t{ijk})$; b) $\text{rank}(t_{ijk}) \le \binom{n+2}{2} \cdot \text{rank}k(t{ijk})$; c) $\text{rank}(t_{ijk} \oplus t'{ijk}) \le \text{rank}k(t{ijk}) + \text{rank}k(t'{ijk})$, in the sense of exercise 48; d) $\text{rank}{k+1}((t_{ijk}) \otimes (t'{ijk})) \le \text{rank}k(t{ijk}) \cdot \text{rank}k(t'{ijk})$; e) $\text{rank}{2T}((t_{ijk}) \otimes (t'_{ijk})) \le \text{rank}T(t{ijk})$, where $r = \text{rank}T(t{ijk})$ and $rT$ denotes the direct sum $T \oplus \cdots \oplus T$ of $r$ copies of $T$.
Verified: no
Solve time: 6m11s
$$ \text{Let } r_k(T)=\operatorname{rank}_k(T). $$
By definition, $r_k(T)$ is the least $r$ for which there exist vector-valued polynomials
$$ a_s(u),\quad b_s(u),\quad c_s(u)\qquad (1\le s\le r) $$
such that
$$ \sum_{s=1}^{r}a_s(u)b_s(u)c_s(u) =u^kT+O(u^{k+1}). $$
Here $a_s(u)b_s(u)c_s(u)$ denotes a rank-$1$ tensor.
We prove the stated properties.
a) $\operatorname{rank}_{k+1}(T)\le \operatorname{rank}_k(T)$
Let $r=r_k(T)$. Then there is a realization
$$ \sum_{s=1}^{r}a_s(u)b_s(u)c_s(u) =u^kT+O(u^{k+1}). $$
Multiplying both sides by $u$ gives
$$ \sum_{s=1}^{r}(ua_s(u)),b_s(u),c_s(u) =u^{k+1}T+O(u^{k+2}). $$
Hence the same number $r$ of rank-$1$ terms yields a realization of order $k+1$. Therefore
$$ r_{k+1}(T)\le r_k(T). $$
b) $\operatorname{rank}(T)\le \binom{k+2}{2},r_k(T)$
Let $r=r_k(T)$, and write
$$ \sum_{s=1}^{r}a_s(u)b_s(u)c_s(u) =u^kT+O(u^{k+1}). $$
Expand
$$ a_s(u)=\sum_{i\ge0}a_{s,i}u^i,\qquad b_s(u)=\sum_{j\ge0}b_{s,j}u^j,\qquad c_s(u)=\sum_{\ell\ge0}c_{s,\ell}u^\ell . $$
The coefficient of $u^k$ on the left is
$$ \sum_{s=1}^{r} \sum_{i+j+\ell=k} a_{s,i},b_{s,j},c_{s,\ell}. $$
Since the coefficient of $u^k$ is precisely $T$,
$$ T= \sum_{s=1}^{r} \sum_{i+j+\ell=k} a_{s,i},b_{s,j},c_{s,\ell}. $$
Each summand is a rank-$1$ tensor. The number of triples
$(i,j,\ell)$ of nonnegative integers satisfying $i+j+\ell=k$ is
$$ \binom{k+2}{2}. $$
Therefore $T$ is expressed as a sum of at most
$$ r\binom{k+2}{2} $$
rank-$1$ tensors. Hence
$$ \operatorname{rank}(T) \le \binom{k+2}{2},r_k(T). $$
c) (\operatorname{rank}_k(T\oplus T')
\le r_k(T)+r_k(T'))
Let
$$ r=r_k(T),\qquad r'=r_k(T'). $$
Choose realizations
$$ \sum_{s=1}^{r}a_s(u)b_s(u)c_s(u) =u^kT+O(u^{k+1}), $$
$$ \sum_{t=1}^{r'}a'_t(u)b'_t(u)c'_t(u) =u^kT'+O(u^{k+1}). $$
Embed the first family in the coordinates of $T$ and the second in the
coordinates of $T'$. Then
$$ \sum_{s=1}^{r} (a_s\oplus0)(b_s\oplus0)(c_s\oplus0) + \sum_{t=1}^{r'} (0\oplus a'_t)(0\oplus b'_t)(0\oplus c'_t) = u^k(T\oplus T') +O(u^{k+1}). $$
This realization uses $r+r'$ rank-$1$ terms. Thus
$$ r_k(T\oplus T') \le r_k(T)+r_k(T'). $$
d) (\operatorname{rank}_{k+1}(T\otimes T')
\le r_k(T),r_k(T'))
Let
$$ r=r_k(T),\qquad r'=r_k(T'). $$
Choose realizations
$$ A(u):=\sum_{s=1}^{r}a_s(u)b_s(u)c_s(u) =u^kT+O(u^{k+1}), $$
$$ B(u):=\sum_{t=1}^{r'}a'_t(u)b'_t(u)c'_t(u) =u^kT'+O(u^{k+1}). $$
Then
$$ A(u)\otimes B(u) = u^{2k}(T\otimes T') + O(u^{2k+1}). $$
But
$$ A(u)\otimes B(u) = \sum_{s=1}^{r} \sum_{t=1}^{r'} (a_s\otimes a'_t) (b_s\otimes b'_t) (c_s\otimes c'_t), $$
a sum of $rr'$ rank-$1$ tensors. Hence there is a realization of
$T\otimes T'$ of order $2k$ with $rr'$ terms, and therefore
$$ r_{2k}(T\otimes T') \le rr'. $$
Applying part (a),
$$ r_{k+1}(T\otimes T') \le r_{2k}(T\otimes T') \le rr' =r_k(T),r_k(T'). $$
e) (\operatorname{rank}_{2T}(T\otimes T)
\le \operatorname{rank}_T(T))
Let
$$ r=r_T(T). $$
Choose a realization
$$ \sum_{s=1}^{r}a_s(u)b_s(u)c_s(u) = u^T T+O(u^{T+1}). $$
Let
$$ X_s(u)=a_s(u)b_s(u)c_s(u). $$
Then
$$ \sum_{s=1}^{r}X_s(u) = u^T T+O(u^{T+1}). $$
Tensoring this identity with itself gives
$$ \sum_{s,t=1}^{r}X_s(u)\otimes X_t(u) = u^{2T}(T\otimes T)+O(u^{2T+1}). $$
Now regard the left-hand side as a direct sum of $r$ groups indexed by
$s$:
$$ \sum_{s=1}^{r} X_s(u)\otimes \Bigl(\sum_{t=1}^{r}X_t(u)\Bigr). $$
Using
$$ \sum_{t=1}^{r}X_t(u) = u^T T+O(u^{T+1}), $$
we obtain
$$ X_s(u)\otimes \Bigl(\sum_{t=1}^{r}X_t(u)\Bigr) = u^{2T}\bigl(X_{s,T}\otimes T\bigr) +O(u^{2T+1}), $$
where $X_{s,T}$ denotes the coefficient of $u^T$ in $X_s(u)$.
Each term on the left is rank $1$, because it is the tensor product of
three vectors
$$ a_s(u)\otimes\Bigl(\sum_t a_t(u)\Bigr),\qquad b_s(u)\otimes\Bigl(\sum_t b_t(u)\Bigr),\qquad c_s(u)\otimes\Bigl(\sum_t c_t(u)\Bigr). $$
Therefore
$$ u^{2T}(T\otimes T)+O(u^{2T+1}) $$
is represented as a sum of only $r$ rank-$1$ tensors. Hence
$$ r_{2T}(T\otimes T)\le r. $$
Since $r=r_T(T)$,
$$ \boxed{\operatorname{rank}_{2T}(T\otimes T)\le \operatorname{rank}_T(T)}. $$
This is the desired inequality. ∎