TAOCP 4.6.4 Exercise 47
Let $V=\mathbb F^{m\times n\times s}$ be the vector space of all $m\times n\times s$ tensors over a field $\mathbb F$.
Section 4.6.4: Evaluation of Polynomials
Exercise 47. [M25] Prove that for all $m$, $n$, and $s$ there exists an $m \times n \times s$ tensor whose rank is at least $\lfloor mns/(m + n + s) \rfloor$. Conversely, show that every $m \times n \times s$ tensor has rank at most $\min(mns/(m, n, s))$.
Verified: no
Solve time: 10m07s
Solution
Let $V=\mathbb F^{m\times n\times s}$ be the vector space of all $m\times n\times s$ tensors over a field $\mathbb F$. Its dimension is $mns$.
A tensor has rank $1$ if it is of the form
$$ u_i v_j w_k, $$
with $u\in\mathbb F^m$, $v\in\mathbb F^n$, $w\in\mathbb F^s$. The rank of a tensor $t={t_{ijk}}$ is the least $r$ such that
$$ t_{ijk}=\sum_{\ell=1}^r a_i^{(\ell)}b_j^{(\ell)}c_k^{(\ell)}. $$
We prove the lower and upper bounds separately.
Lower bound
We must show that there exists an $m\times n\times s$ tensor whose rank is at least
$$ \left\lfloor \frac{mns}{m+n+s}\right\rfloor . $$
Fix an integer $r$ such that
$$ r(m+n+s)<mns. $$
We shall prove that not every tensor has rank at most $r$. This implies that some tensor has rank at least $r+1$.
Consider the polynomial map
$$ \Phi:\mathbb F^{r(m+n+s)}\to V $$
defined by
$$ \Phi\bigl(a^{(1)},b^{(1)},c^{(1)},\ldots, a^{(r)},b^{(r)},c^{(r)}\bigr) = \sum_{\ell=1}^r a^{(\ell)}\otimes b^{(\ell)}\otimes c^{(\ell)}. $$
Explicitly,
$$ \Phi(\cdots){ijk} = \sum{\ell=1}^r a_i^{(\ell)}b_j^{(\ell)}c_k^{(\ell)}. $$
The image of $\Phi$ is precisely the set of tensors of rank at most $r$.
Now $\mathbb F^{r(m+n+s)}$ is an affine variety of dimension $r(m+n+s)$. A standard theorem of algebraic geometry states that the image of a polynomial map has dimension at most the dimension of the domain. Hence
$$ \dim \operatorname{im}\Phi \le r(m+n+s). $$
Since
$$ r(m+n+s)<mns=\dim V, $$
the image of $\Phi$ cannot equal all of $V$. Therefore the tensors of rank at most $r$ form a proper subset of $V$. Consequently, there exists a tensor whose rank exceeds $r$.
Now choose
$$ r=\left\lfloor \frac{mns}{m+n+s}\right\rfloor-1. $$
Then
$$ r(m+n+s) < mns, $$
so there exists a tensor of rank at least
$$ r+1 = \left\lfloor \frac{mns}{m+n+s}\right\rfloor . $$
This proves the lower bound.
Upper bound
Let $t={t_{ijk}}$ be any $m\times n\times s$ tensor.
For each $k$, define the matrix
$$ M_k=(t_{ijk})_{1\le i\le m,\ 1\le j\le n}. $$
Then
$$ t=\sum_{k=1}^s M_k\otimes e_k, $$
where $e_k$ is the $k$th standard basis vector of $\mathbb F^s$.
Each matrix $M_k$ has matrix rank at most $\min(m,n)$, hence can be written as a sum of at most $\min(m,n)$ rank-one matrices:
$$ M_k=\sum_{\ell=1}^{\min(m,n)} u^{(k,\ell)}(v^{(k,\ell)})^T. $$
Therefore
$$ t= \sum_{k=1}^s \sum_{\ell=1}^{\min(m,n)} u^{(k,\ell)} \otimes v^{(k,\ell)} \otimes e_k. $$
Each summand is a rank-one tensor, so
$$ \operatorname{rank}(t)\le s\min(m,n). $$
By symmetry,
$$ \operatorname{rank}(t)\le m\min(n,s), $$
and
$$ \operatorname{rank}(t)\le n\min(m,s). $$
Hence
$$ \operatorname{rank}(t)\le \min\bigl( s\min(m,n), m\min(n,s), n\min(m,s) \bigr). $$
Let $d=\min(m,n,s)$. If, for example, $d=m$, then $m\le n$ and $m\le s$, so
$$ s\min(m,n)=sm, $$
$$ m\min(n,s)=m\min(n,s), $$
$$ n\min(m,s)=nm. $$
The minimum of these three numbers is
$$ m\min(n,s). $$
Since $m\le n$ and $m\le s$,
$$ m\min(n,s)=\frac{mns}{\max(n,s)} \le \frac{mns}{m}. $$
But one of the three displayed bounds is exactly
$$ ns=\frac{mns}{m}. $$
Thus
$$ \operatorname{rank}(t)\le \frac{mns}{m}. $$
The same argument applies in the cases $d=n$ and $d=s$. Therefore
$$ \operatorname{rank}(t)\le \frac{mns}{\min(m,n,s)}. $$
Thus every $m\times n\times s$ tensor has rank at most
$$ \frac{mns}{\min(m,n,s)}. $$
Combining the two parts completes the proof. ∎