5.1 LU with and without Pivoting

5.1 LU with and without Pivoting

If you’ve ever taken a linear algebra course, you’ve probably seen LU decomposition presented in a neat, formal way:

A = L U

It looks clean. Almost too clean. The reality is more nuanced: LU decomposition can behave beautifully—but only when the matrix cooperates. And many real-world matrices do not.

Before diving into why pivoting exists, let’s start with the basic, idealized version.

LU Without Pivoting: The Textbook Version

In its purest form, LU decomposition takes a matrix A and produces:

• L: a lower-triangular matrix with 1s on the diagonal
• U: an upper-triangular matrix

The idea is simple: perform Gaussian elimination, but instead of discarding the multipliers you used to eliminate each entry below the pivot, store them in L. The remaining upper-triangular entries naturally form U.

Formally:

A = L U

This decomposition is incredibly useful. Once A is factored, solving A x = b becomes a two-step routine:

1. Solve L y = b (forward substitution)
2. Solve U x = y (backward substitution)

This is efficient, elegant, and conceptually clean. But this version of LU has a problem—one so severe it makes the no-pivot version almost unusable in real numerical computing:

It fails for many perfectly legitimate matrices.

When LU Without Pivoting Fails

You can perform Gaussian elimination only if the pivot elements (the diagonal entries of U) are non-zero. More precisely:

LU without pivoting exists only if all leading principal minors of A are non-zero.

This condition is often violated in practice. Even worse, a matrix might be theoretically factorizable but still be hopelessly unstable in floating-point arithmetic.

Here are some common ways LU fails without pivoting:

• Zero pivot: the algorithm breaks immediately.
• Tiny pivot: the multipliers become huge, amplifying rounding errors.
• Poor conditioning: mathematically valid, numerically disastrous.

The tiniest pivot can collapse the entire elimination process—making the decomposition useless or wildly inaccurate.

This fragility leads to the practical question: how do we protect the algorithm?

Enter Pivoting: A Small Adjustment with Enormous Impact

Pivoting introduces a simple idea:

Swap rows to get better pivots.

Most of the time, “better” means “larger in absolute value.” When we swap rows to select a pivot, we are performing partial pivoting, the industry standard for LU decomposition:

P A = L U

Here, P is a permutation matrix representing the row swaps.

Why pivoting matters:

• It prevents division by zero.
• It avoids tiny pivots that cause huge multipliers.
• It dramatically improves numerical stability.
• It enables LU decomposition for almost any nonsingular matrix.

And the cost? Almost nothing. Row swaps are extremely cheap, and modern linear algebra libraries perform pivoting automatically.

Types of Pivoting

1. Partial Pivoting (the default everywhere)

For each column, choose the largest absolute value in that column below the pivot, then swap the rows.

This is the version used by LAPACK, NumPy, MATLAB, and essentially every production-grade library.

2. Complete Pivoting

Search the entire remaining submatrix for the largest value and swap both rows and columns. This gives stronger numerical guarantees, but at a much higher computational cost.

3. No Pivoting

Mostly a teaching tool—dangerous in general computing unless the matrix has special structure (e.g., diagonally dominant or SPD, which we will address in the next chapters).

A Geometric View: Why Pivoting Helps

Pivoting chooses pivots that keep the elimination multipliers small. Smaller multipliers mean smaller error amplification. Think of it as choosing the most stable “anchor point” before each elimination step.

Without pivoting, elimination often looks balanced in theory but becomes chaotic when implemented with floating-point numbers. Pivoting reorganizes that chaos into a stable process.

LU in Practice

Even if you never manually write an LU decomposition, you benefit from pivoting constantly. Whenever you call:

• numpy.linalg.solve(A, b)
• scipy.linalg.lu_factor
• torch.linalg.solve
• tensorflow.linalg.lu

—you are almost certainly using LU with partial pivoting.

This version is the workhorse of scientific and machine learning software. It is not the most precise method (QR and SVD have stronger guarantees), but it is often the fastest and most practical.

Where We’re Going Next

Pivoting makes LU robust, but not invincible. In fact, some of the most subtle and dangerous numerical failures appear after LU is computed—not during the factorization, but during its use.

Even with pivoting, LU can still become unstable when:

• the matrix is extremely ill-conditioned
• the multipliers grow unexpectedly large
• floating-point errors accumulate aggressively

These issues bring us naturally to the next section, where we examine the most common traps in LU decomposition—traps that can quietly destroy an entire computation without warning.

Let’s continue with 5.2 Numerical Pitfalls.