# Determining the rank of a sparse tensor in $\mathbb{R}^{2 \times 2 \times 2}$

In this question I will only consider order 3 tensors.

Consider the following tensor in $\mathbb{R}^{2 \times 2 \times 2}$ (which I want to prove its rank 3): $$T' = \begin{bmatrix} \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ \end{bmatrix} , \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} \end{bmatrix}$$

For notational clarity, one can imagine that $T'$ is a matrix in 3D, of size 2 by 2 by 2. The first matrix corresponds to the index of selecting a matrix, then a second index could be for selecting a column and the last index is for selecting a row. So for example $T'(1,1,1) = 0$.

Recall that a rank one tensor (third order) is defined as:

$$T = u \otimes v \otimes w \otimes$$

Which is simply an outer product of three vectors, where $u \in \mathbb{R}^m, v \in \mathbb{R}^n, w \in \mathbb{R}^p$ (The specific example at the top of the question for $T'$ we have n = m = p). The definition of an outer product of order three is:

$$T_{i,j,k} = u_i v_j w_k$$

To make this definition more intuitive, one can imagine the result of this outer product as a 3D matrix, where you need 3 indices to index a certain position in the 3D matrix (i.e. order 3 tensor). i.e. we have matrices of size m by n stacked on each other and we have p of them.

and recall the definition of the rank of a tensor:

The rank of a tensor T is the minimum r such that we can write T as a sum of r rank one tensors. i.e.

$$r = \min_{r} \{ T = \sum^r_{i = 1} u_i \otimes v_i \otimes w_i \otimes \}$$

MAIN QUESTON:

I was told that it was not hard to proof that the rank of the example T I gave at the top is rank 3. I am very new to tensors and was not sure how to approach such a proof or what components it required. I was wondering if someone could help me either start of such a proof with useful hints or provide a proof so that I can learn how to approach how to prove myself what the rank of a tensor is.

I would expect that such a proof would start as, look we can express $T'$ with 3 rank 1 tensors. Then show that its impossible to construct $T'$ exactly with $r < 3$. Though, this impossibility argument seems difficult for me to reason about.

I am aware that computing the rank of a tensor is computationally hard (NP-hard), so maybe the only way to prove its rank 3 is for this particular examples? If that is the case how do I approach this one?

• I'm interested in your question, I'm not sure what the notation you use to define $T$ means. Could you elaborate on the initial notation used to define $T$? – James S. Cook Mar 9 '15 at 17:21
• Sure, give me a second @JamesS.Cook – Pinocchio Mar 9 '15 at 17:27
• Thanks, although, I'm about to go to lunch here, so I may lose my chance to respond pretty soon... – James S. Cook Mar 9 '15 at 17:27
• @JamesS.Cook don't worry. Whenever you get back is cool :) – Pinocchio Mar 9 '15 at 17:28
• @JamesS.Cook just in case you are still here, do you want me to define a tensor more precisely or the example I gave in particular? – Pinocchio Mar 9 '15 at 17:42

To say $T' = \left[ \left[\begin{array}{cc} a & b \\ c & d \end{array} \right] ,\left[\begin{array}{cc}e & f \\ h & h\end{array} \right]\right] = \left[ A,B \right]$ corresponds to defining a tensor $T': \mathbb{R}^2 \times \mathbb{R}^2 \times \mathbb{R}^2 \rightarrow \mathbb{R}$ as follows: for $u,v,w \in \mathbb{R}^2$: where $w = (w^1,w^2)$, $$T(u,v,w) = u^TAvw^1+u^TBvw^2$$ you can check the expression above is linear in $u,v$ and $w$. Thus it is a trilinear mapping which is to say it is a tensor of type $(3,0)$. I can express it as a sum of covectors $e^j(w)=w^j$. Observe: \begin{align} u^TAv = [u^1,u^2]\left[\begin{array}{cc} a & b \\ c & d \end{array} \right]\left[\begin{array}{cc} v^1 \\ v^2 \end{array} \right]&=au^1v^1+bu^1v_2+cu^2v^1+du^2v_2 \\ &=\left(ae^1\times e^1+be^1 \otimes e^2+ce^2\otimes e^1+d e^2 \otimes e^2 \right)(u,v). \\ \end{align} likewise, $$u^TBvw^2 = \left(e e^1\times e^1+f e^1 \otimes e^2+g e^2\otimes e^1+h e^2 \otimes e^2 \right)(u,v).$$ Consequently, as $w^1 = e^1(w)$ and $w^2 = e^2(w)$ we obtain: \begin{align} T(u,v,w) &= \biggl[\left(ae^1\otimes e^1+be^1 \otimes e^2+ce^2\otimes e^1+d e^2 \otimes e^2 \right)\otimes e^1 \\ & \qquad + \left(e e^1\times e^1+f e^1 \otimes e^2+g e^2\otimes e^1+h e^2 \otimes e^2 \right) \otimes e^2 \biggr] (u,v,w) \end{align} Or, dropping the argument and writing the above as a tensor equation: \begin{align} T &= ae^1\otimes e^1 \otimes e^1 +be^1 \otimes e^2\otimes e^1+ce^2\otimes e^1\otimes e^1+d e^2 \otimes e^2 \otimes e^1 \\ & \qquad + e e^1\times e^1 \otimes e^2+f e^1 \otimes e^2 \otimes e^2 +g e^2\otimes e^1 \otimes e^2 +h e^2 \otimes e^2 \otimes e^2. \end{align} You can see $\beta=\{ e^i \otimes e^j \otimes e^j \ | \ 1 \leq i,j,k \leq 2\}$ forms a basis for the set of all tensors of type $(3,0)$ on $\mathbb{R}^2$. This set of tensors has a vector space structure as the sum and scalar products of tensors of type $(3,0)$ is once more a tensor of the same type. Moreover, the dimension of this space of tensors is just $2^3=8$. The coordinate vector of $T$ is simply; $$[T]_{\beta} = (a,b,c,d,e,f,g,h)$$ assuming the natural ordering on $\beta$ as suggested from my work thus far. Each tensor in $\beta$ has rank one (by definition) and the rank of $T$ would be be the minimum dimension of a rank-one-spanned subspace which contains $T$. Here the term "rank-one-spanned" means the subspace is spanned by a set of tensors of rank one. Notice, if you do not force this condition then we can always find a given $T$ in the space spanned by itself, so, this makes rank a problem which is not directly faced by the linear algebra on the space of tensors. We can only consider rank-one bases for the space of tensors as we seek to find the rank of $T$.
Returning to $T'$, we have $a=d=0$, $b=c=1$, $e=h=1$ and $f=g=0$ $$T' = e^1 \otimes e^2\otimes e^1+e^2\otimes e^1\otimes e^1 + e^1\times e^1 \otimes e^2 + e^2 \otimes e^2 \otimes e^2.$$ I can tell you this much already: $rank(T') \leq 4$. How to see this is rank three? How to calculate rank in general. These questions I must ponder. Great question.