Strong linear independence in bottleneck algebra (Q1094338)

Linear systems of the form \[ \max_{1\leq j\leq n}\min (a_{ij},x_ j)=b_ i\quad (1\leq i\leq m) \] have been treated in the literature for a long time [e.g. cf. \textit{K. Zimmermann} [Extremalni algebra, Praha: Vyzkumná publicace Ekonomicko-matematické Laboratorie pri Ekonomickém ústava CSAV 46, 127 p. (1976)] or the reviewer [Linear and combinatorial optimization in ordered algebraic structures (1981; Zbl 0466.90045)]. Here, all coefficients \(a_{ij}\), \(b_ i\) are chosen from a dense, linearly ordered set (B,\(\leq)\). If the linear system is uniquely solvable for some \(b\in B^ m\) the columns in the matrix \(A=(a_{ij})\) are called strongly linearly independent. Square matrices with strongly independent columns are called strongly regular. An \(m\times n\) matrix A has SLI-columns if and only if it contains a strongly regular matrix of size n. The matrix A is called trapezoidal, if \(a_{kk}>\max \{a_{j}| \quad 1\leq i\leq k,\quad i<j\leq n\}\) for all \(1\leq k\leq m\). It is proved that every strongly regular matrix A can be transformed into a trapezoidal matrix by suitable row- and column- permutations. Vice versa, every trapezoidal matrix is strongly regular. For the latter result, density of B is a necessary assumption. An O(m\(\cdot n\cdot \log (n))\)-algorithm is developed which constructs the row- and column-permutations revealing a hidden trapezoidal matrix. It is well-known that the linear bottleneck assignment problem \(\max_{\pi \in S}\min \{a_{i\pi (i)}| \quad 1\leq i\leq n\},\) where S denotes the set of all permutations of \(\{\) 1,2,...,n\(\}\), can be solved in \(O(n^{5/2}\cdot \log (n))\) using binary search techniques. If A is trapezoidal, then the identity is optimal. If the linear bottleneck assignment problem has a unique optimal solution then A is proved to be strongly regular and, therefore, by revealing its hidden trapezoidal form, the linear bottleneck problem can be solved in \(O(n^ 2\cdot \log (n))\).