Calculating the Determinant (Kraut method)

Kraut (often spelled Crout; CP-Algorithms uses “Kraut”) computes an LU factorization A = L U in O(N³), then reads off

det(A) = Πᵢ Uᵢᵢ

when L has a unit diagonal. This lesson follows CP-Algorithms — Determinant (Kraut).

Idea

• L = lower triangular, Lᵢᵢ = 1
• U = upper triangular
• det(L) = 1, so det(A) = det(L)·det(U) = det(U) = product of diag(U)

An invertible matrix has a unique LU factorization of this form iff all leading principal minors are nonzero. If a pivot Uⱼⱼ hits zero, you need row pivoting (partial pivoting) and must track the sign of each swap.

Formulas

For each column j = 1 … N (1-based):

1. For i = 1 … j:

Uᵢⱼ = Aᵢⱼ − Σ_{k=1}^{i−1} Lᵢₖ · Uₖⱼ

2. For i = j+1 … N:

Lᵢⱼ = (1 / Uⱼⱼ) · ( Aᵢⱼ − Σ_{k=1}^{j−1} Lᵢₖ · Uₖⱼ )

Same formulas, 0-based, appear in the simulator and C++ demo.

Compact storage & pivoting

In practice one matrix overwrites A:

• upper triangle (incl. diagonal) → U
• strict lower triangle → multipliers Lᵢⱼ (L diagonal stays implicit 1s)

The Java snippet on CP-Algorithms also:

• scales rows for pivot selection
• swaps rows for the largest scaled residual (imax)
• flips sign on each swap
• returns sign · Π aᵢᵢ rounded to an integer

Without pivoting the algorithm can fail or lose precision even when det(A) ≠ 0.

Tiny instance

A = [[ 2,  1, 1],
     [ 4, −6, 0],
     [−2,  7, 2]]

L = [[ 1,  0, 0],
     [ 2,  1, 0],
     [−1, −1, 1]]

U = [[ 2,  1,  1],
     [ 0, −8, −2],
     [ 0,  0,  1]]

det(A) = 2 · (−8) · 1 = −16.

🧪 LU determinant (C++, no pivoting)

Complexity

Filling each of the O(N²) entries of L/U costs an O(N) sum → O(N³), same order as Gaussian elimination. Determinant via Laplace expansion is factorial; LU is the practical cubic method.

Check: LU determinant

Quiz

Kraut / LU determinant

1 / 4

With unit-diagonal L, det(A) equals…

Pick an answer to see if you are right.

Practice drills

Activity: 2×2 LU det

Input: four numbers a b c d for matrix [[a,b],[c,d]]. Using unit-L LU (no pivoting), print det as an integer (inputs are chosen so it is exact).

Hint formulas: U00=a, U01=b, L10=c/a, U11=d−L10·b, det=U00·U11.

Contest / further reading

• Implement partial pivoting and compare det on ill-conditioned inputs.
• CP-Algorithms — Gauss method for determinant — closely related cubic approach.
• Solve linear systems with the same L/U via forward- and back-substitution (O(N²) after factorization).

Cheat sheet

Idea	Takeaway
Goal	det(A) via A = L U
Convention	Lᵢᵢ = 1 (CP-Algorithms Kraut / Doolittle)
Formula	det = Π Uᵢᵢ (× (−1)^{#swaps} with pivoting)
Fill	Per column: U for i≤j, then L for i>j
Cost	O(N³)
Caveat	Need nonzero pivots / principal minors, or pivot