4
$\begingroup$

I ask you for this possibly not so simple task:

  • Explicitly construct a 4th-order tensor $A \in \mathbb{C}^{n_1 \times \ldots \times n_4}$ that does not have (border) rank $r$, but for which each matricization does have rank $r$; that is $$\forall J \subset \{1,\ldots,4\},\ |J| \notin \{0,4\}\ :\ r_J := \mathrm{rank}(A^{[J]}) = r,$$ where each $A^{[J]} \in \mathbb{C}^{n_J \times n_{\{1,\ldots,4\} \setminus J}}$ for $n_S := \prod_{s \in S} n_s$ is a simple reshaping into a matrix (see below).

For simplicity, let $n_j = \hat{n} \in \mathbb{N}$ for all $j = 1,\ldots,4$.

You may choose $\hat{n},r \in \mathbb{N}$ as you wish. Convincing numerical evidence is welcome as well.


The following Matlab code displays all relevant matricization ranks:

n = size(A);
r_1 = rank( reshape(A,n(1),[]) )
r_2 = rank( reshape(A,n(2),[]) )
r_3 = rank( reshape(A,n(3),[]) )
r_4 = rank( reshape(A,n(4),[]) )
r_12 = rank( reshape(A,n(1)*n(2),[]) )
r_13 = rank( reshape( permute(A,[1,3,2,4]) ,n(1)*n(3),[]) )
r_14 = rank( reshape( permute(A,[1,4,2,3]) ,n(1)*n(4),[]) )

Note that $\mathrm{rank}(A^{[J]}) = \mathrm{rank}((A^{[J]})^T) = \mathrm{rank}(A^{[\{1,\ldots,d\} \setminus J]})$.

$\endgroup$
2
  • $\begingroup$ Do you really need every matricization to have the exact same rank? Or would it suffice to give a tensor with each matricization having rank $\leq r$, while the tensor itself has rank $> r$? $\endgroup$ Aug 12, 2021 at 13:48
  • $\begingroup$ I suppose that would be fine. However, I would expect this to ultimately be a harder problem. $\endgroup$ Aug 12, 2021 at 14:40

1 Answer 1

1
$\begingroup$

I don't recall papers giving lower bounds on border rank for tensors with more than 3 factors, but we can adapt the constructions from the trilinear case.

If we want an order $4$ tensor with all flattening ranks the same, one way is to take a commutative algebra $R$ and take $A$ to be the tensor corresponding to the iterated multiplication map $A \colon R \times R \times R \to R$ defined as $A(x,y,z) = x\cdot y\cdot z$. If $\dim R = r$, this $r \times r \times r \times r$ tensor will have all flattening ranks also equal to $r$ (you can see this by grouping products in a nice way, for example, the identity $A(x, y, z) = \sum_{i = 1}^r e^i(x\cdot y) (e_i \cdot z)$ will give a rank $r$ decomposition for the $12|34$ flattening rank).

One can argue like in our paper with Markus Bläser "On degeneration of tensors and algebras" and prove that the border rank of such iterated multiplication tensor will be equal to $r$ if and only if the algebra $R$ is smoothable. The simplest non-smoothable algebra is 8-dimensional $\mathbb{C}[x_1,x_2,x_3,x_4]/\left(x_1^2,x_1x_2,x_2^2,x_3^2,x_3x_4,x_4^2,x_1x_4-x_2x_3\right)$ (taken from this paper of Poonen) which gives the tensor $$\begin{aligned} A & = e^{\otimes 4} \\ & + \sum_{i = 1}^4 (x_i \otimes e \otimes e \otimes x_i + e \otimes x_i \otimes e \otimes x_i + e \otimes e \otimes x_i \otimes x_i)\\ & + \sum_{i = 1}^3 (y_i \otimes e \otimes e \otimes y_i + e \otimes y_i \otimes e \otimes y_i + e \otimes e \otimes y_i \otimes y_i)\\ & + x_1 \circ x_3 \circ e \otimes y_1 + x_1 \circ x_4 \circ e \otimes y_2\\ & + x_2 \circ x_3 \circ e \otimes y_2 + x_2 \circ x_4 \circ e \otimes y_3\\ \end{aligned}$$ in $\textrm{span}(e, x_1, x_2, x_3, x_4, y_1, y_2, y_3)^{\otimes 4}$, where $a \circ b \circ c$ is the symmetrized product $a \circ b \circ c = a \otimes b \otimes c + a \otimes c \otimes b + b \otimes c \otimes a + b \otimes a \otimes c + c \otimes a \otimes b + c \otimes b \otimes a$.

The modification proposed by Nathaniel Johnston in the comments is actually easier, as we can just take an order 3 tensor $T$ which has the same property and take $A = v \otimes T$ where $v$ is an arbitrary vector. The flattening ranks would be either $1$ or the same as $T$, and the border rank the same as $T$.

$\endgroup$
3
  • $\begingroup$ Am I counting correctly, the expression for $A$ shows the rank is at most 46? Do you know the exact value of the rank of this $A$, or tensors like it (multiplication maps)? $\endgroup$ Nov 7, 2023 at 13:23
  • 1
    $\begingroup$ I know a lower bound (d - 1)(n - 1) + 1 for similar iterated tensors of order d and size n, it's in our paper arXiv:2211.00652. $\endgroup$ Nov 7, 2023 at 13:57
  • 1
    $\begingroup$ For this specific tensor I see an upper bound of 38, because the rank of $a \circ b \circ c$ is $4$ $\endgroup$ Nov 7, 2023 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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