<p>Testing for constant <em>border</em>-rank can be done in polynomial-time, I'm pretty sure, if you're talking about tensors of fixed arity. More precisely, testing for border-rank <span class="math-container">$\leq r$</span> in <span class="math-container">$\mathbb{C}^{d_1} \otimes \dotsb \otimes \mathbb{C}^{d_k}$</span> can be done in something like <span class="math-container">$k(d_1 d_2 \dotsb d_k)^{2(r+1)}$</span> evaluations of <span class="math-container">$(r+1) \times (r+1)$</span> determinants plus some additional <s>constant work (constant depending on <span class="math-container">$r$</span>).</s> Update 2022-02-10: work of order <span class="math-container">$f(r) \cdot \prod_{i} \binom{d_i}{r}$</span>, so for <span class="math-container">$k,r$</span> constant, this is still polynomial in the <span class="math-container">$\{d_i\}$</span>.</p>
<p>Theorem 3.7.1.1 of <a href="https://rads.stackoverflow.com/amzn/click/com/0821869078" rel="nofollow noreferrer" rel="nofollow noreferrer">Landsberg's tensor book</a> (&quot;Inheritance&quot;) says that the equations for the variety of tensors of border-rank <span class="math-container">$\leq r$</span> in <span class="math-container">$\mathbb{C}^{d_1} \otimes \mathbb{C}^{d_2} \otimes \dotsb \otimes \mathbb{C}^{d_k}$</span> are given by the equations for border-rank <span class="math-container">$r$</span> in <span class="math-container">$\mathbb{C}^r \otimes \mathbb{C}^r \otimes \dotsb \otimes \mathbb{C}^r$</span> (Update 2022-02-10: applied by choosing <span class="math-container">$r$</span> out of the <span class="math-container">$d_i$</span> coordinates in all possible ways) together with all <span class="math-container">$(r+1) \times (r+1)$</span> minors of flattenings. Since <span class="math-container">$r = O(1)$</span>, there are only <s>finitely</s> polynomially many equations of the former type.</p>
<p>Border-rank 1 = rank 1, and more generally rank <span class="math-container">$\leq r$</span> implies border-rank <span class="math-container">$\leq r$</span>. But border-rank 2 can have rank anywhere from <span class="math-container">$2$</span> to the arity <span class="math-container">$k$</span>, and border-rank <span class="math-container">$3$</span> in arity 3 can have ranks 3, 4, or 5. Beyond that I don't know about testing for rank.</p>

