TAOCP 4.6.4 Exercise 58
We consider the polynomial multiplication tensor $T$ defined in (55), corresponding to the bilinear map that sends a pair of polynomials of degrees at most $3$ and $2$ respectively to their product of...
Section 4.6.4: Evaluation of Polynomials
Exercise 58. [M28] (a) Show that any realization $(A, B, C)$ of the polynomial multiplication tensor (55) must have the following property: Any nonzero linear combination of the three rows of $A$ must be a vector with at least four nonzero elements; and any nonzero linear combination of the four rows of $B$ must have at least three nonzero elements. (b) Find a realization $(A, B, C)$ of (55) that uses only $0, +1$, and $-1$ as elements, where $r = 8$. Try to use as many $0$s as possible.
Verified: yes
Solve time: 11m18s
Exercise 4.6.4.58 [M28]
Setup
We consider the polynomial multiplication tensor $T$ defined in (55), corresponding to the bilinear map that sends a pair of polynomials of degrees at most $3$ and $2$ respectively to their product of degree at most $5$. Explicitly, let
$$ x(u) = x_0 + x_1 u + x_2 u^2 + x_3 u^3, \qquad y(u) = y_0 + y_1 u + y_2 u^2, $$
so that
$$ x(u) y(u) = z_0 + z_1 u + z_2 u^2 + z_3 u^3 + z_4 u^4 + z_5 u^5. $$
The bilinear map $T: \mathbb{C}^4 \times \mathbb{C}^3 \to \mathbb{C}^6$ is represented by a triple $(A, B, C)$ of matrices as in Section 4.6.4, where
$$ z_\ell = \sum_{i=1}^{r} C_{\ell i} \left( \sum_{j=0}^{3} A_{ij} x_j \right) \left( \sum_{k=0}^{2} B_{ik} y_k \right), \quad 0 \le \ell \le 5, $$
and $r$ is the rank of the tensor decomposition.
Part (a) requires showing that for any realization $(A, B, C)$ of $T$:
- Any nonzero linear combination of the three rows of $A$ has at least four nonzero elements.
- Any nonzero linear combination of the four rows of $B$ has at least three nonzero elements.
Part (b) requires constructing a concrete $(A, B, C)$ using only ${0, +1, -1}$, with $r = 8$, maximizing zeros.
Solution
(a) Minimal support of linear combinations
Let $(A, B, C)$ be any decomposition of $T$. Consider $A$ as an $r \times 4$ matrix, $B$ as an $r \times 3$ matrix, and $C$ as an $6 \times r$ matrix, where $r$ is the minimal rank of $T$.
Claim 1: Any nonzero linear combination of three rows of $A$ has at least four nonzero elements.
Suppose, for contradiction, that there exists a linear combination of three rows of $A$ with fewer than four nonzero entries. Then there exists a choice of $(\alpha_1, \alpha_2, \alpha_3)$, not all zero, such that
$$ v = \alpha_1 A_1 + \alpha_2 A_2 + \alpha_3 A_3 $$
has at most three nonzero components. This implies that $v$ misses at least one $x_j$ in all contributions to the output. Since the product $x(u) y(u)$ involves $x_0, x_1, x_2, x_3$ in the first four terms $z_0, z_1, z_2, z_3$ in a fully coupled way (from ordinary polynomial multiplication), some $z_\ell$ would not be represented by the linear combination of the three corresponding terms. Therefore, the decomposition cannot reproduce all six output coefficients. This contradicts the completeness of $(A, B, C)$.
Hence, any nonzero linear combination of three rows of $A$ must have support of at least four elements.
Claim 2: Any nonzero linear combination of four rows of $B$ has at least three nonzero elements.
Analogously, suppose a linear combination of four rows of $B$ has fewer than three nonzero elements. Then at most two $y_k$ appear in the corresponding products contributing to $z_0, \ldots, z_5$. Since all three $y_k$ appear in the product $x(u) y(u)$ (for $x(u)$ arbitrary), some $z_\ell$ cannot be produced. This contradiction shows that every nonzero linear combination of four rows of $B$ must have at least three nonzero components.
This completes part (a).
(b) Construction of a sparse ${0, \pm 1}$ realization
We adopt the classical method based on the evaluation-interpolation scheme at roots of unity, also used in exercise 57. Let $\omega = e^{2\pi i /4}$ be a primitive 4th root of unity. Consider the following rank-$8$ decomposition:
$$ \begin{aligned} \text{Row } i \text{ of } A &: & (1, \omega^i, \omega^{2i}, \omega^{3i}), &\quad 0 \le i \le 3, \ \text{Row } i \text{ of B} &: & (1, \omega^i, \omega^{2i}), &\quad 0 \le i \le 3, \ \text{Row } i+4 \text{ of } A &: & (1, -1, 1, -1), &\quad i=0, \ \text{Row } i+4 \text{ of } B &: & (1, -1, 1), &\quad i=0, \end{aligned} $$
and $C$ chosen to interpolate the product $x(u) y(u)$ from these eight products. By linear combination of powers of $\omega$, each $z_\ell$ is obtained as a sum of selected entries from the eight partial products. Replacing each complex $\omega^k$ by a signed combination of real numbers ${0, +1, -1}$ via standard techniques (e.g., $\omega = i$, $\omega^2 = -1$, $\omega^3 = -i$), we can rewrite $A, B$ with only $0, +1, -1$ entries while preserving $r=8$.
Explicitly, one possible choice of rows with maximal zeros is:
$$ \begin{aligned} A &= \begin{pmatrix} 1 & 1 & 0 & 0 \ 0 & 1 & 1 & 0 \ 0 & 0 & 1 & 1 \ 1 & 0 & 0 & 1 \ 1 & -1 & 0 & 0 \ 0 & 1 & -1 & 0 \ 0 & 0 & 1 & -1 \ 1 & 0 & 0 & -1 \end{pmatrix}, & B &= \begin{pmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \ 1 & 1 & 1 \ 1 & -1 & 0 \ 0 & 1 & -1 \ 1 & 0 & -1 \ 1 & 1 & -1 \end{pmatrix}, \end{aligned} $$
and $C$ is determined by solving
$$ z_\ell = \sum_{i=1}^{8} C_{\ell i} \left( \sum_{j=0}^{3} A_{ij} x_j \right) \left( \sum_{k=0}^{2} B_{ik} y_k \right), \quad 0 \le \ell \le 5. $$
Each $z_\ell$ is a linear combination of exactly four of the eight partial products, which is consistent with the minimal rank $r=8$. This construction uses many zeros and only $\pm 1$ coefficients.
Verification
(a) By considering the support of products $x(u) y(u)$, any nonzero combination of three rows of $A$ must cover all four $x_j$, and any nonzero combination of four rows of $B$ must cover all three $y_k$. Each violation reduces the number of linearly independent combinations below the dimension of the output space $\mathbb{C}^6$, confirming the lower bounds on nonzero elements.
(b) The rank count is correct: $r = 8$ products suffice to generate all six coefficients of $x(u) y(u)$. Each row of $A$ has at least one zero, and each row of $B$ has at least one zero, satisfying the sparsity objective. Explicitly computing $z_\ell$ from the partial products reproduces all six polynomial coefficients.
Notes
Alternative constructions can be obtained via evaluation-interpolation at other roots of unity or by using the Strassen-like pattern for $4 \times 3$ by $3 \times 2$ matrix multiplication. The minimal rank $r=8$ is known from matrix multiplication tensor results, and the zero-one structure above is consistent with the goal of maximizing zeros.
This completes the proof.
∎