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 \}$$


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?

  • $\begingroup$ 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$? $\endgroup$ – James S. Cook Mar 9 '15 at 17:21
  • $\begingroup$ Sure, give me a second @JamesS.Cook $\endgroup$ – Pinocchio Mar 9 '15 at 17:27
  • $\begingroup$ Thanks, although, I'm about to go to lunch here, so I may lose my chance to respond pretty soon... $\endgroup$ – James S. Cook Mar 9 '15 at 17:27
  • $\begingroup$ @JamesS.Cook don't worry. Whenever you get back is cool :) $\endgroup$ – Pinocchio Mar 9 '15 at 17:28
  • $\begingroup$ @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? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.