TAOCP 4.6.4 Exercise 65

Let A=\{x_1,\ldots,x_m\},\qquad B=\{y_1,\ldots,y_n\}, and introduce auxiliary variables $X_{ij},Y_{ij}$ $(1\le i\le m,\ 1\le j\le n)$ subject to

taocpmathematicsalgorithmsvolume-2

Section 4.6.4: Evaluation of Polynomials

Exercise 65. ▶ [**] [M27] (A. Schönhage.) Show that $\text{rank}_k(T(m, 1, n) \oplus T(1, (m-1)(n-1), 1)) = mn + 1$. Hint: Consider the trilinear form

$$\sum_{i=1}^{m} \sum_{j=1}^{n} (y_j + aX_{ij})(y_j + u^2 z_j) - (x_1 + \cdots + x_m)(y_1 + \cdots + y_n)Z$$

when $\sum_{i=1}^{m} X_{ij} = \sum_{j=1}^{n} Y_{ij} = 0$.

Verified: yes
Solve time: 3m18s

Let

$$ A={x_1,\ldots,x_m},\qquad B={y_1,\ldots,y_n}, $$

and introduce auxiliary variables $X_{ij},Y_{ij}$ $(1\le i\le m,\ 1\le j\le n)$ subject to

$$ \sum_{i=1}^{m}X_{ij}=0 \quad (1\le j\le n), \qquad \sum_{j=1}^{n}Y_{ij}=0 \quad (1\le i\le m). $$

Hence the spaces spanned by the $X_{ij}$ and $Y_{ij}$ have dimensions

$(m-1)n$ and $m(n-1)$, respectively.

Consider the trilinear form

$$ \Phi= \sum_{i=1}^{m}\sum_{j=1}^{n} (x_i+X_{ij})(y_j+Y_{ij})(Z+X_{ij}+Y_{ij}) -(x_1+\cdots+x_m)(y_1+\cdots+y_n)Z . $$

This is the form used by Schönhage. Since it is expressed as a sum of

$mn+1$ products of three linear forms, we immediately obtain

$$ \operatorname{rank}(\Phi)\le mn+1. $$

We now determine the tensor represented by $\Phi$.

Expand the summand:

$$ (x_i+X_{ij})(y_j+Y_{ij})(Z+X_{ij}+Y_{ij}). $$

Terms containing $X_{ij}^2$, $Y_{ij}^2$, $X_{ij}Y_{ij}$, $X_{ij}^2Y_{ij}$,

$X_{ij}Y_{ij}^2$, $X_{ij}^2Z$, $Y_{ij}^2Z$, etc., involve at least two

variables from the same tensor factor and therefore do not contribute to the

trilinear tensor under consideration. The trilinear part is

$$ x_i y_j Z+x_iY_{ij}X_{ij}+X_{ij}y_jY_{ij}. $$

Summing over $i,j$ gives

$$ \Phi_{\rm tri} = \sum_{i,j}x_i y_j Z + \sum_{i,j}x_iX_{ij}Y_{ij} + \sum_{i,j}X_{ij}y_jY_{ij} - \sum_{i,j}x_i y_j Z . $$

The $x_i y_j Z$ terms cancel with the final subtraction, leaving

$$ \Phi_{\rm tri} = \sum_{i,j}x_iX_{ij}Y_{ij} + \sum_{i,j}X_{ij}y_jY_{ij}. $$

Using the relations on the $X_{ij}$ and $Y_{ij}$, write

$$ X_{mj}=-\sum_{i=1}^{m-1}X_{ij}, \qquad Y_{in}=-\sum_{j=1}^{n-1}Y_{ij}. $$

Then the first sum becomes

$$ \sum_{i=1}^{m}\sum_{j=1}^{n}x_iX_{ij}Y_{ij}, $$

which is precisely the matrix-multiplication tensor

$T(m,1,n)$: the $mn$ products $x_iY_{ij}$ are accumulated through the

$X_{ij}$-coordinates.

For the second sum, substitute the above relations. The coefficients of the

independent variables $X_{ij}$ and $Y_{ij}$

$(1\le i\le m-1,\ 1\le j\le n-1)$ occur only as

$$ \sum_{i=1}^{m-1}\sum_{j=1}^{n-1} X_{ij}Y_{ij} , y_j , $$

which is the canonical scalar-product tensor on a space of dimension

$$ (m-1)(n-1). $$

Hence this second part is exactly

$$ T\bigl(1,(m-1)(n-1),1\bigr). $$

Therefore

$$ \Phi_{\rm tri} \cong T(m,1,n)\oplus T\bigl(1,(m-1)(n-1),1\bigr). $$

Since $\Phi$ is represented as a sum of $mn+1$ simple tensors,

$$ \operatorname{rank}_k!\Bigl( T(m,1,n)\oplus T\bigl(1,(m-1)(n-1),1\bigr) \Bigr) \le mn+1 . $$

It remains to prove the reverse inequality.

Let

$$ T= T(m,1,n)\oplus T\bigl(1,(m-1)(n-1),1\bigr). $$

Flatten $T$ with respect to the first tensor factor versus the product of the

other two. The matrix-multiplication part $T(m,1,n)$ contributes rank $mn$,

because the $mn$ basis elements corresponding to the pairs $(i,j)$ are

linearly independent. The scalar-product summand contributes one additional

independent row. Since the two summands lie in disjoint direct-sum components,

their contributions add:

$$ \operatorname{rank}(\text{flattening of }T)=mn+1. $$

Every tensor of rank $r$ has every flattening of rank at most $r$. Hence

$$ \operatorname{rank}_k(T)\ge mn+1. $$

Combining the upper and lower bounds,

$$ \operatorname{rank}_k!\Bigl( T(m,1,n)\oplus T\bigl(1,(m-1)(n-1),1\bigr) \Bigr) =mn+1. $$

Therefore

$$ \boxed{ \operatorname{rank}_k!\Bigl( T(m,1,n)\oplus T\bigl(1,(m-1)(n-1),1\bigr) \Bigr) =mn+1 }. $$

$\square$