Can anyone help me find the rank and border rank of the following tensor:
\begin{align} T=a_{11}\otimes b_{11}\otimes c_{11}+a_{12}\otimes b_{21}\otimes c_{11}+a_{11}\otimes b_{12}\otimes c_{12}\\ +a_{12}\otimes b_{22}\otimes c_{12}+a_{21}\otimes b_{11}\otimes c_{21}+a_{21}\otimes b_{12}\otimes c_{22} \end{align}
It's the product of two matrices $\mathit{A}$ and $\mathit{B}$ where the entry in the last column and the last row of matrix $\mathit{A}$ i.e. $a_{22}$ equals zero(given by Bini). I know the answer, but I do not understand the procedure.
This question is very, very old, but nevertheless I think an answer might help people coming across. The Bini tensor is an excellent tensor to demonstrate some basic techniques to investigate rank and border rank for tensors.
Let $A$, $B$ and $C$ be finite dimensional, complex vector spaces.
First, recall that the rank $R(T)$ of a tensor $T \in A\otimes B \otimes C$ is defined as the minimal $r$ such that there exists vectors $u_1, \dots , u_r \in A$, $v_1, \dots , v_r \in B$ and $w_1, \dots w_r \in C$ such that $$T = \sum_{i=1}^r u_i \otimes v_i \otimes w_i$$
The border rank $\underline{R}(T)$ is the minimal $r$ such that $$T = \lim_{\epsilon \rightarrow 0} T_\epsilon$$ where $R(T_\epsilon) \leq r$ for all $\epsilon > 0$ (the limit can be taken for example in the Euclidean norm).
Fact 1: By definition, it is clear that local linear maps cannot enlarge the rank: For $T \in A \otimes B\otimes C$ and linear maps $M_A: A \rightarrow A'$, $M_B: B \rightarrow B'$ and $M_C: C \rightarrow C'$ we have $$R(T) \geq R\left((M_A\otimes M_B\otimes M_C) T\right)$$ The same holds true for the border rank.
Fact 2: A tensor $T \in A\otimes B \otimes C$ naturally defines a linear map $T_A : A^* \rightarrow B\otimes C$: For $T = \sum_{i=1}^r u_i \otimes v_i \otimes w_i$, define $T_A(\alpha) = \sum_{i=1}^r \alpha(u_i) \cdot v_i \otimes w_i$. This is called a flattening. With the same procedure, we also get linear maps $T_B$ and $T_C$. Every simple tensor of the form $a\otimes b \otimes c$ leads to a linear map of rank 1. Therefore, the rank of a flattening map of a tensor of rank $\leq r$ is at most $r$. That is, $R(T) \geq rank(T_A)$. The same is true for $T_B$ and $T_C$. Indeed, the same holds for border rank and since for linear maps the rank is lower semicontinuous, we have $\underline{R}(T) \geq rank(T_A)$.
Let us now think about our specific tensor: Let $\lbrace a_{11}, a_{12}, a_{21} \rbrace$ be a basis of $A$ and similarly $\lbrace b_{11}, b_{12}, b_{21}, b_{22} \rbrace$ and $\lbrace c_{11}, c_{12}, c_{21}, c_{22} \rbrace$ bases for $B$ and $C$ and define
\begin{align} T_{Bini}=a_{11}\otimes b_{11}\otimes c_{11}+a_{12}\otimes b_{21}\otimes c_{11}+a_{11}\otimes b_{12}\otimes c_{12}\\ +a_{12}\otimes b_{22}\otimes c_{12}+a_{21}\otimes b_{11}\otimes c_{21}+a_{21}\otimes b_{12}\otimes c_{22} \end{align}
Since it is written as a sum of $6$ simple tensors, its rank is at most $6$: $R(T_{Bini}) \leq 6$.
We will now show that it is exactly 6.
Proposition 1: $R(T_{Bini})\geq 6$ and consequently, $R(T_{Bini}) = 6$.
Proof: Assume it has actually rank at most 5, so we can write it as
$$T_{Bini} = u_1\otimes v_1 \otimes w_1 + \dots + u_5\otimes v_5 \otimes w_5$$
Clearly, if we write the $v_k$ as linear combinations of the basis vectors $b_{ij}$, for one of them the coefficient of $b_{21}$ is non-zero (else, we would never get the summand $a_{12}\otimes b_{21}\otimes c_{11}$). Say without loss of generality that $$v_1 = c_1 b_{21} + w_1$$ for $w_1 \in \text{span}(b_{11}, b_{12}, b_{22})$ and $c_1 \neq 0$.
Define the linear map
$$M_1 : B \rightarrow B, b_{ij} \mapsto \begin{cases}b_{ij} &\text{ if } (i,j) \neq (2,1) \\ -\frac{1}{c_1}w_1 &\text{ else}\end{cases}$$
By construction, $M_1(v_1) = 0$, so,
$$(\text{id} \otimes M_1 \otimes \text{id}) T_{Bini} = u_2\otimes M_1(v_2) \otimes w_2 + \dots + u_5\otimes M_1 (v_5) \otimes w_5$$ has tensor rank at most 4. By definition of $M_1$, we also have \begin{align} (\text{id} \otimes M_1 \otimes \text{id})T_{Bini}=a_{11}\otimes b_{11}\otimes c_{11}+a_{12}\otimes M_1(b_{21})\otimes c_{11}+a_{11}\otimes b_{12}\otimes c_{12}\\ +a_{12}\otimes b_{22}\otimes c_{12}+a_{21}\otimes b_{11}\otimes c_{21}+a_{21}\otimes b_{12}\otimes c_{22} \end{align} Again, we see that one of the vectors $M_1 (v_i)$ must have a non-zero $b_{22}$-coefficient. Else, the summand $a_{12}\otimes b_{22}\otimes c_{12}$ could not be there.
Now, the same strategy can be used to decrease the rank again: Without loss, assume $$M_1(v_2) = c_2 b_{22} + w_2$$ $w_2 \in \text{span}(b_{11}, b_{12}, b_{21})$ and $c_2 \neq 0$ and define $$M_2 : B \rightarrow B, b_{ij} \mapsto \begin{cases}b_{ij} &\text{ if } (i,j) \neq (2,2) \\ -\frac{1}{c_2}w_2 &\text{ else}\end{cases}$$
This has $M_1(v_2)$ in its kernel, therefore $$(\text{id} \otimes M_2 \otimes \text{id})(\text{id} \otimes M_1 \otimes \text{id}) T_{Bini} = u_3\otimes M_2(M_1(v_3)) \otimes w_3 + \dots + u_5\otimes M_2(M_1 (v_5)) \otimes w_5$$ has rank at most 3.
Note that this tensor now is of the form \begin{align} (\text{id} \otimes M_2 \otimes \text{id})(\text{id} \otimes M_1 \otimes \text{id})T_{Bini}=a_{11}\otimes b_{11}\otimes c_{11}+a_{12}\otimes M_2(M_1(b_{21}))\otimes c_{11}+a_{11}\otimes b_{12}\otimes c_{12}\\ +a_{12}\otimes M_2(b_{22})\otimes c_{12}+a_{21}\otimes b_{11}\otimes c_{21}+a_{21}\otimes b_{12}\otimes c_{22} \end{align}
Now, we see why it was good that we chose $b_{21}$ and $b_{22}$ for the above procedure: The maps we applied only affect summands in this decomposition that "start" with $a_{12}$. So, by projecting out $a_{12}$ by using a local map on the first vector space, we can get rid of all terms with $M_i$'s and get a tensor which is supposed to have rank at most 3.
More formally, define the projector $$\Pi : A \rightarrow A, a_{ij} \mapsto \begin{cases} a_{ij} &\text{ if } (i,j) \neq (1,2) \\ 0 &\text{ else}\end{cases}$$
Then, by Fact 2, \begin{align} S :=(\Pi \otimes \text{id} \otimes \text{id})(\text{id} \otimes M_2 \otimes \text{id})(\text{id} \otimes M_1 \otimes \text{id})T_{Bini}=a_{11}\otimes b_{11}\otimes c_{11}+a_{11}\otimes b_{12}\otimes c_{12}\\ +a_{21}\otimes b_{11}\otimes c_{21}+a_{21}\otimes b_{12}\otimes c_{22} \end{align} has rank at most 3.
But we can observe that the flattening $S_C$ has image $$\text{span}(a_{11}\otimes b_{11},a_{11}\otimes b_{12}, a_{21}\otimes b_{11}, a_{21}\otimes b_{12} )$$ which is four dimensional as span of four linearly independent vectors. By Fact 2, the tensor $S$ therefore has rank at least 4 - a contradiction. $\square$
Remark: This proof method is a standard method to prove lower bounds on tensor rank and is called substitution method. The reason why this is called substitution method can be found for example in these lecture notes by Markus Bläser.
Exercise: Show with the exact same method that the so-called $W$-tensor $W = a_1 \otimes b_1 \otimes c_2 + a_1 \otimes b_2 \otimes c_1 + a_2 \otimes b_1 \otimes c_1$ has rank 3. This is an excellent exercise to convince yourself that you understood how the above proof works.
We now know the rank of $T_{Bini}$. Let's think about border rank now.
Proposition 2: $\underline{R}(T_{Bini}) \leq 5$
Proof: For every $\epsilon > 0$, let \begin{align} T(\epsilon) =\frac{1}{\epsilon}[& \left(\epsilon a_{11}+a_{21}\right)\otimes b_{12}\otimes \left(c_{12}+\epsilon c_{22}\right)+\\ & \left(\epsilon a_{11}+a_{12}\right)\otimes\left(b_{11}+\epsilon b_{21}\right) \otimes c_{11}-\\ & a_{21}\otimes \left(b_{11}+b_{12} + \epsilon b_{22}\right)\otimes c_{12} -\\ & a_{12}\otimes b_{11}\otimes\left(c_{11} + c_{12} +\epsilon c_{21}\right) +\\ & \left( a_{12}+a_{21}\right)\otimes\left(b_{11}+\epsilon b_{22}\right) \otimes \left(c_{12}+\epsilon c_{21}\right)]\\ \end{align} For every fixed $\epsilon >0$, this is a tensor of rank at most 5. A direct calculation shows that $$T(\epsilon) = T_{Bini} + \epsilon \cdot T'$$ for some tensor $T'$, consequently, $$\lim_{\epsilon \rightarrow 0} T(\epsilon) = T_{Bini}$$ which shows $\underline{R}(T_{Bini}) \leq 5$.$\square$
The last thing we need to do is to show that $\underline{R}(T_{Bini}) \geq 5$. This is a bit more difficult and requires some more involved techniques called Strassen's equations. This technique is a quite powerful variation of Fact 2. I took everything that follows from this book by JM Landsberg.
For that we need some very basic facts about antisymmetric tensors. Generally, we see that for a complex vector space $A$, the permutation group $\mathfrak{S}_n$ acts on $A^{\otimes n}$. For $\sigma \in \mathfrak{S}_n$ we define a linear map $M_\sigma$ by linearly extending $$M_\sigma : u_1 \otimes \dots \otimes u_n \mapsto u_{\sigma(1)} \otimes \dots \otimes u_{\sigma(n)}$$ to the whole space.
We can define the space $\Lambda^n A$ of antisymmetric tensors in $A^{\otimes n}$ via $$\Lambda^nA = \lbrace T \in A^{\otimes n}: M_\sigma(T) = \text{sgn}(\sigma)\cdot T \;\;\forall \sigma \in \mathfrak{S}_n\rbrace$$ For $n = 2$, we have the following projection map projecting onto the antisymmetric space: $$\Pi^\Lambda : A^{\otimes 2} \rightarrow \Lambda^2 A , u_1 \otimes u_2 \mapsto u_1 \wedge u_2 := \frac{1}{2} (u_1 \otimes u_2 - u_2 \otimes u_1) $$ It can be shown that for a $n$ dimensional space $A$ with basis $\lbrace a_1, \dots , a_n \rbrace$, the space $\Lambda^2 A$ has the set $\lbrace a_i \wedge a_j: 1 \leq i < j \leq n \ \rbrace$ as a basis.
Enough about antisymmetric spaces. Recall from Fact 2 that every tensor $T \in A \otimes B \otimes C$ induces a linear map $T_B : B^* \rightarrow A \otimes C$. Note that we can blow up this map a bit by tensoring it with an identity map: $\text{id}_A \otimes T_B : A \otimes B^* \rightarrow A \otimes A \otimes C$. We define the map $$T^\wedge_A = \left( \Pi^\Lambda \otimes \text{id}_C \right) \left( \text{id}_A \otimes T_B\right): A \otimes B^* \rightarrow \left(\Lambda^2A \right) \otimes C$$ How does that look like for a rank one tensor $T = u \otimes v \otimes w\in A \otimes B \otimes C$? There, $$T^\wedge_{A} (x \otimes \beta) = \beta(v) \cdot (x\wedge u) \otimes w$$ for $x \in A$ and $\beta \in B^*$.
If we define a basis of $A$ having the vector $u\in A$ as an element, say $\lbrace u, u_2, \dots, u_n\rbrace$, it is not hard to see that the $(u_i \wedge u)\otimes w$ are linearly independent for $i = 2, \dots , n,$ so we have that $T^\wedge_A$ has rank $n-1$ as a linear map.
For tensors $T_1$ and $T_2$ both in $A \otimes B \otimes C$ we observe that $\left( T_1 + T_2 \right)^\wedge_A = \left( T_1 \right)^\wedge_A + \left( T_2\right)^\wedge_A$ we consequently for a tensor with rank $R(T) = r$ the linear map $T^\wedge_A$ will have rank at most $r\cdot(n -1)$. Since the rank of linear maps is lower semicontinuous, we even know for $\underline{R}(T) = r$ that $T^\wedge_A$ has rank at most $r\cdot(n-1)$. Conclusion: if we calculate the rank of the linear map $T^\wedge_A$, we might be able to lower bound the border rank of $T$!
Indeed, this let's us now finish our little analysis of the Bini tensor:
Proposition 3: $\underline{R}(T) \geq 5$ and therefore $\underline{R}(T) = 5$.
Proof: Let $r = \underline{R}(T)$ be the border rank of the Bini tensor. By the above discussion, the rank of the linear map $T^\wedge_A$ will be bounded from above by $r \cdot (3-1) = 2\cdot r$. We will now show that $T^\wedge_A$ has rank 10 which proves $2\cdot r \geq 10$, or equivalently, $\underline{R}(T) \geq 5$.
From our basis $\lbrace b_{11}, b_{12}, b_{21}, b_{22}\rbrace$ of $B$ we naturally get a basis $\lbrace \beta_{11}, \beta_{12}, \beta_{21}, \beta_{22}\rbrace$ of $B^*$ by defining $$\beta_{ij}(b_{kl}) = \begin{cases}1 &\text{ if } (i,j) = (k,l)\\ 0 &\text{ else}\end{cases}$$
Our map $T^\wedge_A$ does the following: \begin{align} T^\wedge_A ( a_{ij} \otimes \beta_{kl}) = &\beta_{kl} (b_{11}) \left((a_{ij} \wedge a_{11}) \otimes c_{11}\right)+ \\ &\beta_{kl} (b_{21}) \left((a_{ij} \wedge a_{12}) \otimes c_{11}\right)+ \\ &\beta_{kl} (b_{12}) \left((a_{ij} \wedge a_{11}) \otimes c_{12}\right)+ \\ &\beta_{kl} (b_{22}) \left((a_{ij} \wedge a_{12}) \otimes c_{12}\right)+ \\ &\beta_{kl} (b_{11}) \left((a_{ij} \wedge a_{21}) \otimes c_{21}\right)+ \\ &\beta_{kl} (b_{12}) \left((a_{ij} \wedge a_{21}) \otimes c_{22}\right) \end{align}
Probably, the easiest way to check the rank of this linear map is to fix bases and write it as a matrix. For $A \otimes B^*$, we have a basis basis $$a_{11} \otimes \beta_{11}, \dots, a_{11} \otimes \beta_{22}, a_{12} \otimes \beta_{11}, \dots a_{12} \otimes \beta_{22}, a_{21} \otimes \beta_{11} \dots , a_{21} \otimes \beta_{22}$$ and for $(\Lambda^2A) \otimes C$, we have a basis $$(a_{11}\wedge a_{12})\otimes c_{11}, \dots ,(a_{11}\wedge a_{12})\otimes c_{22}, (a_{11}\wedge a_{21})\otimes c_{11}, \dots , (a_{11}\wedge a_{21})\otimes c_{22}, (a_{12}\wedge a_{21})\otimes c_{11}, \dots, (a_{12}\wedge a_{21})\otimes c_{22}$$
In these bases, we have e.g. $$T^\wedge_A:\begin{pmatrix}1 \\ 0 \\ \vdots \\ 0 \end{pmatrix} = a_{11} \otimes \beta_{11} \mapsto (a_{11}\wedge a_{21})\otimes c_{21} = \begin{pmatrix}0\\\vdots \\0\\1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$$ where the image is the seventh basis vector and has the 1 in the seventh position. By doing that for all 12 basis vectors, we see that the linear map is in these bases represented by the matrix $$\begin{pmatrix} & & & & & & & & & & & \\ & & 1& &-1& & & & & & & \\ & & & 1& &-1& & & & & & \\ & & & & & & & & & & & \\ & & & & & & & &-1& & & \\ & & & & & & & & &-1& & \\ 1& & & & & & & & & & & \\ & 1& & & & & & & & & & \\ & & & & & & & & & &-1& \\ & & & & & & & & & & &-1\\ & & & & 1& & & & & & & \\ & & & & & 1& & & & & & \\ \end{pmatrix}$$
which is a $12\times 12$ matrix and has rank 10. Therefore, we are done. $\square$
Remark: We said this method is known as Strassen's equations. But where are the equations? For this, we make a little detour to algebraic geometry. Define $$\sigma_r = \lbrace T \in A \otimes B \otimes C: R(T) \leq r \rbrace \subset A \otimes B \otimes C$$ and let $\overline{\sigma_r}$ be the closure of $\sigma_r$ in the Zariski topology. Clearly, the question if $R(T) \leq r$ is equivalent to the question if $T\in \sigma_r$. As it turns out, the question if $\underline{R}(T) \leq r$ is also equivalent to the question $T \in \overline{\sigma_r}$. To show that a tensor has border rank at least $r$, it is therefore enough to show that $T \notin \overline{\sigma_{r-1}}$. As $\overline{\sigma_r}$ are Zariski closed, there are polynomials $p_1, \dots , p_k$ on $A\otimes B\otimes C$ such that $$\overline{\sigma_r} = \lbrace T \in A \otimes B \otimes C: p_1(T) = 0, \dots , p_k(T) = 0 \rbrace $$ To show that $T \notin \overline{\sigma_r}$, we can in principle always find a polynomial $p$ on $A\otimes B \otimes C$ such that $p$ vanishes on all $\overline{\sigma_r}$ but not on $T$. In the above example, all $10\times 10$-minors of $T^\wedge_A$ vanish on $\overline{\sigma_4}$ but some not on $T$. This explains the name a bit.
This is a self-contained analysis of this specific tensor. One can learn much more about this topic in the lecture notes Fast Matrix Multiplication by Markus Bläser. They are written more from a computer science perspective which is quite different from the language we used in this answer. I found them very instructive and can highly recommend them.
Much more about lower bounds on the border ranks and the geometry of tensor decompositions can be found in the book Geometry and Complexity Theory by JM Landsberg. It is an excellent book and covers a gigantic amount of topics.