CC BY-SA 3.0
2013-10-25T21:53:18.647Z
Yes, fixed arity.  This book looks great.  The naive system of polynomial equations to check for rank at most $r$ (for arity $k$ and $d = d_1 = \dotsb d_k$) has $d r$ variables in $d^k$ equations, each of degree $k$ with $r$ monomials.  Are the equations for the variety of tensors of border-rank $\le r$ significantly simpler than this?
Tyson Williams
CC BY-SA 3.0
2013-10-26T15:07:03.260Z
If you're talking about the naive equations you get by expressing a variable rank-r tensor and then setting it = to your tensor $T$, then there's a key difference. In that setting, you setup a system of equations that depend on $T$, and then check if the system has a solution. In the equations for border-rank I was talking about, you simply plug the coordinates of your tensor into the equations and make sure they all evaluate to zero. For fixed $r$ and $k$, the only equations that aren't of O(1) size are determinants, so are easy to evaluate.
Joshua Grochow
CC BY-SA 3.0
2013-10-26T15:09:10.693Z
Note: checking if a system of equations over $\mathbb{Z}$ has a solution in $\mathbb{C}$ is in PSPACE unconditionally and in PH assuming the generalized Riemann hypothesis. In the Blum-Shub-Smale model (or even the usual Boolean model, if working over finite fields), solving systems of equations is NP-complete. So this seems much harder than merely evaluating equations, as in the case of border-rank.
Joshua Grochow
CC BY-SA 3.0
2013-10-30T20:09:11.150Z
For others reading this question, the [first two chapters of Landsberg's book](http://www.math.tamu.edu/~jml/Tbookintro.pdf) are available online.
Tyson Williams
CC BY-SA 3.0
2013-11-01T01:43:52.680Z
Oh, the "naive system of polynomials" I spoke about in my first comment is for checking symmetric (aka Waring) rank.
Tyson Williams
CC BY-SA 4.0
2013-10-24T16:53:03.517Z
2023-02-11T03:44:40.140Z
2023-02-11T03:44:40.140Z
Joshua Grochow
<p>This question is related to a previous unanswered <a href="https://cstheory.stackexchange.com/questions/7903/complexity-of-tensor-rank-over-an-infinite-field">question</a> of mine.  Please see that question for background.</p>

<p>When Håstad <a href="http://www.nada.kth.se/~johanh/tensorrank.pdf" rel="nofollow noreferrer">proved</a> that computing tensor rank is NP-complete, the rank in question was allowed to be part of the input.  Specifically, given a Boolean formula with $n$ variables and $m$ clauses, Håstad constructed a tensor that has rank exactly $4n+2m$ if the formula is satisfiable and has some larger rank otherwise.</p>

<p>What if we fix the bound on the rank to some constant?  For example...</p>

<blockquote>
  <p>What is the complexity of deciding if a tensor has rank at most 3?</p>
</blockquote>

<p>The tensor should be defined over an infinite field, otherwise the problem is trivial (...only a finite number of things to check).  Answers for the natural infinite fields $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ would be best.  I am personally interested in this question using the complex numbers.</p>

<ds.algorithms><reference-request><tensor-rank>
Deciding bound on Tensor Rank for a fixed value
Tyson Williams
# Deciding bound on Tensor Rank for a fixed value

(Asked by: username_0 on 2013-10-24)

This question is related to a previous unanswered [question](https://cstheory.stackexchange.com/questions/7903/complexity-of-tensor-rank-over-an-infinite-field) of mine. Please see that question for background.

When Håstad [proved](http://www.nada.kth.se/~johanh/tensorrank.pdf) that computing tensor rank is NP-complete, the rank in question was allowed to be part of the input. Specifically, given a Boolean formula with $n$ variables and $m$ clauses, Håstad constructed a tensor that has rank exactly $4n+2m$ if the formula is satisfiable and has some larger rank otherwise.

What if we fix the bound on the rank to some constant? For example...

> What is the complexity of deciding if a tensor has rank at most 3?

The tensor should be defined over an infinite field, otherwise the problem is trivial (...only a finite number of things to check). Answers for the natural infinite fields $\mathbb{Q}$, $\mathbb{R}$, and $\mathbb{C}$ would be best. I am personally interested in this question using the complex numbers.

**Tags:** ds.algorithms, reference-request, tensor-rank


---

## 1 answers

### Answer by username_1 on 2013-10-24. Score: 8

Testing for constant *border*-rank can be done in polynomial-time, I'm pretty sure, if you're talking about tensors of fixed arity. More precisely, testing for border-rank $\leq r$ in $\mathbb{C}^{d\_1} \otimes \dotsb \otimes \mathbb{C}^{d\_k}$ can be done in something like $k(d\_1 d\_2 \dotsb d\_k)^{2(r+1)}$ evaluations of $(r+1) \times (r+1)$ determinants plus some additional ~~constant work (constant depending on $r$).~~ Update 2022-02-10: work of order $f(r) \cdot \prod\_{i} \binom{d\_i}{r}$, so for $k,r$ constant, this is still polynomial in the $\{d\_i\}$.

Theorem 3.7.1.1 of [Landsberg's tensor book](https://rads.stackoverflow.com/amzn/click/com/0821869078) ("Inheritance") says that the equations for the variety of tensors of border-rank $\leq r$ in $\mathbb{C}^{d\_1} \otimes \mathbb{C}^{d\_2} \otimes \dotsb \otimes \mathbb{C}^{d\_k}$ are given by the equations for border-rank $r$ in $\mathbb{C}^r \otimes \mathbb{C}^r \otimes \dotsb \otimes \mathbb{C}^r$ (Update 2022-02-10: applied by choosing $r$ out of the $d\_i$ coordinates in all possible ways) together with all $(r+1) \times (r+1)$ minors of flattenings. Since $r = O(1)$, there are only ~~finitely~~ polynomially many equations of the former type.

Border-rank 1 = rank 1, and more generally rank $\leq r$ implies border-rank $\leq r$. But border-rank 2 can have rank anywhere from $2$ to the arity $k$, and border-rank $3$ in arity 3 can have ranks 3, 4, or 5. Beyond that I don't know about testing for rank.

> **Comments:**
> **username_0**: Yes, fixed arity.  This book looks great.  The naive system of polynomial equations to check for rank at most $r$ (for arity $k$ and $d = d_1 = \dotsb d_k$) has $d r$ variables in $d^k$ equations, each of degree $k$ with $r$ monomials.  Are the equations for the variety of tensors of border-rank $\le r$ significantly simpler than this?  
> **username_1**: If you're talking about the naive equations you get by expressing a variable rank-r tensor and then setting it = to your tensor $T$, then there's a key difference. In that setting, you setup a system of equations that depend on $T$, and then check if the system has a solution. In the equations for border-rank I was talking about, you simply plug the coordinates of your tensor into the equations and make sure they all evaluate to zero. For fixed $r$ and $k$, the only equations that aren't of O(1) size are determinants, so are easy to evaluate.  
> **username_1**: Note: checking if a system of equations over $\mathbb{Z}$ has a solution in $\mathbb{C}$ is in PSPACE unconditionally and in PH assuming the generalized Riemann hypothesis. In the Blum-Shub-Smale model (or even the usual Boolean model, if working over finite fields), solving systems of equations is NP-complete. So this seems much harder than merely evaluating equations, as in the case of border-rank.  
> **username_0**: For others reading this question, the [first two chapters of Landsberg's book](http://www.math.tamu.edu/~jml/Tbookintro.pdf) are available online.  
> **username_0**: Oh, the "naive system of polynomials" I spoke about in my first comment is for checking symmetric (aka Waring) rank.  

---

