The complexity of tropical matrix factorization

The tropical arithmetic operations on R are defined by a⊕b=min{a,b}a⊕b=min{a,b} and a⊗b=a+ba⊗b=a+b. Let A be a tropical matrix and k   a positive integer, the problem of Tropical Matrix Factorization (TMF) asks whether there exist tropical matrices B∈Rm×kB∈Rm×k and C∈Rk×nC∈Rk×n satisfying B⊗C=AB⊗C=A. We show that the TMF problem is NP-hard for every k≥7k≥7 fixed in advance, thus resolving a problem proposed by Barvinok in 1993.