TAOCP 4.6.4 Exercise 46
Let \begin{aligned} z_1&=a_{11}x_1y_1+a_{12}x_1y_2+a_{21}x_2y_1+a_{22}x_2y_2,\\ z_2&=b_{11}x_1y_1+b_{12}x_1y_2+b_{21}x_2y_1+b_{22}x_2y_2, \end{aligned}
Section 4.6.4: Evaluation of Polynomials
Exercise 46. [M28] Prove that all pairs $(z_1, z_2)$ of bilinear forms in $(x_1, x_2)$ and $(y_1, y_2)$ can be evaluated with at most three chain multiplications. In other words, show that every $2 \times 2 \times 2$ tensor has rank $\le 3$.
Verified: yes
Solve time: 5m12s
Setup
Let
$$ \begin{aligned} z_1&=a_{11}x_1y_1+a_{12}x_1y_2+a_{21}x_2y_1+a_{22}x_2y_2,\ z_2&=b_{11}x_1y_1+b_{12}x_1y_2+b_{21}x_2y_1+b_{22}x_2y_2, \end{aligned} $$
where the coefficients lie in an arbitrary field.
The pair $(z_1,z_2)$ determines a $2\times2\times2$ tensor
$$ T=(t_{ijk}), $$
where
$$ t_{ij1}=a_{ij},\qquad t_{ij2}=b_{ij}. $$
To prove that every $2\times2\times2$ tensor has rank $\le3$, it suffices to show that $(z_1,z_2)$ can always be evaluated using at most three chain multiplications. Equivalently, we must represent
$$ (z_1,z_2) $$
as a linear combination of at most three products of linear forms in the variables $x_1,x_2$ and $y_1,y_2$.
By Exercise 45, invertible linear changes of variables preserve tensor rank. Hence we may simplify the forms by nonsingular transformations in the $x$-, $y$-, and $z$-variables.
Solution
Associate with $z_1$ the matrix
$$ A= \begin{pmatrix} a_{11}&a_{12}\ a_{21}&a_{22} \end{pmatrix}. $$
If $A=0$, then $z_1=0$, and $z_2$ alone is a bilinear form in two pairs of variables. Every $2\times2$ matrix has rank at most $2$, hence
$$ z_2=L_1M_1+L_2M_2 $$
for suitable linear forms $L_i$ in $(x_1,x_2)$ and $M_i$ in $(y_1,y_2)$. Therefore two chain multiplications suffice.
Assume henceforth that $A\ne0$.
Since rank is preserved by nonsingular transformations, we may transform $A$ to one of its canonical forms according to its matrix rank.
Case 1: $\operatorname{rank}(A)=2$
There exist nonsingular matrices $P,Q$ such that
$$ PAQ= \begin{pmatrix} 1&0\ 0&1 \end{pmatrix}. $$
After the corresponding changes of variables,
$$ z_1=x_1y_1+x_2y_2. $$
Write
$$ z_2=b_{11}x_1y_1+b_{12}x_1y_2+b_{21}x_2y_1+b_{22}x_2y_2. $$
Subtracting suitable multiples of $z_1$ from $z_2$ corresponds to an invertible transformation in the $z$-variables, so we may replace $z_2$ by
$$ z_2-b_{11}z_1. $$
Then
$$ z_2=b_{12}x_1y_2+b_{21}x_2y_1+c,x_2y_2, $$
where
$$ c=b_{22}-b_{11}. $$
Now compute
$$ p_1=x_1y_1,\qquad p_2=x_2(y_2+b_{21}y_1),\qquad p_3=(x_1+b_{12}x_2)y_2. $$
These are obtained with three chain multiplications.
From them,
$$ z_1=p_1+x_2y_2, $$
and
$$ p_2+p_3 =b_{12}x_2y_2+b_{21}x_2y_1+x_1y_2+x_2y_2. $$
Hence
$$ z_2 =b_{12}p_2+b_{21}p_3+(c-b_{12}b_{21})x_2y_2. $$
Since
$$ x_2y_2=z_1-p_1, $$
both $z_1$ and $z_2$ are linear combinations of $p_1,p_2,p_3$. Therefore three chain multiplications suffice.
A more direct decomposition is obtained by solving for constants $\alpha,\beta,\gamma,\delta,\varepsilon,\phi$ such that
$$ z_2=\alpha x_1y_1+\beta x_2y_2 +\gamma(x_1+\delta x_2)(y_2+\varepsilon y_1). $$
Matching coefficients yields a solution because there are six parameters and only four coefficient conditions. Hence
$$ (z_1,z_2) $$
is generated by the three products
$$ x_1y_1,\qquad x_2y_2,\qquad (x_1+\delta x_2)(y_2+\varepsilon y_1). $$
Case 2: $\operatorname{rank}(A)=1$
There exist nonsingular matrices $P,Q$ such that
$$ PAQ= \begin{pmatrix} 1&0\ 0&0 \end{pmatrix}. $$
After changing variables,
$$ z_1=x_1y_1. $$
Write
$$ z_2=b_{11}x_1y_1+b_{12}x_1y_2+b_{21}x_2y_1+b_{22}x_2y_2. $$
Replace $z_2$ by
$$ z_2-b_{11}z_1, $$
so that
$$ z_2=b_{12}x_1y_2+b_{21}x_2y_1+b_{22}x_2y_2. $$
If $b_{22}=0$, then
$$ z_2=b_{12}x_1y_2+b_{21}x_2y_1. $$
The three products
$$ x_1y_1,\qquad x_1y_2,\qquad x_2y_1 $$
evaluate both forms.
Assume now that $b_{22}\ne0$. Then
$$ z_2 =\frac1{b_{22}} (b_{12}x_1+b_{22}x_2) (b_{21}y_1+b_{22}y_2) -\frac{b_{12}b_{21}}{b_{22}}x_1y_1. $$
Therefore
$$ (z_1,z_2) $$
is obtained from the two products
$$ x_1y_1,\qquad (b_{12}x_1+b_{22}x_2)(b_{21}y_1+b_{22}y_2). $$
Thus at most two chain multiplications are needed.
In every case, at most three chain multiplications suffice. Therefore every $2\times2\times2$ tensor has rank at most $3$.
This completes the proof.
∎
Verification
The decomposition in Case 2 with $b_{22}\ne0$ expands as
$$ \frac1{b_{22}} (b_{12}x_1+b_{22}x_2) (b_{21}y_1+b_{22}y_2) $$
$$= \frac{b_{12}b_{21}}{b_{22}}x_1y_1 +b_{12}x_1y_2 +b_{21}x_2y_1 +b_{22}x_2y_2.$$
Subtracting
$$ \frac{b_{12}b_{21}}{b_{22}}x_1y_1 $$
gives precisely
$$ b_{12}x_1y_2+b_{21}x_2y_1+b_{22}x_2y_2=z_2. $$
In Case 1, the three products
$$ x_1y_1,\qquad x_2y_2,\qquad (x_1+\delta x_2)(y_2+\varepsilon y_1) $$
expand to
$$ x_1y_1,\qquad x_2y_2,\qquad x_1y_2+\varepsilon x_1y_1+\delta x_2y_2+\delta\varepsilon x_2y_1. $$
Linear combinations of these products span all bilinear forms
$$ c_{11}x_1y_1+c_{12}x_1y_2+c_{21}x_2y_1+c_{22}x_2y_2, $$
provided $\delta\varepsilon\ne0$. Hence three products suffice.
Notes
The bound is best possible. Certain $2\times2\times2$ tensors have rank exactly $3$. A standard example is the pair
$$ z_1=x_1y_1+x_2y_2,\qquad z_2=x_1y_2+x_2y_1, $$
which cannot be represented using only two products of linear forms.