Detecting matrices of combinatorial rank three

The smallest integer k for which the elements of a real matrix A can be expressed as A i j = min t = 1 k { B i t + C t j } with B ∈ R m × k and C ∈ R k × n is called the combinatorial rank of A. This notion was introduced by Barvinok in 1993, and he posed a problem on the complexity of detecting matrices with combinatorial rank equal to a fixed integer k. Fast algorithms solving this problem have been known only for k ≤ 2 , and we construct an algorithm that decides whether or not a given matrix has combinatorial rank three in time O ( ( m + n ) 3 m n log ( m n ) ) .