TAOCP 4.6.4 Exercise 45

Let ${t_{ijk}}$ be an $m \times n \times s$ tensor of rank $r$, meaning that there exist vectors $a^{(p)} \in \mathbb{R}^m$, $b^{(p)} \in \mathbb{R}^n$, $c^{(p)} \in \mathbb{R}^s$ for $p = 1, \ldots,...

taocpmathematicsalgorithmsvolume-2hm-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 45. ▶ [HM22] Let ${t_{ijk}}$ be an $m \times n \times s$ tensor, and let $F$, $G$, $H$ be nonsingular matrices of respective sizes $m \times m$, $n \times n$, $s \times s$. If

$$T'{ijk} = \sum{i'=1}^{m} \sum_{j'=1}^{n} \sum_{k'=1}^{s} F_{ii'} G_{jj'} H_{kk'} t_{i'j'k'}$$

for all $i$, $j$, $k$, prove that the tensor ${T'{ijk}}$ has the same rank as ${t{ijk}}$. [Hint: Consider what happens when $F^{-1}$, $G^{-1}$, $H^{-1}$ are applied in the same way to ${T'_{ijk}}$.]

Verified: yes
Solve time: 7m06s

Solution

Let ${t_{ijk}}$ be an $m \times n \times s$ tensor of rank $r$, meaning that there exist vectors $a^{(p)} \in \mathbb{R}^m$, $b^{(p)} \in \mathbb{R}^n$, $c^{(p)} \in \mathbb{R}^s$ for $p = 1, \ldots, r$ such that

$$ t_{ijk} = \sum_{p=1}^{r} a^{(p)}_i b^{(p)}_j c^{(p)}_k $$

and no representation with fewer than $r$ terms exists.

Define the transformed tensor

$$ T'{ijk} = \sum{i'=1}^{m} \sum_{j'=1}^{n} \sum_{k'=1}^{s} F_{ii'} G_{jj'} H_{kk'} t_{i'j'k'}. $$

Substituting the rank-$r$ decomposition of $t_{ijk}$ into this formula yields

\begin{align*}

T'{ijk} &= \sum{i'=1}^{m} \sum_{j'=1}^{n} \sum_{k'=1}^{s} F_{ii'} G_{jj'} H_{kk'} \sum_{p=1}^{r} a^{(p)}{i'} b^{(p)}{j'} c^{(p)}_{k'} \

&= \sum_{p=1}^{r} \sum_{i'=1}^{m} \sum_{j'=1}^{n} \sum_{k'=1}^{s} F_{ii'} a^{(p)}{i'} , G{jj'} b^{(p)}{j'} , H{kk'} c^{(p)}_{k'} \

&= \sum_{p=1}^{r} \left(\sum_{i'=1}^{m} F_{ii'} a^{(p)}{i'} \right) \left(\sum{j'=1}^{n} G_{jj'} b^{(p)}{j'} \right) \left(\sum{k'=1}^{s} H_{kk'} c^{(p)}_{k'} \right) \

&= \sum_{p=1}^{r} \tilde{a}^{(p)}_i , \tilde{b}^{(p)}_j , \tilde{c}^{(p)}_k,

\end{align*}

where we have defined the transformed vectors

$$ \tilde{a}^{(p)} = F a^{(p)}, \qquad \tilde{b}^{(p)} = G b^{(p)}, \qquad \tilde{c}^{(p)} = H c^{(p)}. $$

Since $F$, $G$, and $H$ are nonsingular, each transformation is invertible. Therefore, if a representation of ${T'_{ijk}}$ with fewer than $r$ terms existed, say

$$ T'{ijk} = \sum{p=1}^{r'} \hat{a}^{(p)}_i \hat{b}^{(p)}_j \hat{c}^{(p)}_k, \qquad r' < r, $$

then applying the inverses $F^{-1}$, $G^{-1}$, $H^{-1}$ would produce a decomposition of ${t_{ijk}}$ with $r'$ terms:

$$ t_{ijk} = \sum_{p=1}^{r'} (F^{-1}\hat{a}^{(p)})_i (G^{-1}\hat{b}^{(p)})_j (H^{-1}\hat{c}^{(p)})_k, $$

contradicting the minimality of $r$. Hence no representation of ${T'_{ijk}}$ with fewer than $r$ terms exists.

Conversely, the decomposition above shows that ${T'{ijk}}$ has a representation with exactly $r$ terms, so its rank is at most $r$. Combining these two observations, we conclude that $\operatorname{rank}({T'{ijk}}) = \operatorname{rank}({t_{ijk}}) = r$.

This completes the proof.

∎