On the regularity of matrices in min algebra (Q807718): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Peter Butkovic / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Raymond Cuninghame-Green / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Joseph L. Zemmer / rank | |||
Normal rank |
Revision as of 03:29, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the regularity of matrices in min algebra |
scientific article |
Statements
On the regularity of matrices in min algebra (English)
0 references
1991
0 references
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.
0 references
linearly ordered commutative group
0 references
regular matrices
0 references
assignment problem
0 references
acyclic digraphs
0 references
algorithms
0 references