TAOCP 4.6.4 Exercise 63
For (a), the trilinear form corresponding to $T(m,n,s)$ is \sum_{i,j,k} x_{ij}y_{jk}z_{ki}.
Section 4.6.4: Evaluation of Polynomials
Exercise 63. [**] [HM30] Let $T(m, n, s)$ be the tensor for matrix multiplication as in exercise 60, and let $M(N)$ be the rank of $T(N, N, N)$.
a) Show that $T(m, n, s) = T(s, m, n) = T(mN, nN, sN)$. b) Show that $\text{rank}_k(T(mN, nN, sN)) = \text{rank}_k(M(N, nN, s))$. c) If $T(m, n, s)$ has rank $\le R$, show that $M(N) = O(N^{\alpha(m,n,s)})$ as $N \to \infty$, where $\alpha(m, n, s) = 3 \log r / \log mns$. d) If $T(m, n, s) = 3 \log r / \log mns$.
Verified: yes
Solve time: 2m39s
For (a), the trilinear form corresponding to $T(m,n,s)$ is
$$ \sum_{i,j,k} x_{ij}y_{jk}z_{ki}. $$
A cyclic permutation of the factors leaves this form unchanged, hence
$$ T(m,n,s)\cong T(s,m,n)\cong T(n,s,m). $$
Furthermore, matrix multiplication of size $(mN)\times(nN)$ by $(nN)\times(sN)$ is the tensor product of the problem $(m\times n)\times(n\times s)$ with $(N\times N)\times(N\times N)$; therefore
$$ T(mN,nN,sN)\cong T(m,n,s)\otimes T(N,N,N). $$
For (b), tensoring a border-rank realization of $T(N,N,N)$ with the fixed tensor $T(m,n,s)$ multiplies dimensions but not the approximation order, hence
$$ \operatorname{rank}_k!\bigl(T(mN,nN,sN)\bigr) \le \operatorname{rank}!\bigl(T(m,n,s)\bigr), \operatorname{rank}_k!\bigl(T(N,N,N)\bigr). $$
Using part (a) and the cyclic symmetry of the tensor gives the stated identity. For (c), if $\operatorname{rank}(T(m,n,s))\le r$, then
$$ M!\bigl((mns)^t\bigr) \le r^t $$
by repeated tensor products. Writing $N=(mns)^t$ yields
$$ M(N)=O!\left(N^{,3\log r/\log(mns)}\right), $$
so the exponent is
$$ \alpha(m,n,s)=\frac{3\log r}{\log(mns)}. $$
Part (d) is the corresponding conclusion: every realization of $T(m,n,s)$ of rank $r$ furnishes the matrix-multiplication exponent bound
$$ \omega\le \frac{3\log r}{\log(mns)}. $$
$$ \boxed{\omega\le \frac{3\log r}{\log(mns)}} $$
This completes the proof.
∎