6
$\begingroup$

For simplicity, work over $\mathbb F_2$ and only consider order-$3$ equilateral tensors. For $r\in\mathbb Z_{>0}$, how many tensors $\mathfrak{T}\in\mathsf{Ten}_{n}^{\otimes 3}(\mathbb F_2)$ are there of tensor rank $r$? ($\mathfrak{T}$ is Gothic $T$.) Here $\mathsf{Ten}_n^{\otimes 3}(\mathbb F_2)$ denotes the set of all $n\times n\times n$ tensors over $\mathbb F_2$. In general, the tensor rank of a tensor $\mathfrak{T}\in\mathsf{Ten}_{\ell,m,n}(\mathbb F)$ is defined as $$\mathrm{trk}(\mathfrak{T})=\min\left\{r\in\mathbb Z_{>0}\colon\mathfrak{T}=\sum_{i=1}^r\vec{u}\otimes\vec{v}\otimes \vec{w} \text{ for }\vec u\in\mathbb F^\ell,\vec v\in\mathbb F^m,\vec w\in\mathbb F^n\right\}.$$

The same question is easy for matrices over $\mathbb F_2$ (and indeed over finite field of any characteristic). Note that picking an $r$-dimensional subspace of $\mathbb F_2^n$ can be thought as picking a rank $r$ matrix of size $n\times k$ for some $n\ge k\ge r$ (for the current purpose, take $k=n$), modulo picking a $k\times r$ matrix of rank $r$. $$\# r\text{-dim subspaces}=\frac{\#n\times k\text{ matrices of rank }r}{\#k\times r\text{ matrices of rank }r}.$$

The number of $r$-dimensional subspaces is given by the famous Gaussian binomial coefficient $\begin{bmatrix}n\\r\end{bmatrix}_2$. The number of full column-rank $k\times r$ matrix ($k>r$) can be obtained by sequentially picking its columns so that the $i$-th column is linearly independent of the first $i-1$ columns. This gives $\prod_{i=0}^{r-1}(2^k-2^i)$. Hence the number of rank-$r$ $n\times k$ matrices is $$\begin{bmatrix}n\\r\end{bmatrix}_2\cdot \prod_{i=0}^{r-1}(2^k-2^i)=\prod_{i=0}^{r-1}\frac{(2^n-2^i)(2^k-2^i)}{2^r-2^i}.$$

I do not see how to apply such an idea to tensors. For one thing, we can think a tensor as generating a vector space of matrices. Some people call it a slice space of the tensor (cf. page 2 of this paper). However, there does not seem to be a higher order notion of Gaussian coefficient for a subspace of $\mathsf{Mat}_{n\times n}(\mathbb F_2)$. For another thing, tensors have different directions. By that I mean, an order-$3$ tensor has three directions. We cannot pick sequentially two-dimensional slices, i.e., three $n\times n$ matrices, and claim that the tensor rank is bounded desiredly.

My question is: how can one count the number of $\ell\times m\times n$ tensors over $\mathbb F_q$ of rank $r$?

$\endgroup$
  • 1
    $\begingroup$ This is almost surely extraordinarily difficult, right? I don't think we even know the largest possible value of r. That is, we don't even know how to determine whether there are $0$ or $\geq 1$ tensors of a given rank r, much less how to count exactly how many of them there are. $\endgroup$ – Nathaniel Johnston Apr 24 at 14:39
  • 1
    $\begingroup$ For a small result in this direction, see page 18 of math.wisc.edu/~svs/talks/2011/finitefield.pdf. $\endgroup$ – Richard Stanley Apr 24 at 19:28
  • 1
    $\begingroup$ @NathanielJohnston Thank you Nathaniel. I think you are right. en.wikipedia.org/wiki/Tensor_rank_decomposition#Maximum_rank -- unlike matrix rank which is obviously bounded by the dimension of the matrix, the maximum rank of a tensor is unknown and we do not even have a conjecture for that. However, according to wiki, this is the situation over $F\in\{\mathbb R,\mathbb C\}$. Since the tensor rank heavily relies on the underlying field, do you know whether anything more is known over $\mathbb F_q$? Even knowing a tensor rank bound would be somewhat good to me. $\endgroup$ – Yihan Zhang Apr 25 at 0:07
1
$\begingroup$

This seems difficult. Deciding if a tensor has rank $\leq r$ (over a fixed finite field) is $\mathsf{NP}$-complete (Hastad, 1990). I haven't checked recently, but surely it's also the case that counting the number of ways to write a given tensor as a sum of $r$ rank-one tensors is $\mathsf{\# P}$-complete. Such counts are the size of the fibers of the natural map from r-tuples of rank-1 tensors onto the space of tensors of rank $\leq r$, which would be at least one analogue of trying to count them the way you did for rank $r$ matrices.

Note that, unlike matrices, the space of tensors of rank $r$ has many orbits of the natural group action (of $GL_n \times GL_n \times GL_n$), whereas for matrices the set of matrices of a given rank is a single orbit. Counting the number of these orbits also seems hard. (In particular, deciding whether two tensors are in the same orbit is at least as hard as Graph Isomorphism, Code Equivalence, and several even harder isomorphism problems, so we might expect that counting isomorphism types of tensors of rank $r$ - for $r$ sufficiently large* - should be at least as hard as counting isomorphism types of graphs. The complexity of the latter problem is not known, but again, seems hard, see, e.g., this question.)

* For $r=1$ and 2 it should not be too hard to count. Maybe even for the next few values. But even relatively small $r$ - maybe 5 or 6 is enough? maybe 10? - I expect this to already be difficult.

$\endgroup$
  • $\begingroup$ Thank you Joshua. Indeed the hardness results do not appear surprising to me. For instance the title of this paper sort of says everything. I also agree with your algebraic interpretation. GI can be formulated as checking whether two matrices are in the same orbit which is no harder than the tensor version. $\endgroup$ – Yihan Zhang Apr 25 at 1:03
  • $\begingroup$ However, I do not care about complexity. What I want is some formula for this number which is ``reasonably" easy to use. For instance, counting independent set is #P-complete, but the number of independent sets is given by a nice polynomial. Evaluating that is certainly hard but sometimes that is good enough for some mathematical reasoning. $\endgroup$ – Yihan Zhang Apr 25 at 1:07
  • $\begingroup$ Sure, i see. But note that this analogy is off by a level of abstraction. Each graph has an independence poly counting the ind sets in that graph; what you're asking for is more like a formula for the number of graphs with a given property. While this may be given by a poly in q (or, more likely, a quasi-poly?), it seems hard to find and not so easy to work with. It is probably not much easier to work with than counting points on a general variety... $\endgroup$ – Joshua Grochow Apr 25 at 1:38
  • 1
    $\begingroup$ Hmm, fair enough. Actually my motivation comes from coding theory. Classic coding theory is (roughly) about packing vectors over $\mathbb F_q$ in Hamming metric or packing vectors over $\mathbb R$ in Euclidean metric. It turns out similar packing questions can be posed for matrices over $\mathbb F_q$ in rank metric $d(\mathbf{A},\mathbf{B})=\mathrm{rk}(\mathbf A-\mathbf B)$. Such codes find applications in network coding. I think a natural generalization would be packing tensors in tensor rank metric. I am not aware of any application but maybe it is of independent interest. $\endgroup$ – Yihan Zhang Apr 25 at 4:00
  • 1
    $\begingroup$ Fundamental to packing questions is balls in the metric we are interested in. Unfortunately it seems we are not even close to understanding the volume of ball in tensor rank metric. $\endgroup$ – Yihan Zhang Apr 25 at 4:02

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.