TAOCP 4.6.4 Exercise 62
Let T=\begin{pmatrix}1&0\\0&1\end{pmatrix} denote the tensor with nonzero entries
Section 4.6.4: Evaluation of Polynomials
Exercise 62. [**] [M24] The border rank of $(t_{ijk})$, denoted by $\underline{\text{rank}}(t_{ijk})$, is $\min_{k\ge 0} \text{rank}k(t{ijk})$, where $\text{rank}_k$ is defined in exercise 61. Prove that the tensor $\begin{pmatrix} 1 & 0 \ 0 & 1 \end{pmatrix}$ has rank 3 but border rank 2, over every field.
Verified: no
Solve time: 6m15s
Solution
Let
$$ T=\begin{pmatrix}1&0\0&1\end{pmatrix} $$
denote the tensor with nonzero entries
$$ t_{111}=t_{122}=t_{212}=1, $$
all other $t_{ijk}=0$. Equivalently,
$$ T=e_1\otimes e_1\otimes e_1 +e_1\otimes e_2\otimes e_2 +e_2\otimes e_1\otimes e_2 . $$
We prove that $\operatorname{rank}(T)=3$ but $\underline{\operatorname{rank}}(T)=2$.
Rank
The displayed expression already gives
$$ \operatorname{rank}(T)\le3. $$
It remains to prove that $\operatorname{rank}(T)\neq2$.
Suppose, for contradiction, that
$$ T=a_1\otimes b_1\otimes c_1 +a_2\otimes b_2\otimes c_2 . $$
For each $k\in{1,2}$, let
$$ M_k=(t_{ijk})_{i,j} $$
be the $2\times2$ matrix obtained by fixing the third index.
From the definition of $T$,
$$ M_1=\begin{pmatrix}1&0\0&0\end{pmatrix}, \qquad M_2=\begin{pmatrix}0&1\1&0\end{pmatrix}. $$
Now every simple tensor $a\otimes b\otimes c$ contributes
$$ c_1ab^{\mathsf T} \quad\text{to }M_1, \qquad c_2ab^{\mathsf T} \quad\text{to }M_2. $$
Hence there exist rank-1 matrices $A,B$ such that
$$ M_1=A+B, \qquad M_2=\lambda A+\mu B $$
for some scalars $\lambda,\mu$.
Since $M_1$ has rank $1$, while $A$ and $B$ each have rank at most $1$, it follows that $A$ and $B$ are linearly dependent. Therefore $M_2$ must also be a scalar multiple of $M_1$.
But this is impossible, because
$$ M_1=\begin{pmatrix}1&0\0&0\end{pmatrix} $$
and
$$ M_2=\begin{pmatrix}0&1\1&0\end{pmatrix} $$
are not proportional.
Hence $\operatorname{rank}(T)\ge3$. Therefore
$$ \boxed{\operatorname{rank}(T)=3.} $$
Border rank
We now show that $T$ has border rank $2$.
For $\varepsilon\neq0$, define
$$ T_\varepsilon = \frac1\varepsilon (e_1+\varepsilon e_2)\otimes (e_1+\varepsilon e_2)\otimes (e_1+\varepsilon e_2) - \frac1\varepsilon e_1\otimes e_1\otimes e_1 . $$
Each $T_\varepsilon$ is the difference of two simple tensors, hence has rank at most $2$.
Expand:
$$ \begin{aligned} T_\varepsilon &= \frac1\varepsilon \Bigl( e_1\otimes e_1\otimes e_1 \ &\qquad +\varepsilon( e_2\otimes e_1\otimes e_1 +e_1\otimes e_2\otimes e_1 +e_1\otimes e_1\otimes e_2) \ &\qquad +\varepsilon^2( e_2\otimes e_2\otimes e_1 +e_2\otimes e_1\otimes e_2 +e_1\otimes e_2\otimes e_2) \ &\qquad +\varepsilon^3 e_2\otimes e_2\otimes e_2 \Bigr) - \frac1\varepsilon e_1\otimes e_1\otimes e_1 . \end{aligned} $$
After cancellation,
$$ \begin{aligned} T_\varepsilon &= e_2\otimes e_1\otimes e_1 +e_1\otimes e_2\otimes e_1 +e_1\otimes e_1\otimes e_2 \ &\qquad +\varepsilon( e_2\otimes e_2\otimes e_1 +e_2\otimes e_1\otimes e_2 +e_1\otimes e_2\otimes e_2) \ &\qquad +\varepsilon^2 e_2\otimes e_2\otimes e_2 . \end{aligned} $$
Now apply invertible linear changes of basis in the three tensor factors:
$$ A(e_1)=e_2,\quad A(e_2)=e_1, $$
$$ B(e_1)=e_1,\quad B(e_2)=e_2, $$
$$ C(e_1)=e_1,\quad C(e_2)=e_2. $$
Then
$$ (A\otimes B\otimes C)(T_\varepsilon) $$
has limit
$$ e_1\otimes e_1\otimes e_1 + e_2\otimes e_2\otimes e_1 + e_2\otimes e_1\otimes e_2 . $$
Finally, permuting the third basis vectors exchanges $e_1$ and $e_2$ in the third factor, giving the limit
$$ e_1\otimes e_1\otimes e_1 + e_1\otimes e_2\otimes e_2 + e_2\otimes e_1\otimes e_2 =T. $$
Thus $T$ is a limit of tensors of rank at most $2$. Therefore
$$ \underline{\operatorname{rank}}(T)\le2. $$
Since $\operatorname{rank}(T)=3$, certainly $T\neq0$, so its border rank cannot be $1$. Hence
$$ \boxed{\underline{\operatorname{rank}}(T)=2.} $$
Therefore the tensor
$$ \begin{pmatrix}1&0\0&1\end{pmatrix} $$
has rank $3$ but border rank $2$, over every field. ∎