  Obtaining superlinear lower bounds on tensor rank is a major open problem in
complexity theory. In this paper we propose a generalization of the approach
used by Strassen in the proof of his 3n/2 border rank lower bound. Our approach
revolves around a problem on commuting matrices:
  Given matrices Z_1,...,Z_p of size n and an integer r>n, are there commuting
matrices Z'_1,...,Z'_p of size r such that every Z_k is embedded as a submatrix
in the top-left corner of Z'_k?
  As one of our main results, we show that this question always has a positive
answer for r larger than rank(T)+n, where T denotes the tensor with slices
Z_1,..,Z_p. Taking the contrapositive, if one can show for some specific
matrices Z_1,...,Z_p and a specific integer r that this question has a negative
answer, this yields the lower bound rank(T) > r-n. There is a little bit of
slack in the above rank(T)+n bound, but we also provide a number of exact
characterizations of tensor rank and symmetric rank, for ordinary and symmetric
tensors, over the fields of real and complex numbers. Each of these
characterizations points to a corresponding variation on the above approach. In
order to explain how Strassen's theorem fits within this framework we also
provide a self-contained proof of his lower bound.
