Regularity of matrices in min-algebra and its time-complexity (Q1346691)

Let \({\mathcal G}= (G, \otimes, \leq)\) be a linearly ordered commutative group and \(\oplus\) be defined by \(a\oplus b= \min(a, b)\) for all \(a, b\in G\). An \(n\times n\) matrix \(A\) with columns \(A_ 1,\dots, A_ n\) is called regular if \[ \sum_{j\in U}^ \oplus \lambda_ j\otimes A_ j= \sum_{j\in V}^ \oplus \lambda_ j\otimes A_ j \] does not hold for any \(\lambda_ 1,\dots, \lambda_ n\in G\), \(\varnothing\neq U, V\subseteq \{1,2,\dots, n\}\), \(U\cap V= \varnothing\). The author studies the time-complexity of the problem of checking regularity of matrices. Since addition is now not a group operation, there are several non-equivalent ways of defining the regularity. He investigates three different such definitions. Two of these can be checked efficiently in \(O(n^ 3)\) operations but the third, which plays a central role in minimal-realization of the discrete event dynamic systems, is shown to be polynomially equivalent to the problem of the existence of an even cycle in a digraph.