Strong regularity of matrices -- a survey of results (Q1314327)

Let \((G,\otimes,\leq)\) be a linearly ordered commutative group and define an addition by \(x\oplus y= \max(x,y)\) for all \(x,y\in G\). Both operations extend in a canonical way to addition and multiplication of matrices over \(G\). If the linear system \(A\otimes x= b\) has a unique solution \(x\in G^ n\) for some \(b\in G^ m\), then the columns of the \(m\times n\) matrix \(A\) are called \textit{strongly linearly independent (SLI)}. In particular, if \(m= n\), then such a matrix \(A\) is called \textit{strongly regular (SR)}. The survey describes characterizations of strong linear independence and strong regularity. Strong regularity can be checked in \(O(n^ 3)\) using certain combinatorial algorithms. No polynomial time algorithm is known to testify strong linear independence. A similar discussion is done for monoids \((B,\otimes,\leq)\) with \(a\otimes b:=\min(a,b)\) for all \(a,b{\i}B\), which are based on some underlying linearly ordered set \((B,\leq)\). Here, for dense sets, efficient tests for \(SLI\) (in \(O(mn\log n))\) as well as \(SR\) (in \(O(n^ 2\log n))\) are known, while the general case remains open. In both systems the permanent is the value of the corresponding (sum or bottleneck) assignment problem. Unique solvability of the assignment problem is closely related to strong regularity. Bottleneck assignment problems with unique optimum can be solved in \(O(n^ 2\log n)\), i.e. faster than in the general case for which an \(O(n^{2.5}\sqrt{\log n})\) algorithm is known. A similar improvement is not known for sum assignment problems.