A \(PLU\)-factorization of rectangular matrices by the Neville elimination (Q1855413)

The authors prove that a rectangular matrix \(A\) of size \(n \times m\) can be factorized as \(A=PLU\) by the Neville elimination algorithm, where \(P\) is a permutation matrix of size \(n \times n\), \(L\) is a lower triangular matrix of size \(n \times n\) and \(U\) is an upper echelon form matrix of size \(n \times m\). This result generalizes previous existing ones for matrices satisfying the consecutive-column and consecutive-row properties [cf. \textit{M. Fiedler}, \textit{T.L. Markham}, Linear Algebra Appl. 304, 161-171 (2000; Zbl 0948.15012)] and the without-row exchange condition of \textit{M. Gasca} and \textit{J.M. Peña} [Linear Algebra Appl. 202, 33-53 (1994; Zbl 0804.65028)]. The main result is obtained after proving first that Neville elimination can be described as the product of elementary and permutation matrices. In addition, a class of matrices where Neville elimination has lower computational cost than Gaussian elimination is defined.