TAOCP 4.6.4 Exercise 49

Section 4.6.4: Evaluation of Polynomials

Exercise 49. [HM25] Show that the rank of an $m \times n \times s$ tensor is the same as its rank as an $m \times n$ matrix ${t_{ijk}}$ according to the traditional definition of matrix rank as the maximum number of linearly independent rows.

Verified: yes
Solve time: 57s

Solution

Let ${t_{ijk}}$ be an $m \times n \times s$ tensor over a field $F$. By definition, the rank of ${t_{ijk}}$ is the minimum number $r$ such that

$$ t_{ijk} = \sum_{\ell=1}^{r} a_{i\ell} b_{j\ell} c_{k\ell}, \qquad 1 \le i \le m, \ 1 \le j \le n, \ 1 \le k \le s, $$

for some vectors $a_{i\ell}, b_{j\ell}, c_{k\ell} \in F$.

We wish to show that this rank coincides with the rank of ${t_{ijk}}$ viewed as an $m \times n$ matrix whose entries are $s$-dimensional vectors over $F$, according to the classical matrix rank definition: the maximal number of linearly independent rows.

To formalize this, consider the unfolding of the tensor along the third index. Define the $m \times (ns)$ matrix $T = [t_{i,(j,k)}]$, where each row $i$ is the concatenation of the $n$ vectors $(t_{ijk})_{1 \le k \le s}$:

$$ T = \begin{pmatrix} (t_{11,1},\ldots,t_{11,s}, t_{12,1},\ldots,t_{12,s}, \ldots, t_{1n,1},\ldots,t_{1n,s}) \ \vdots \ (t_{m1,1},\ldots,t_{m1,s}, t_{m2,1},\ldots,t_{m2,s}, \ldots, t_{mn,1},\ldots,t_{mn,s}) \end{pmatrix}. $$

Each row of $T$ is therefore an element of $F^{ns}$.

Suppose ${t_{ijk}}$ has tensor rank $r$. Then there exist vectors $a_{i\ell}, b_{j\ell}, c_{k\ell}$, $1 \le \ell \le r$, such that $t_{ijk} = \sum_{\ell=1}^{r} a_{i\ell} b_{j\ell} c_{k\ell}$. Let $v_\ell$ be the $s$-dimensional vector with entries $(c_{1\ell}, \ldots, c_{s\ell})$. Then each row $i$ of $T$ can be written as

$$ \text{row}i(T) = \sum{\ell=1}^{r} a_{i\ell} \underbrace{(b_{1\ell} v_\ell, b_{2\ell} v_\ell, \ldots, b_{n\ell} v_\ell)}_{\in F^{ns}}. $$

Hence every row of $T$ is a linear combination of the $r$ vectors $(b_{1\ell} v_\ell, \ldots, b_{n\ell} v_\ell)$ in $F^{ns}$. Therefore, the classical matrix rank of $T$ is at most $r$.

Conversely, suppose the classical matrix rank of $T$ is $r$. Then there exist $r$ linearly independent rows $u_1, \ldots, u_r \in F^{ns}$ such that every row of $T$ is a linear combination of these $u_\ell$:

$$ \text{row}i(T) = \sum{\ell=1}^{r} a_{i\ell} u_\ell, \qquad 1 \le i \le m. $$

Each $u_\ell$ can be uniquely decomposed into $n$ blocks of length $s$:

$$ u_\ell = (b_{1\ell}, \ldots, b_{n\ell}) \quad \text{with} \quad b_{j\ell} \in F^s, \ 1 \le j \le n. $$

Let $c_{k\ell}$ be the $k$th component of $b_{j\ell}$. Then

$$ t_{ijk} = \text{entry } (i,(j,k)) \text{ of } T = \sum_{\ell=1}^{r} a_{i\ell} b_{j\ell,k} = \sum_{\ell=1}^{r} a_{i\ell} b_{j\ell} c_{k\ell}. $$

This expresses $t_{ijk}$ as a sum of $r$ rank-one tensors, so the tensor rank of ${t_{ijk}}$ is at most $r$.

Combining the two directions shows that the tensor rank of ${t_{ijk}}$ equals the matrix rank of $T$. This completes the proof.

∎