Which factor has ones on its diagonal?

In the standard Crout convention used here, U does.

Does LU factorization require symmetry?

General LU does not; Cholesky has additional structural requirements.

Can the factors be reused?

Yes, for new right-hand sides with the same coefficient matrix, using the same permutation and solve conventions.

AI Glossary / Mathematics and optimization / Intermediate

Crout matrix decomposition

Definition

Crout matrix decomposition is an LU factorization convention in which a matrix is expressed as a lower-triangular factor L times an upper-triangular factor U whose diagonal entries are all one. It supports efficient solution of linear systems through forward and backward substitution. Row permutations may be needed to avoid unsuitable pivots and improve numerical behavior.

What it means

Triangular systems are easier to solve than general dense systems because each equation introduces only one new unknown when processed in the appropriate order. Factoring A into L and U converts Ax=b into two such solves.

Crout and Doolittle differ in where they place the unit diagonal: Crout normally uses a unit upper factor, while Doolittle uses a unit lower factor. Neither convention means that A itself is triangular. In high-performance numerical software, “Crout” can also describe an ordering of factorization work, so documentation must establish the exact convention being used.

How it works

For the basic unpivoted scheme, set the diagonal of U to one. Work through successive columns. Compute the current column of L by subtracting contributions from previously completed columns and rows. Then compute the corresponding row of U by subtracting earlier contributions and dividing by the new diagonal entry of L.

In symbols, Lᵢⱼ=Aᵢⱼ−Σₖ<ⱼLᵢₖUₖⱼ for i≥j. For k>j, Uⱼₖ=(Aⱼₖ−Σᵣ<ⱼLⱼᵣUᵣₖ)/Lⱼⱼ. A zero or problematic pivot requires appropriate handling rather than division regardless of its value.

With a permutation convention PA=LU, solve Ly=Pb and then Ux=y. Other libraries express the permutation differently, so use their stated identity. The same factors can support multiple right-hand sides when A is unchanged.

Three practical examples

1. Engineering models: solve linear equations arising from discretized physical relationships, provided the matrix structure and solver choice suit the model.

2. Repeated scenarios: reuse one factorization for several load or forcing vectors when only the right-hand side changes.

3. Numerical education and implementation review: compare Crout and Doolittle storage layouts and verify that substitution routines use the correct diagonal convention.

Think of it this way

Think of resolving a complicated set of dependencies through two orderly passes. The first pass determines intermediate quantities from the beginning forward; the second recovers the final unknowns from the end backward.

The analogy does not suggest arbitrary dependencies can be split without numerical difficulty. Matrix properties, pivot selection and rounding error affect the calculation. The intermediate vector y is also a mathematical construction, not necessarily a meaningful physical state.

Worked example

Consider the original matrix A=[[2,4,−2],[4,11,2],[2,1,−3]]. A Crout factorization without row swaps is L=[[2,0,0],[4,3,0],[2,−3,5]] and U=[[1,2,−1],[0,1,2],[0,0,1]].

The first column of L copies (2,4,2). The first row of U uses the first row of A divided by 2, giving (1,2,−1). Next L₂₂=11−4×2=3 and L₃₂=1−2×2=−3. Then U₂₃=(2−4×(−1))/3=2. Finally L₃₃=−3−2×(−1)−(−3)×2=5.

Solve Ax=b for b=(4,32,−5). Forward substitution in Ly=b gives y₁=2, y₂=(32−4×2)/3=8, and y₃=(−5−2×2+3×8)/5=3.

Backward substitution in Ux=y gives x₃=3, x₂=8−2×3=2, and x₁=2−2×2+3=1. Direct checking gives A(1,2,3)=(4,32,−5).

The determinant is the product of the L diagonal entries because U has unit diagonal: 2×3×5=30. This hand-checked example requires no pivoting, but that convenience must not be assumed for arbitrary matrices.

Illustrative case study

Fictional case: a simulation team replaces a teaching LU routine with a production library. A developer mistakenly passes the new factors into an old substitution function that assumes the opposite unit-diagonal convention. The resulting answers have the correct dimensions but fail a residual check.

The team verifies the library's factorization identity, diagonal storage and permutation convention before correcting the solve. It preserves a small known system as a diagnostic example and checks results against the original A and b, rather than trusting factor shapes alone.

Common misconceptions and mistakes

Do not assume every nonsingular matrix admits the straightforward unpivoted scheme. For example, [[0,1],[1,0]] is nonsingular but begins with a zero pivot; a row exchange resolves that obstruction.

Do not divide by the U diagonal in a Crout backward solve as though it contained the general pivot values. Under this convention those pivots are in L.

Do not confuse Crout with Cholesky factorization, which exploits symmetric or Hermitian positive-definite structure. Also distinguish a small residual from a guaranteed small solution error: ill-conditioned systems can be highly sensitive even when the computed equations nearly balance.

Business use

Factorization is often an internal operation in analytics and simulation software rather than a feature selected directly by business users. Its practical value includes efficient repeated solves and well-understood numerical diagnostics.

Use appropriate library routines, document whether factors overwrite the original matrix and retain enough information to check residuals. Consider sparsity and structure before choosing a dense method. Reusing factors is valid only when the coefficient matrix remains the same; changing b is different from changing entries of A. Avoid explicitly forming an inverse merely to solve a system unless a separate requirement justifies it.

Check your understanding

Where are the non-unit diagonal values in the worked example?

Answer: They are 2, 3 and 5 on L's diagonal. U's diagonal is (1,1,1), which determines how the two substitution passes are performed.

Related terms

Condition number
LU factorisation
Doolittle method
triangular matrix
pivoting
permutation matrix
forward substitution
backward substitution

Learn next

multiply the example's L and U to reconstruct every entry of A. Then test the zero-pivot matrix in the misconceptions section and trace how a row permutation changes both the factorization and the right-hand side.

Sources

Sources: Wallstedt's primary implementation notes and Crout factorisation/substitution code read: https://www.sci.utah.edu/~wallstedt/LU.htm . Pracma's primary LU documentation consulted for the related factorisation conventions: https://search.r-project.org/CRAN/refmans/pracma/html/lu.html . The example is independently constructed and hand-checked; source code was inspected, not executed. Case is fictional.

Previous: Crossover study Next: Crowdsource