A comparison of gaussian and gauss-jordan elimination in regular algebra

A comparison is presented in regular algebra of the Gaussian and Gauss-Jordon elimination techniques for solving sparse systems of simultaneous equations. Specifically, the elimination form and product form of the star A* of a matrix A are defined and it is then shown that the product form is never more sparse than the elimination form. This result generalises an earlier one due to Brayton, Gustavson and Willoughby in which it is shown that the product form of the inverse A-1 of a matrix A is never more sparse than the elimination form of the inverse. Our result applies both in linear algebra and, more generally, to path-finding problems.