A generalization of the fast LUP matrix decomposition algorithm and applications

We show that any m × n matrix A, over any field, can be written as a product, LSP, of three matrices, where L is a lower triangular matrix with l's on the main diagonal, S is an m × n matrix which reduces to an upper triangular matrix with nonzero diagonal elements when the zero rows are deleted, and P is an n × n permutation matrix. Moreover, L, S, and P can be found in O(m^α?1n) time, where the complexity of matrix multiplication is O(m^α). We use the LSP decomposition to construct fast algorithms for some important matrix problems. In particular, we develop O(m^α?1n) algorithms for the following problems, where A is any m × n matrix: (1) Determine if the system of equations $\text{A}\text{x}\text{=}\text{b}$ (where $\text{b}$ is a column vector) has a solution, and if so, find one such solution. (2) Find a generalized inverse, $\text{A}{}^1$, of A (i.e., $\text{AA}{}^1\text{A = A}$). (3) Find simultaneously a maximal independent set of rows and a maximal independent set of columns of A.