On the existence and computation of 𝐿𝑈-factorizations with small pivots

Let A be an n by n matrix which may be singular with a one-dimensional null space, and consider the LU -factorization of A . When A is exactly singular, we show conditions under which a pivoting strategy will produce a zero n th pivot. When A is not singular, we show conditions under which a pivoting strategy will produce an n th pivot that is O ( σ n ) O({σ _n}) or O ( κ − 1 ( A ) ) O({κ - 1}(A)) , where σ n {σ _n} is the smallest singular value of A and κ ( A ) κ (A) is the condition number of A . These conditions are expressed in terms of the elements of A − 1 {A- 1} in general but reduce to conditions on the elements of the singular vectors corresponding to σ n {σ _n} when A is nearly or exactly singular. They can be used to build a 2-pass factorization algorithm which is guaranteed to produce a small n th pivot for nearly singular matrices. As an example, we exhibit an LU -factorization of the n by n upper triangular matrix \[