TAOCP 4.6.4 Exercise 50
Let $T={t_{ijk}}$ be the $mn\times n\times m$ tensor corresponding to multiplication of an $m\times n$ matrix by an $n\times1$ column vector.
Section 4.6.4: Evaluation of Polynomials
Exercise 50. [HM20] (S. Winograd.) Let ${t_{ijk}}$ be the $mn \times n \times m$ tensor corresponding to multiplication of an $m \times n$ matrix by an $n \times 1$ column vector. Prove that the rank of ${t_{ijk}}$ is $mn$.
Verified: yes
Solve time: 3m05s
Solution
Let $T={t_{ijk}}$ be the $mn\times n\times m$ tensor corresponding to multiplication of an $m\times n$ matrix by an $n\times1$ column vector.
Write the entries of the matrix as $a_{pq}$, $1\le p\le m$, $1\le q\le n$, and the entries of the vector as $x_q$, $1\le q\le n$. The product $y=Ax$ has components
$$ y_p=\sum_{q=1}^{n} a_{pq}x_q . $$
Index the $mn$ matrix entries by a single index
$$ i=(p,q), \qquad 1\le p\le m,\ 1\le q\le n. $$
Then the bilinear map is
$$ y_p=\sum_{q=1}^{n} t_{(p,q),q,p},a_{pq}x_q, $$
where
$$ t_{(p,q),q,p}=1, $$
and all other tensor entries are $0$.
Exercise 49 identifies the tensor rank with the rank of the associated matrix whose rows are indexed by $i=(p,q)$ and whose columns are indexed by pairs $(j,k)$. Thus it suffices to determine the matrix rank.
For each row index $(p,q)$, the only nonzero entry occurs in column $(q,p)$, and that entry equals $1$. Hence the associated matrix has exactly one nonzero entry in each row, and distinct rows correspond to distinct columns. After a suitable ordering of rows and columns, this matrix is simply the $mn\times mn$ identity matrix.
Therefore its rows are linearly independent. The matrix rank is
$$ mn. $$
By Exercise 49, the tensor rank equals this matrix rank. Hence
$$ \operatorname{rank}(T)=mn. $$
Therefore the tensor corresponding to multiplication of an $m\times n$ matrix by an $n\times1$ column vector has rank
$$ \boxed{mn}. $$
This completes the proof.
∎