STRONG REGULARITY OF MATRICES - A SURVEY OF RESULTS

Let G = (G, x, less than or equal to) be a linearly ordered, commutati ve group and u+v = max(u, v) for all u, v epsilon G. Extend +, x in th e usual way on matrices over G. An m x n matrix A is said to have stro ngly linearly independent (SLI) columns, if for some b the system of e quations Axx = b has a unique solution. If, moreover, m = n then A is said to be strongly regular (SR). This paper is a survey of results co ncerning SLI and SR with emphasis on computational complexity. We pres ent also a similar theory developed for a structure based on a linearl y ordered set where + is maximum and x is minimum.