Strong regularity of matrices in a discrete bottleneck algebra (Q916746)

The author studies systems of linear equations of the form \(A\otimes x=b\) over a discrete bottleneck algebra (B,\(\oplus,\otimes,\leq)\), where (B,\(\leq)\) is a nonempty linearly ordered set, \(\oplus =\max\), \(\otimes =\min\) and every \(x\in B\) has a successor. A square matrix A over B is said to be strongly regular if for some vector b the system \(A\otimes x=b\) is uniquely solvable. Theorem: A square matrix A over B is strongly regular if and only if A is equivalent to a strongly trapezoidal matrix. An algorithm for testing of strong regularity of matrices which terminates after using \(O(n^ 2\log n)\) arithmetical operations is described.