On the existence and computation of 𝐿𝑈-factorizations with small pivots
Authors: Chan Tony F. 
Published: June 2010

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 nth pivot. When A is not singular, we show conditions under which a pivoting strategy will produce an nth pivot that is

O
(

σ
n

)

O({\sigma _n})

or

O
(

κ

−
1

(
A
)
)

O({\kappa ^{ - 1}}(A))

, where

σ
n

{\sigma _n}

is the smallest singular value of A and

κ
(
A
)

\kappa (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

{\sigma _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 nth pivot for nearly singular matrices. As an example, we exhibit an LU-factorization of the n by n upper triangular matrix
\[
<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T equals Start 7 By 8 Matrix 1st Row 1st Column 1 2nd Column a m p semicolon negative 1 3rd Column a m p semicolon 4th Column a m p semicolon negative 1 5th Column a m p semicolon 6th Column a m p semicolon dot 7th Column a m p semicolon dot 8th Column a m p semicolon negative 1 2nd Row 1st Column Blank 2nd Column a m p semicolon 1 3rd Column a m p semicolon 4th Column a m p semicolon dot 5th Column a m p semicolon 6th Column a m p semicolon 7th Column a m p semicolon 8th Column a m p semicolon dot 3rd Row 1st Column Blank 2nd Column a m p semicolon 3rd Column a m p semicolon 4th Column a m p semicolon 1 5th Column a m p semicolon dot 6th Column a m p semicolon 7th Column a m p semicolon 8th Column a m p semicolon 4th Row 1st Column Blank 2nd Column a m p semicolon 3rd Column a m p semicolon 4th Column a m p semicolon 5th Column a m p semicolon dot 6th Column a m p semicolon dot 7th Column a m p semicolon 8th Column a m p semicolon dot 5th Row 1st Column Blank 2nd Column a m p semicolon 3rd Column a m p semicolon 0 4th Column a m p semicolon 5th Column a m p semicolon 6th Column a m p semicolon dot 7th Column a m p semicolon dot 8th Column a m p semicolon dot 6th Row 1st Column Blank 2nd Column a m p semicolon 3rd Column a m p semicolon 4th Column a m p semicolon 5th Column a m p semicolon 6th Column a m p semicolon 7th Column a m p semicolon dot 8th Column a m p semicolon negative 1 7th Row 1st Column Blank 2nd Column a m p semicolon 3rd Column a m p semicolon 4th Column a m p semicolon 5th Column a m p semicolon 6th Column a m p semicolon 7th Column a m p semicolon 8th Column a m p semicolon 1 EndMatrix">

T
=

[

1

a
m
p
;

−
1

a
m
p
;

a
m
p
;

−
1

a
m
p
;

a
m
p
;
⋅

a
m
p
;
⋅

a
m
p
;

−
1

a
m
p
;
1

a
m
p
;

a
m
p
;
⋅

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;
⋅

a
m
p
;

a
m
p
;

a
m
p
;
1

a
m
p
;
⋅

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;
⋅

a
m
p
;
⋅

a
m
p
;

a
m
p
;
⋅

a
m
p
;

a
m
p
;
0

a
m
p
;

a
m
p
;

a
m
p
;
⋅

a
m
p
;
⋅

a
m
p
;
⋅

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;
⋅

a
m
p
;

−
1

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;

a
m
p
;
1

]

T = \left [ {\begin {array}{*{20}{c}} 1 & { - 1} & {} & { - 1} & {} & \cdot & \cdot & { - 1} \\ {} & 1 & {} & \cdot & {} & {} & {} & \cdot \\ {} & {} & {} & 1 & \cdot & {} & {} & {} \\ {} & {} & {} & {} & \cdot & \cdot & {} & \cdot \\ {} & {} & 0 & {} & {} & \cdot & \cdot & \cdot \\ {} & {} & {} & {} & {} & {} & \cdot & { - 1} \\ {} & {} & {} & {} & {} & {} & {} & 1 \\ \end {array} } \right ]

\]
that has an nth pivot equal to

2

−
(
n
−
2
)

2^{-(n-2)}

.