TAOCP 4.6.4 Exercise 48

Let t_{ijk}=\sum_{\alpha=1}^{r} a_{\alpha i} b_{\alpha j} c_{\alpha k}, \qquad t'_{i'j'k'}=\sum_{\beta=1}^{r'} a'_{\beta i'} b'_{\beta j'} c'_{\beta k'},

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 48. [M21] If ${t_{ijk}}$ and ${t'{ijk}}$ are tensors of sizes $m \times n \times s$ and $m' \times n' \times s'$, respectively, their direct sum ${t{ijk}} \oplus {t'{ijk}} = {t''{ijk}}$ is the $(m + m') \times (n + n') \times (s + s')$ tensor defined by $t''{ijk} = t{ijk}$ if $i \le m$, $j \le n$, $k \le s$; $t''{ijk} = t'{i-m,j-n,k-s}$ if $i > m$, $j > n$, $k > s$; and $t''{ijk} = 0$ otherwise. Their direct product ${t{ijk}} \otimes {t'{ijk}} = {t''{ijk}}$ is the $mm' \times nn' \times ss'$ tensor defined by $t''{(i,i')(j,j')(k,k')} = t{ijk} t'{i'j'k'}$. Prove the upper bounds $\text{rank}(t''{ijk}) \le \text{rank}(t_{ijk}) + \text{rank}(t'{ijk})$ and $\text{rank}(t''{ijk}) \le \text{rank}(t_{ijk}) \cdot \text{rank}(t'_{ijk})$.

Verified: yes
Solve time: 5m03s

Solution

Let

$$ t_{ijk}=\sum_{\alpha=1}^{r} a_{\alpha i} b_{\alpha j} c_{\alpha k}, \qquad t'{i'j'k'}=\sum{\beta=1}^{r'} a'{\beta i'} b'{\beta j'} c'_{\beta k'}, $$

where

$$ r=\operatorname{rank}(t_{ijk}), \qquad r'=\operatorname{rank}(t'_{i'j'k'}). $$

Thus $r$ and $r'$ are the minimum numbers of simple tensors needed to represent $t$ and $t'$.

We first consider the direct sum.

Define vectors of lengths $m+m'$, $n+n'$, and $s+s'$ by

$$ A_{\alpha i}= \begin{cases} a_{\alpha i}, & i\le m,\ 0, & i>m, \end{cases} \qquad B_{\alpha j}= \begin{cases} b_{\alpha j}, & j\le n,\ 0, & j>n, \end{cases} \qquad C_{\alpha k}= \begin{cases} c_{\alpha k}, & k\le s,\ 0, & k>s, \end{cases} $$

for $1\le\alpha\le r$, and

$$ A'{\beta i}= \begin{cases} 0, & i\le m,\ a'{\beta,i-m}, & i>m, \end{cases} $$

with analogous definitions for $B'{\beta j}$ and $C'{\beta k}$.

Then

$$ \sum_{\alpha=1}^{r} A_{\alpha i}B_{\alpha j}C_{\alpha k} + \sum_{\beta=1}^{r'} A'{\beta i}B'{\beta j}C'_{\beta k} $$

equals $t_{ijk}$ in the first block, equals $t'_{i-m,j-n,k-s}$ in the second block, and vanishes whenever the indices are not simultaneously in one block or the other. Hence this tensor is exactly $t\oplus t'$.

Therefore $t\oplus t'$ has been expressed as a sum of $r+r'$ simple tensors, so

$$ \operatorname{rank}(t\oplus t') \le r+r' = \operatorname{rank}(t)+\operatorname{rank}(t'). $$

Next consider the direct product.

Using the rank decompositions above,

$$ t''{(i,i')(j,j')(k,k')} = t{ijk},t'{i'j'k'} = \left( \sum{\alpha=1}^{r} a_{\alpha i}b_{\alpha j}c_{\alpha k} \right) \left( \sum_{\beta=1}^{r'} a'{\beta i'}b'{\beta j'}c'_{\beta k'} \right). $$

Expanding,

$$ t''{(i,i')(j,j')(k,k')} = \sum{\alpha=1}^{r} \sum_{\beta=1}^{r'} \bigl(a_{\alpha i}a'{\beta i'}\bigr) \bigl(b{\alpha j}b'{\beta j'}\bigr) \bigl(c{\alpha k}c'_{\beta k'}\bigr). $$

Each summand is a simple tensor on the index sets

$(i,i')$, $(j,j')$, and $(k,k')$. Thus $t\otimes t'$ is represented as a sum of exactly $rr'$ simple tensors.

Consequently,

$$ \operatorname{rank}(t\otimes t') \le rr' = \operatorname{rank}(t)\operatorname{rank}(t'). $$

Hence

$$ \boxed{\operatorname{rank}(t\oplus t') \le \operatorname{rank}(t)+\operatorname{rank}(t')} $$

and

$$ \boxed{\operatorname{rank}(t\otimes t') \le \operatorname{rank}(t)\operatorname{rank}(t')}. $$

This completes the proof.

∎