On the regularity of matrices in min algebra

Directed graphs (digraphs), tournaments (05C20) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Matrices of integers (15B36) Discrete location and assignment (90B80)

Review text

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.

Recommendations

Cites work

Cited in

(15)

This page was built for publication: On the regularity of matrices in min algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q807718)