Try
Consider A with rows (1,2,0), (2,5,1), (0,1,3), using exact real arithmetic. Subtract twice row 1 from row 2. The new second row is (0,1,1). Then subtract this new row 2 from row 3, obtaining (0,0,2). The resulting upper triangular matrix U has rows (1,2,0), (0,1,1), (0,0,2).
We have not simply made the matrix look tidier. We have recorded two reversible instructions that can be reused when the right-hand side changes. To recover A from U, its original second row is twice U’s first row plus U’s second row. Its original third row is U’s second row plus U’s third row. Therefore A=LU, where L has rows (1,0,0), (2,1,0), (0,1,1). Multiply all nine entries to check the claim before relying on it.
The factor L is unit lower triangular: it has zeros above the diagonal and ones on it. U is upper triangular. The unit normalization prevents arbitrary rescaling between the factors. In this lesson, “LU” means exactly these conventions, without row exchanges.
Predict
Can a nonsingular matrix fail to have this LU? Test the swap matrix with rows (0,1),(1,0). Its determinant is −1, so the linear map is invertible. But elimination cannot divide by its top-left zero. Write possible factors as L=(1,0;ℓ,1) and U=(u,v;0,w), where semicolons separate rows. Entry 11 of LU forces u=0, and then entry 21 is ℓu=0, contrary to the required 1. Thus this ordering genuinely has no LU of the declared form. A row exchange changes the problem to a pivoted factorization.
Also predict whether singularity forbids LU. It does not: diag(1,0)=I·diag(1,0). We must separate existence of factors, existence of a usable nonzero pivot at every stage, and invertibility of the original matrix. They agree under certain hypotheses, not by definition.
Experiment
On paper, reproduce the two elimination steps for the starting matrix. Alongside each step record the multiplier and the row it acts on. Then rebuild L rather than guessing it from the final zeros.
| Stage | Matrix rows | Information retained |
|---|
| Start | (1,2,0); (2,5,1); (0,1,3) | First pivot 1 |
|---|
| Row 2 minus 2 row 1 | (1,2,0); (0,1,1); (0,1,3) | Multiplier ℓ₂₁=2; ℓ₃₁=0 |
|---|
| Row 3 minus row 2 | (1,2,0); (0,1,1); (0,0,2) | Multiplier ℓ₃₂=1; final pivot 2 |
|---|
The three leading principal minors are 1, 1 and 2. Here the k-th leading principal minor Δk means the determinant using the first k rows and first k columns. Put Δ0=1. The ratios Δ1/Δ0, Δ2/Δ1 and Δ3/Δ2 are 1,1,2, exactly the pivots. Predict why the first two minors, not just the determinant of the whole matrix, enter a no-exchange algorithm.
Extract the diagonal D=diag(1,1,2) from U. Set R=D⁻¹U, scaling row 3 of U by 1/2. Then R has rows (1,2,0), (0,1,1), (0,0,1), and A=LDR. Both L and R now have unit diagonals. The non-unit pivot sizes are stored entirely in D. Multiplying U by D⁻¹ on the other side would scale columns instead and would generally produce a different factor.
Understand
Here is the precise existence theorem. Let A be a nonsingular square n×n matrix over a field, with n≥1. Then A has unit-lower LU without row exchanges if and only if every leading principal minor Δ1,…,Δn is nonzero. The final one is det A; it is already nonzero under the hypothesis, but belongs to the list. This is an exact algebraic criterion, not a numerical stability guarantee.
First prove necessity. If A=LU, its leading k×k block equals the product of the leading blocks of L and U. Indeed, in a top-left entry, every summation index beyond k has a zero entry from the lower triangular L. The determinant of the leading L block is 1, and the determinant of the leading U block is the product of its first k diagonal entries. Since det A is the product of all diagonal entries of U and is nonzero in a field, none of those entries vanishes. Consequently every Δk is nonzero. The same identity immediately yields
u(k,k)=Δk/Δ(k−1).
We now construct the factors and prove sufficiency, rather than assuming that elimination always succeeds. The one-dimensional case is [a]=[1][a], with a≠0. In higher dimension write A in blocks (a,w;r,C): a is a scalar, w a row, r a column, and C the remaining square block. Since a=Δ1≠0, subtract r/a times the first row from the lower rows. The remaining lower-right matrix is the Schur complement S=C−rw/a.
For each leading j×j block of S, perform exactly the same row additions on the leading (j+1)×(j+1) block of A. They preserve its determinant and produce an upper block triangular matrix with diagonal blocks a and that block of S. Thus the latter determinant equals Δ(j+1)/a, which is nonzero. The induction hypothesis applies to S and supplies S=LₛUₛ. Define the block matrices
L=(1,0; r/a,Lₛ), U=(a,w; 0,Uₛ).
Their product is (a,w; r,rw/a+LₛUₛ)=(a,w;r,C)=A. They have the required shapes and unit diagonal for L. This proves the construction at every dimension, using only inverses already known to exist. It also explains the stored multipliers: they are the lower-column entries needed to reverse the successive elimination steps.
Why are the factors unique? Suppose L₁U₁=L₂U₂ for a nonsingular A. The inverse of an invertible triangular matrix has the same triangular form, as follows by solving its triangular systems column by column. A unit lower inverse still has diagonal 1. Therefore L₂⁻¹L₁=U₂U₁⁻¹ is simultaneously unit lower triangular and upper triangular. It must be the identity. This forces both L factors and both U factors to agree. Inverting U is legitimate here because every pivot is nonzero; it would not be legitimate for an arbitrary singular matrix.
Now define D from the nonzero diagonal entries of U and R=D⁻¹U. This proves existence of normalized LDU. Conversely any other triple with unit lower L, invertible diagonal D and unit upper R yields an LU with upper factor DR. LU uniqueness fixes L and U; the diagonal of U then fixes D, and hence R. Without normalization, even I₂ has different triangular products: for example diag(2,3) times diag(1/2,1/3) over the reals.
At singular matrices neither the iff theorem nor the uniqueness conclusion can be transferred unchanged. The zero 2×2 matrix equals L·0 for every L with rows (1,0),(ℓ,1), so there are infinitely many normalized L choices over R. Conversely, some singular matrices have perfectly valid LU, as diag(1,0) shows. A zero pivot during one proposed process can reflect an unsuitable ordering or actual rank deficiency; the single observation does not decide which.
Apply
Change to the rectangular matrix with rows (2,1,3),(4,3,8). With m=2 rows and n=3 columns, use the full-row convention L of size m×m and U of size m×n. Subtract twice row 1 from row 2: L has rows (1,0),(2,1), and U has rows (2,1,3),(0,1,2). Their product gives the original matrix. U is echelon and upper trapezoidal, but it is not a square invertible matrix.
A pivot need not lie on the diagonal in a rectangular echelon form. For the 3×2 matrix with rows (0,1),(0,2),(0,3), the first column is zero and the first pivot is at row 1, column 2. Use L with rows (1,0,0),(2,1,0),(3,0,1) and U with rows (0,1),(0,0),(0,0). Check their product and identify rank 1. Insisting on a nonzero u11 would incorrectly reject this valid factorization. A whole nonsquare determinant is not defined, so the square leading-minor criterion is not a general rectangular theorem.
For an independent parameter check, take A(t) with rows (t,1,0),(1,1,0),(0,0,2). Its leading minors are t,t−1,2(t−1). Distinguish the case t=0, where the matrix is invertible but needs a row exchange, from t=1, where it is singular yet admits LU. For all other t derive the factors explicitly; then see which expressions remain meaningful at t=1. Do not substitute into a pivot ratio whose denominator has become zero.
Continue
A usable factorization report states the field, matrix shape, triangular normalization, permutation convention and every zero-pivot qualification. The construction explains how to factor once; solving several right-hand sides then uses forward and backward substitution rather than repeating elimination. Pivoted factors require tracking row exchanges and earlier multipliers consistently, which is the next reuse investigation.
Return to determinant products and invertibility for the block determinant identities, or row operations for solution equivalence. Exact correctness does not imply that an unpivoted numerical implementation is stable: small computed pivots require a separate error analysis.
