The general trapezoidal algorithm for strongly regular max--min matrices. (Q1399940)

A max-min algebra is a fuzzy algebra that consists of a linearly ordered set together with the binary operations of maximum and minimum \(({\mathcal B},\leq,\oplus,\otimes)\). For any natural number \(n>0\), \({\mathcal B}(n)\) denotes the set of all \(n\)-dimensional column vectors over \({\mathcal B}\) and similarly \({\mathcal B}(m,n)\) denotes the set of all \(m \times n\) matrices over \({\mathcal B}\). A square matrix \(A \in {\mathcal B}(n,n)\) is {strongly regular} if there exists \(b \in {\mathcal B}(n)\) such that the equation \(A \otimes x=b\) is uniquely solvable. The author proposes an \(O(n^2\log n)\) algorithm for the recognition of the strong regularity of a given \(n \times n\) matrix. This generalizes several previous results in which additional assumptions on the matrix had to be imposed to prove the result.