Strong linear independence in bottleneck algebra

Abstract Let ( B , ⩽) be a dense, linearly ordered set without maximum and minimum and (⊕, ⊗) = (max,min). We say that a matrix A has strongly linearly independent (SLI) columns if for some b the system A ⊗ x = b is uniquely solvable. An ( n , n ) matrix A = ( a ij ) is said (a) to be strongly regular if it has SLI columns; (b) to have a strong permanent if the equality per(A)= ⊗ i=1 n a i,π(i) holds for unique π ∈ P n [ per ( A ) is ⊕ π ∈ P n ⊗ n i = 1 a i , π ( i ) and P n is the set all permutations of the set {1,2,…, n }]. We prove: (i) that an ( m, n ) matrix has SLI columns if and only if it contains an ( n, n ) submatrix which is strongly regular [we derive an O ( mn log n ) algorithm for checking this property], (ii) that every matrix with strong permanent is strongly regular, and (iii) that a solution to the bottleneck assignment problem for strongly regular ( n, n ) matrices can be found using O ( n 2 log n ) operations.