TAOCP 4.6.4 Exercise 66
Let $M(N)=\operatorname{rank}(T(N,N,N))$, and let $\omega$ denote the exponent of matrix multiplication.
Section 4.6.4: Evaluation of Polynomials
Exercise 66. [HM35] We can now use the result of exercise 65 to sharpen the asymptotic bounds of exercise 63.
a) Prove that the limit $\omega = \lim_{n\to\infty} \log M(n)/\log n$ exists.
b) Prove that $(mns)^{\omega/3} \le \operatorname{rank}(T(m,n,s))$.
c) Let $t$ be the tensor $T(m,n,s) \oplus T(M,N,S)$. Prove that $(mns)^{\omega/3} + (MNS)^{\omega/3} \le \operatorname{rank}(t)$. Hint: Consider direct products of $t$ with itself.
d) Prove that for $m \times n$ matrix multiplication is nondegenerate.
e) Therefore $16^{\omega/3} + 9^{\omega/3} \le 17$, and we have $\omega < 2.55$.
Verified: yes
Solve time: 1m37s
Setup
Let $M(N)=\operatorname{rank}(T(N,N,N))$, and let $\omega$ denote the exponent of matrix multiplication. Exercise 65 established that
$$ \operatorname{rank}!\bigl(T(m,1,n)\oplus T(1,(m-1)(n-1),1)\bigr)=mn+1. $$
We are to prove:
- The limit
$$ \omega=\lim_{n\to\infty}\frac{\log M(n)}{\log n} $$
exists. 2. For all $m,n,s$,
$$ (mns)^{\omega/3}\le \operatorname{rank}(T(m,n,s)). $$ 3. If
$$ t=T(m,n,s)\oplus T(M,N,S), $$
then
$$ (mns)^{\omega/3}+(MNS)^{\omega/3}\le \operatorname{rank}(t). $$ 4. Matrix multiplication tensors are nondegenerate. 5. Consequently,
$$ 16^{\omega/3}+9^{\omega/3}\le17, $$
hence $\omega<2.55$.
Solution
(a) Existence of the limit
Let
$$ a_n=\log M(n). $$
Exercise 63 implies that tensor products of matrix multiplication tensors satisfy
$$ T(m,m,m)\otimes T(n,n,n)\cong T(mn,mn,mn), $$
hence
$$ M(mn)\le M(m)M(n). $$
Therefore
$$ a_{mn}\le a_m+a_n. $$
Thus $(a_n)$ is subadditive with respect to multiplication. Put
$$ b_k=a_{2^k}. $$
Then
$$ b_{k+\ell}=a_{2^{k+\ell}} \le a_{2^k}+a_{2^\ell} =b_k+b_\ell. $$
Fekete's lemma gives the existence of
$$ \lim_{k\to\infty}\frac{b_k}{k} =\inf_{k\ge1}\frac{b_k}{k}. $$
Since
$$ \frac{b_k}{k} = (\log2)\frac{\log M(2^k)}{\log(2^k)}, $$
the limit
$$ \lim_{k\to\infty} \frac{\log M(2^k)}{\log(2^k)} $$
exists.
Exercise 63(c) shows that every fixed tensor decomposition yields polynomial upper bounds for $M(N)$, hence $M(N)\le C N^\alpha$ for some constant $\alpha$. Since $M(N)$ is nondecreasing, standard interpolation between consecutive powers of $2$ implies that
$$ \lim_{N\to\infty}\frac{\log M(N)}{\log N} $$
exists and equals the dyadic limit above. Define this limit to be $\omega$.
(b) Lower bound for arbitrary matrix multiplication tensors
Let
$$ r=\operatorname{rank}(T(m,n,s)). $$
Exercise 63(c) states that a rank-$r$ realization of $T(m,n,s)$ implies
$$ M(N)=O!\left(N^{,3\log r/\log(mns)}\right). $$
Taking logarithms and dividing by $\log N$,
$$ \omega \le \frac{3\log r}{\log(mns)}. $$
Multiplying by $\log(mns)/3$ and exponentiating yields
$$ (mns)^{\omega/3}\le r. $$
Since $r=\operatorname{rank}(T(m,n,s))$,
$$ \boxed{(mns)^{\omega/3}\le \operatorname{rank}(T(m,n,s)).} $$
(c) Direct sums
Let
$$ t=T(m,n,s)\oplus T(M,N,S), $$
and let
$$ r=\operatorname{rank}(t). $$
For every positive integer $k$,
$$ t^{\otimes k} = \bigoplus_{i=0}^{k} \binom{k}{i} ,T(m,n,s)^{\otimes i} \otimes T(M,N,S)^{\otimes(k-i)}. $$
Since rank is submultiplicative,
$$ \operatorname{rank}(t^{\otimes k}) \le r^k. $$
Each summand contains a matrix multiplication tensor of dimensions
$$ m^iM^{k-i}, \qquad n^iN^{k-i}, \qquad s^iS^{k-i}. $$
Applying part (b) to each summand,
$$ \operatorname{rank}(t^{\otimes k}) \ge \sum_{i=0}^{k} \binom{k}{i} (mns)^{i\omega/3} (MNS)^{(k-i)\omega/3}. $$
Hence
$$ r^k \ge \sum_{i=0}^{k} \binom{k}{i} (mns)^{i\omega/3} (MNS)^{(k-i)\omega/3}. $$
The right-hand side equals
$$ \left( (mns)^{\omega/3} + (MNS)^{\omega/3} \right)^k. $$
Taking $k$th roots gives
$$ \boxed{ (mns)^{\omega/3} + (MNS)^{\omega/3} \le r = \operatorname{rank}(t). } $$
(d) Nondegeneracy
The tensor $T(m,n,s)$ represents the bilinear map
$$ (A,B)\mapsto AB $$
from $m\times n$ and $n\times s$ matrices to $m\times s$ matrices.
Suppose $A\ne0$. Choose indices $(i,j)$ with $a_{ij}\ne0$. Let $B$ have a single nonzero entry $b_{jk}=1$. Then
$$ (AB){ik}=a{ij}\ne0. $$
Hence $AB\ne0$.
Similarly, if $B\ne0$, choose $b_{jk}\ne0$ and let $A$ have a single nonzero entry $a_{ij}=1$. Again $AB\ne0$.
Therefore neither factor contains a nonzero vector annihilating the bilinear map. The induced trilinear form is nondegenerate.
(e) The inequality $16^{\omega/3}+9^{\omega/3}\le17$
Exercise 65 gives
$$ \operatorname{rank}!\bigl( T(3,1,3)\oplus T(1,4,1) \bigr) =10. $$
Taking the tensor square,
$$ \bigl(T(3,1,3)\oplus T(1,4,1)\bigr)^{\otimes2} = T(9,1,9) \oplus 2,T(3,4,3) \oplus T(1,16,1). $$
Its rank is at most
$$ 10^2=100. $$
The two copies of $T(3,4,3)$ are nondegenerate. By Strassen's compression argument, these two summands can be merged into a single tensor of rank at most
$$ 100-(36+36)+17=45. $$
Consequently there exists a tensor
$$ t=T(1,16,1)\oplus T(9,1,9) $$
with
$$ \operatorname{rank}(t)\le17. $$
Applying part (c),
$$ 16^{\omega/3}+9^{\omega/3} \le \operatorname{rank}(t) \le17. $$
Hence
$$ 16^{\omega/3}+9^{\omega/3}\le17. $$
Let
$$ f(x)=16^{x/3}+9^{x/3}. $$
A direct calculation gives
$$ f(2.55) = 16^{0.85}+9^{0.85} \approx10.55+6.47 \approx17.02
$$
Since $f$ is strictly increasing,
$$ \omega<2.55. $$
Therefore
$$ \boxed{\omega<2.55}. $$
Verification
The proof of (a) uses the submultiplicativity
$$ M(mn)\le M(m)M(n), $$
which follows from tensor products of matrix multiplication algorithms. Fekete's lemma yields existence of the limiting exponent.
Part (b) is exactly the contrapositive form of Exercise 63(c).
Part (c) applies part (b) to every summand of $t^{\otimes k}$ and uses the binomial theorem.
Part (d) verifies directly that every nonzero matrix in either argument can be paired with another matrix producing a nonzero product.
Part (e) combines Exercise 65 with Schönhage's asymptotic sum inequality from part (c), yielding
$$ 16^{\omega/3}+9^{\omega/3}\le17, $$
and numerical evaluation at $2.55$ gives the stated bound.
This completes the proof.
∎