Minimum deviation, quasi-LU factorization of nonsingular matrices (Q2383020)

The authors are concerned with the following problem. If the matrix \(A\) is nonsingular and has no \(LU\) factorization, how may \(A\) be factored into \(\widetilde L\) and \(\widetilde U\) that are ``nearly'' lower and upper triangular, respectively? They give an explicit measure of nearness to a matrix being triangular, and they introduce a measure, the deviation \(\text{dev}(\widetilde L,\widetilde U)\) of the quasi-\(LU\) factorization \(A=\widetilde L\widetilde U\) from an \(LU\) factorization. It is known that \(A\) can be written as \(LPU\), where \(L\) is unit lower triangular, \(P\) is a permutation matrix, and \(U\) is upper triangular. One obtains a quasi-\(LU\) factorization of \(A\) by putting \(\widetilde L=LP\) and \(\widetilde U=U\). The authors calculate \(\text{dev}(\widetilde L,\widetilde U)\) and establish that the deviation of any quasi-\(LU\) factorization cannot be better than the one mentioned above.