On the regularity of matrices in min algebra (Q807718)

Let \(G(+,\geq)\) be a linearly ordered commutative group. Define an algebraic structure G(\(\oplus,\otimes)\) on G by setting \(x\oplus y=\min (x,y)\) and \(x\otimes y=x+y\). The authors consider the set \(G_ n\) of \(n\times n\) matrices over G(\(\oplus,\otimes)\). Note that if \(A=(a_{ij})\) is an element of \(G_ n\) and \(X=(x_ i)\) is an \(n\times 1\) matrix over G then AX is an \(n\times 1\) matrix whose ith row is \(\min (a_{i1}+x_ 1,a_{i2}+x_ 2,...,a_{in}+x_ n)\). Let \(B=(b_ i)\) be an arbitrary \(n\times 1\) matrix over G, and let T(A) be the set of all possible cardinalities of the solution set of \(AX=B\), where the entries in B range over all of G. It is easy to show that either \(T(A)=\{0,1,\infty \}\) or \(T(A)=\{0,\infty \}\). The matrix A is said to be regular if \(T(A)=\{0,1,\infty \}\). The authors develop connections between regular matrices and (i) the assignment problem and (ii) acyclic digraphs. The main purpose of this paper is to use the connections and certain well known algorithms to establish a procedure to determine, in case G is cyclic, whether or not a given matrix is regular. The procedure established requires \(O(n^ 3)\) operations.