TAOCP 4.6.4 Exercise 55

Let T(P) = \sum_{i,j=1}^{n} p_{ij}\, e_i \otimes e_j \otimes e_{ij}, where ${e_i}$, ${e_j}$, and ${e_{ij}}$ are the standard bases of the three tensor factors.

taocpmathematicsalgorithmsvolume-2hm-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 55. [HM22] Determine the rank of tensor (74) when $P$ is an arbitrary $n \times n$ matrix.

Verified: yes
Solve time: 18m49s

Solution

Let

$$ T(P) = \sum_{i,j=1}^{n} p_{ij}, e_i \otimes e_j \otimes e_{ij}, $$

where ${e_i}$, ${e_j}$, and ${e_{ij}}$ are the standard bases of the three tensor factors. We wish to determine the rank of $T(P)$ as a tensor in $F^n \otimes F^n \otimes F^{n \times n}$.

Let

$$ S = {(i,j) \mid p_{ij} \neq 0}, \qquad m = |S|. $$

We will prove that

$$ \operatorname{rank}(T(P)) = m. $$

Upper bound

For each $(i,j)\in S$, the tensor

$$ p_{ij}, e_i \otimes e_j \otimes e_{ij} $$

is a simple tensor. Therefore

$$ T(P) = \sum_{(i,j)\in S} p_{ij}, e_i \otimes e_j \otimes e_{ij} $$

expresses $T(P)$ as a sum of $m$ simple tensors. Hence

$$ \operatorname{rank}(T(P)) \le m. $$

Lower bound

Suppose

$$ T(P) = \sum_{k=1}^{r} u_k \otimes v_k \otimes w_k $$

is any decomposition into simple tensors. For each $(a,b)\in S$, define the linear functional

$$ \pi_{ab} : F^{n \times n} \to F, \qquad \pi_{ab}(e_{ij}) = \delta_{ai}\delta_{bj}. $$

Applying $I \otimes I \otimes \pi_{ab}$ to both sides gives

$$ (I \otimes I \otimes \pi_{ab})(T(P)) = p_{ab}, e_a \otimes e_b = \sum_{k=1}^{r} \pi_{ab}(w_k) , u_k \otimes v_k. $$

Since $p_{ab} \neq 0$, the left-hand side is a nonzero simple tensor. Therefore at least one $\pi_{ab}(w_k) \neq 0$, so that $e_a \otimes e_b$ lies in the linear span of the matrices ${u_k \otimes v_k : 1 \le k \le r}$.

This holds for every $(a,b) \in S$. Therefore the $m$ linearly independent matrices

$$ {e_a \otimes e_b : (a,b) \in S} $$

lie in the span of ${u_k \otimes v_k : 1 \le k \le r}$. Since these $m$ matrices are linearly independent, the dimension of their span is $m$, and hence the number of rank-1 summands must satisfy

$$ r \ge m. $$

Conclusion

Combining the upper and lower bounds gives

$$ \operatorname{rank}(T(P)) = m = |{(i,j) \mid p_{ij} \neq 0}|. $$

Hence the tensor rank of $T(P)$ equals the number of nonzero entries of $P$.

$$ \boxed{\operatorname{rank}(T(P)) = |{(i,j) \mid p_{ij} \neq 0}|} $$

This completes the proof.