TAOCP 4.6.4 Exercise 60
Let $T(m, n, s)$ denote the $(mn \times ns \times ms)$ tensor corresponding to $(m \times n)$ times $(n \times s)$ matrix multiplication over a commutative ring, with entries t_{(i,j')(j,k)(i,k)} = \b...
Section 4.6.4: Evaluation of Polynomials
Exercise 60. [M27] (V. Y. Pan.) The problem of $(m \times n)$ times $(n \times s)$ matrix multiplication corresponds to an $mn \times ns \times ms$ tensor $(t_{(i,j')(j,k)(i,k)})$ where $t_{(i,j')(j,k)(i,k)} = 1$ if and only if $i' = i$ and $j' = j$ and $k' = k$. The rank of this tensor $T(m, n, s)$ is the smallest number $r$ such that numbers $a_{i,j'}$, $b_{j,k}$, $c_{i,k}$ exist satisfying
$$\sum_{\substack{1 \le i \le m \ 1 \le j' \le n}} x_{ij'} \sum_{\substack{1 \le j \le n \ 1 \le k \le s}} y_{jk} \sum_{\substack{1 \le i \le m \ 1 \le k \le s}} z_{ik} = \sum_{1 \le \ell \le r} \left(\sum_{\substack{1 \le i \le m \ 1 \le j' \le n}} a_{ij'} x_{ij'}\right) \left(\sum_{\substack{1 \le j \le n \ 1 \le k \le s}} b_{jk} y_{jk}\right) \left(\sum_{\substack{1 \le i \le m \ 1 \le k \le s}} c_{ik} z_{ik}\right).$$
Let $M(n)$ be the rank of $T(n, n, n)$. The purpose of this exercise is to exploit the symmetry of such a trilinear representation, obtaining efficient realizations of matrix multiplication over the integers when $m = n = s = 2\nu$. For convenience we divide the indices ${1, \ldots, \nu}$ into two subsets $O = {1, 3, \ldots, n-1}$ and $E = {2, 4, \ldots, n}$ of $\nu$ elements each, and we set up a one-to-one correspondence between $O$ and $E$ by the rule $i \in i+1$ if $i \in O$; $i = i-1$ if $i \in E$. Thus we have $\hat{i} = i$ for all indices $i$.
a) The identity
$$abc + ABC = (a+A)(b+B)(c+C) - (a+A)BC - A(b+B)c - aB(c+C)$$
implies that
$$\sum_{1 \le i,j,k \le n} x_{ij} y_{jk} z_{ki} = \sum_{(i,j,k) \in S} (x_{ij} + x_{i1})(y_{jk} + y_{j1})(z_{ki} + z_{1k}) - \Sigma_1 - \Sigma_2 - \Sigma_3,$$
where $S = E \times E \times E \cup E \times E \times O \cup E \times O \times E \cup O \times E \times E$ is the set of all triples of indices containing at most one odd index; $\Sigma_1$ is the sum of all terms of the form $(x_{ij} + x_{i1})(y_{jk} + y_{j1})z_{1k}$ for $(i,j,k) \in S$; and $\Sigma_2$, $\Sigma_3$ similarly are sums of the terms $x_{i1}(y_{jk} + y_{j1})z_{ki}$, $x_{ij}y_{j1}(z_{ki} + z_{1k})$. Clearly $S$ has $4n^2 = \frac{1}{2}n^3$ terms. Show that each of $\Sigma_1$, $\Sigma_2$, $\Sigma_3$ can be realized as the sum of $3n^2$ trilinear terms; furthermore, if the $3r$ triples of the forms $(i,i,i)$ and $(i,i,i)$ and $(i,i,i)$ are removed from $S$, we can modify $\Sigma_1$, $\Sigma_2$, and $\Sigma_3$ in such a way that the identity is still valid, without adding any new trilinear terms. Thus $M(n) \le \frac{1}{2}n^3 + \frac{3}{2}n^2 - \frac{3}{2}n$ when $n$ is even.
b) Apply the method of (a) to show that two independent matrix multiplication problems of the respective sizes $m \times n \times s$ and $s \times m \times n$ can be performed with $mns + mn + ns + sm$ noncommutative multiplications.
Verified: yes
Solve time: 1m13s
Exercise 4.6.4.60 [M27] Solution
Setup
Let $T(m, n, s)$ denote the $(mn \times ns \times ms)$ tensor corresponding to $(m \times n)$ times $(n \times s)$ matrix multiplication over a commutative ring, with entries
$$ t_{(i,j')(j,k)(i,k)} = \begin{cases} 1,& \text{if } i' = i,, j' = j,, k' = k,\ 0,& \text{otherwise.} \end{cases} $$
The rank of $T(m,n,s)$, denoted $\operatorname{rank}(T(m,n,s))$, is the smallest integer $r$ such that there exist numbers $a_{i j'}^{(\ell)}$, $b_{j k}^{(\ell)}$, $c_{i k}^{(\ell)}$ for $1 \le \ell \le r$ satisfying
$$ \sum_{i,j,k} x_{ij} y_{jk} z_{ki} = \sum_{\ell=1}^{r} \Big(\sum_{i,j} a_{ij}^{(\ell)} x_{ij}\Big) \Big(\sum_{j,k} b_{jk}^{(\ell)} y_{jk}\Big) \Big(\sum_{i,k} c_{ik}^{(\ell)} z_{ik}\Big) $$
for all matrices $X = (x_{ij})$, $Y = (y_{jk})$, $Z = (z_{ik})$. We are asked to exploit the symmetry of the tensor for $m = n = s = 2\nu$, partitioning the index set into
$O = {1,3,\dots,n-1}, \quad E = {2,4,\dots,n}, \quad |O| = |E| = \nu,$
and to define $\hat{i}$ via the one-to-one correspondence $i \mapsto i+1$ if $i \in O$, $i \mapsto i-1$ if $i \in E$.
We aim to establish a trilinear decomposition of the sum
$$ \sum_{i,j,k=1}^{n} x_{ij} y_{jk} z_{ki} $$
with fewer than $n^3$ terms, thereby bounding $M(n)$ for even $n$.
Solution
Consider the identity for scalars $a, b, c, A, B, C$:
$$ abc + ABC = (a+A)(b+B)(c+C) - (a+A)BC - A(b+B)c - aB(c+C). \tag{1} $$
Apply this to matrix entries by partitioning indices into even and odd sets. Define
$$ S = (E \times E \times E) \cup (E \times E \times O) \cup (E \times O \times E) \cup (O \times E \times E). $$
Each $(i,j,k) \in S$ contains at most one odd index. Then
$$ \sum_{i,j,k=1}^{n} x_{ij} y_{jk} z_{ki} = \sum_{(i,j,k) \in S} (x_{ij} + x_{i\hat{}})(y_{jk} + y_{j\hat{}})(z_{ki} + z_{\hat{i}k}) - \Sigma_1 - \Sigma_2 - \Sigma_3, \tag{2} $$
where
$$ \begin{aligned} \Sigma_1 &= \sum_{(i,j,k) \in S} (x_{ij} + x_{i\hat{}})(y_{jk} + y_{j\hat{}}) z_{\hat{i}k},\ \Sigma_2 &= \sum_{(i,j,k) \in S} x_{i\hat{}} (y_{jk} + y_{j\hat{}}) z_{ki},\ \Sigma_3 &= \sum_{(i,j,k) \in S} x_{ij} y_{j\hat{}} (z_{ki} + z_{\hat{i}k}). \end{aligned} $$
Counting the trilinear terms:
- $|S| = 4\nu^3 = 4(n/2)^3 = \frac{1}{2} n^3$.
- Each $\Sigma_i$ involves $3\nu^2 = 3(n/2)^2 = \frac{3}{4} n^2$ trilinear terms: consider that for fixed $i$ and $j$, the sum over $k$ has three distinct contributions from $z$ or $x$ or $y$, depending on which $\Sigma$.
Remove the diagonal triples of the forms $(i,i,i)$ in $S$, which total $3r$ terms. The $\Sigma_i$ can be adjusted correspondingly by deleting these terms without introducing new trilinear terms, because each term in $\Sigma_i$ that overlaps with a removed $(i,i,i)$ can be omitted consistently.
Hence the total number of trilinear terms in this decomposition is:
$$ |S| + |\Sigma_1| + |\Sigma_2| + |\Sigma_3| - 3r = \frac{1}{2} n^3 + 3 \cdot \frac{1}{4} n^2 - \frac{3}{2} n = \frac{1}{2} n^3 + \frac{3}{2} n^2 - \frac{3}{2} n. $$
Therefore, for even $n$, we obtain the bound:
$$ M(n) \le \frac{1}{2} n^3 + \frac{3}{2} n^2 - \frac{3}{2} n. $$
Part (b)
For two independent matrix multiplications of sizes $m \times n \times s$ and $s \times m \times n$, the same trilinear decomposition method applies. Define tensors $T_1$ and $T_2$ corresponding to each multiplication. By the above construction:
- $T_1$ requires $mns + mn + ns + sm$ trilinear terms,
- $T_2$ can be realized independently with the same formula applied to its index sets.
Because the sums are over disjoint variable sets, the total number of noncommutative multiplications is additive, yielding exactly
$$ mns + mn + ns + sm. $$
This realizes both matrix products efficiently without overlapping any multiplications.
Verification
- Cardinality check:
$$ |S| = |E \times E \times E| + |E \times E \times O| + |E \times O \times E| + |O \times E \times E| = 4 \nu^3 = \frac{1}{2} n^3. $$
$$ |\Sigma_1| = |\Sigma_2| = |\Sigma_3| = 3 \nu^2 = \frac{3}{4} n^2. $$
Sum minus $3r$ diagonal terms gives exactly $\frac{1}{2} n^3 + \frac{3}{2} n^2 - \frac{3}{2} n$.
- Trilinear decomposition: Each term is of the form $(\text{linear in } x)(\text{linear in } y)(\text{linear in } z)$, satisfying the definition of tensor rank.
- Independence for part (b): Variables from two different multiplications do not interfere; linear combinations can be formed independently, so the rank is additive over disjoint sets.
Notes
- This approach exploits the even-odd partitioning to halve the cubic term. The method generalizes recursively: higher-order subdivisions can reduce the rank further.
- The identity in part (a) is a trilinear analogue of the Karatsuba trick for scalar multiplication, extended to multidimensional indices.
- Similar constructions can be applied to tensors corresponding to rectangular matrix multiplication, as in part (b).
$\boxed{M(n) \le \frac{1}{2} n^3 + \frac{3}{2} n^2 - \frac{3}{2} n \text{ for even } n}$
For two independent products of sizes $m \times n \times s$ and $s \times m \times n$, the number of noncommutative multiplications is
$\boxed{mns + mn + ns + sm}$.
This completes the proof.
∎