CONCISE ROW-PRUNING ALGORITHM TO INVERT A MATRIX

Presented here, in a vector formulation, is an O(mn2) direct concise a lgorithm that prunes/identifies the linearly dependent (ld) rows of an arbitrary m X n matrix A and computes its reflexive type minimum norm inverse A(mr)-, which will be the true inverse A-1 if A is nonsingula r and the Moore-Penrose inverse A+ if A is full row-rank. The algorith m, without any additional computation, produces the projection operato r P = (I - A(mr)- A) that provides a means to compute any of the solut ions of the consistent linear equation Ax = b since the general soluti on may be expressed as x = A(mr)+b + Pz, where z is an arbitrary vecto r. The rank r of A will also be produced in the process. Some of the s alient features of this algorithm are that (i) the algorithm is concis e, (ii) the minimum norm least squares solution for consistent/inconsi stent equations is readily computable when A is full row-rank (else, a minimum norm solution for consistent equations is obtainable), (iii) the algorithm identifies ld rows, if any, and reduces concerned comput ation and improves accuracy of the result, (iv) error-bounds for the i nverse as well as the solution x for Ax = b are readily computable, (v ) error-free computation of the inverse, solution vector, rank, and pr ojection operator and its inherent parallel implementation are straigh tforward, (vi) it is suitable for vector (pipeline) machines, and (vii ) the inverse produced by the algorithm can be used to solve under-/ov erdetermined linear systems.