Sum of low rank tensors

Question

How high can the sum of $k$ low rank $m\times m\times\dots \times m$ tensors of rank $t$ be? Is there a good upper bound?

Answer 1

Rank $t$ means $t$ (but no more) linearly independent rows/columns. If those $t$ that are linearly independent in the first matrix are also linearly independent to $t$ of those independent in the second one, you get rank $2t$, and so on.

Therefore, your answer is $r_{MAX} = \min \{ m, kt \}$.

Without knowing anything more about these matrices, their sum will have rank anywhere between $0$ and $r_{MAX}$.

Answer 2

The best upper bound is $\min\{m, kt\}$. This bound can be realised.

For $1 \leq i \leq k$, let $E_i$ be the $m\times m$ matrix with ones in the $(i-1)k+1, (i-1)k+2, \dots, ik$ entries on the main diagonal (all of the numbers taken $\operatorname{mod} m$ so that they are elements of $\{1, \dots, m\}$) and zeroes elsewhere. Note that each $E_i$ has rank $k$ (provided $k \leq m$) and the sum of these matrices has rank $\min\{kt, m\}$.