Determinant via Row Reduction and Upper Triangular Form

Goal of this page

Learn how to use elementary row operations to reduce a matrix to upper triangular form and compute its determinant. This approach connects directly to practical computational algorithms and yields an efficient $O(n^3)$ method.

1. Determinant of an upper triangular matrix

1.1 Upper triangular matrices

A matrix whose entries below the main diagonal are all zero is called an upper triangular matrix:

$$U = \begin{pmatrix} u_{11} & u_{12} & u_{13} & \cdots & u_{1n} \\ 0 & u_{22} & u_{23} & \cdots & u_{2n} \\ 0 & 0 & u_{33} & \cdots & u_{3n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & u_{nn} \end{pmatrix}$$

1.2 Key theorem

Theorem. The determinant of an upper triangular matrix (or lower triangular matrix) equals the product of its diagonal entries:

$$\det(U) = u_{11} \cdot u_{22} \cdot u_{33} \cdots u_{nn}$$

1.3 Idea of the proof

Apply cofactor expansion along the first column. Since $u_{21} = u_{31} = \cdots = 0$, only the term involving $u_{11}$ survives:

$$\det(U) = u_{11} \cdot \det\begin{pmatrix} u_{22} & u_{23} & \cdots & u_{2n} \\ 0 & u_{33} & \cdots & u_{3n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{pmatrix}$$

Applying this recursively yields the product of the diagonal entries. This is an intuitive explanation; a rigorous proof by mathematical induction follows.

1.4 Rigorous proof (mathematical induction)

We proceed by induction on $n$.

Base case ($n = 1$): The determinant of a $1 \times 1$ matrix $(u_{11})$ is $u_{11}$, which is exactly the product of its diagonal entries.

Inductive hypothesis: Assume the theorem holds for all $(n-1) \times (n-1)$ upper triangular matrices.

Inductive step: Expand the determinant of an $n \times n$ upper triangular matrix $U$ along the first column by cofactor expansion:

$$\det(U) = \sum_{i=1}^{n} (-1)^{i+1} \, u_{i1} \, M_{i1}$$

Here $M_{i1}$ is the $(i, 1)$ minor, that is, the determinant of the $(n-1) \times (n-1)$ matrix obtained by deleting row $i$ and column $1$.

Since $U$ is upper triangular, $u_{21} = u_{31} = \cdots = u_{n1} = 0$. Each term in the sum has the form $u_{i1} \cdot M_{i1}$, so if $u_{i1} = 0$ then the entire term vanishes. Hence all terms with $i \geq 2$ vanish, and only the $i = 1$ term remains:

$$\det(U) = (-1)^{1+1} \, u_{11} \, M_{11} = u_{11} \, M_{11}$$
u11 u22 ⋱ unn * ⋯ * ⋯ * ⋮ 0 ⋮ 0 ⋮ 0 ⋯ M11 The red zeros vanish under cofactor expansion → det(U) = u11 · det(M11)

$M_{11}$ is the determinant of the matrix obtained by deleting the first row and first column of $U$. This matrix is:

$$\begin{pmatrix} u_{22} & u_{23} & \cdots & u_{2n} \\ 0 & u_{33} & \cdots & u_{3n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{pmatrix}$$

This is an $(n-1) \times (n-1)$ upper triangular matrix. By the inductive hypothesis,

$$M_{11} = u_{22} \cdot u_{33} \cdots u_{nn}$$

Therefore,

$$\det(U) = u_{11} \cdot u_{22} \cdot u_{33} \cdots u_{nn} = \prod_{i=1}^{n} u_{ii}$$

Hence the theorem holds for every $n \geq 1$. $\square$

2. Elementary row operations and the determinant

2.1 Three types of elementary row operations

There are three elementary row operations. We examine how each affects the determinant.

Operation 1: Swap two rows

$$R_i \leftrightarrow R_j$$

Effect: The sign of the determinant is flipped (alternating property).

The determinant is a signed area (signed volume in 3D). Swapping two sides of a parallelogram reverses its orientation, so the sign flips.

r1 r2 + → swap r2 r1 − orientation reversed

Operation 2: Multiply a row by $c$

$$R_i \leftarrow c \cdot R_i$$

Effect: The determinant is multiplied by $c$ (multilinearity).

Stretching one side of a parallelogram by a factor of $c$ scales the area by $c$ as well.

r1 r2 S → scale r1 by c c·r1 r2 cS area scaled by c

Operation 3: Add a scalar multiple of another row to a row

$$R_i \leftarrow R_i + c \cdot R_j$$

Effect: The determinant is unchanged.

This corresponds to a shear. Sliding one side of a parallelogram in the direction of the other does not change the base or the height, so the area is preserved.

rj ri h S → shear c·rj ri+c·rj rj h S same base and height

2.2 Why Operation 3 leaves the determinant unchanged

By multilinearity (linearity in a single row when all other rows are held fixed), replacing the $i$-th row by $\boldsymbol{r}_i + c\boldsymbol{r}_j$ decomposes the determinant as follows:

$$\det(\ldots, \boldsymbol{r}_i + c\boldsymbol{r}_j, \ldots, \boldsymbol{r}_j, \ldots) = \det(\ldots, \boldsymbol{r}_i, \ldots, \boldsymbol{r}_j, \ldots) + c \cdot \det(\ldots, \bbox[#fff9c4,3px]{\boldsymbol{r}_j}, \ldots, \bbox[#fff9c4,3px]{\boldsymbol{r}_j}, \ldots)$$

The second term has two identical rows (both equal to $\boldsymbol{r}_j$ at the $i$-th and $j$-th positions), so it vanishes by the alternating property. Hence the determinant equals the original.

3. Algorithm for computing the determinant

3.1 General strategy

  1. Reduce the matrix to upper triangular form using elementary row operations.
  2. Record the operations performed (number of row swaps, scalar multiplications).
  3. Compute the product of the diagonal entries of the upper triangular matrix.
  4. Correct the result based on the recorded operations.

3.2 Worked example

Compute $\det\begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}$.

Target: make the $(2,1)$ and $(3,1)$ entries zero

Step 1: $R_2 \leftarrow R_2 - 2R_1$ (determinant unchanged)

$$\begin{pmatrix} 2 & 1 & 1 \\ \color{#c62828}{\mathbf{0}} & \color{#c62828}{1} & \color{#c62828}{1} \\ 8 & 7 & 9 \end{pmatrix}$$

Step 2: $R_3 \leftarrow R_3 - 4R_1$ (determinant unchanged)

$$\begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ \color{#c62828}{\mathbf{0}} & \color{#c62828}{3} & \color{#c62828}{5} \end{pmatrix}$$

Target: make the $(3,2)$ entry zero

Step 3: $R_3 \leftarrow R_3 - 3R_2$ (determinant unchanged)

$$\begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ \color{#c62828}{0} & \color{#c62828}{\mathbf{0}} & \color{#c62828}{2} \end{pmatrix}$$

The matrix is now upper triangular, so:

$$\det(A) = 2 \times 1 \times 2 = 4$$

3.3 Computational complexity

The complexity of this method is $O(n^3)$, which is dramatically more efficient than the $O(n!)$ of cofactor expansion.

This method (LU decomposition) is what practical numerical linear algebra libraries use.

4. The determinant emerges from Gaussian elimination

4.1 A change of perspective

So far we have explained things from the viewpoint "use row operations to compute the determinant." Historically, however, the order is reversed:

Key insight

When the forward elimination of Gaussian elimination is applied to a system of linear equations, the product of the diagonal entries of the resulting upper triangular matrix coincides with the determinant.

Historical background

Gottfried Wilhelm Leibniz (1693) first treated expressions equivalent to the determinant in his correspondence while studying the elimination of unknowns in systems of linear equations.

Gabriel Cramer (1750) noticed, in the process of solving systems of linear equations, that a common expression appears in the denominator of the solutions. This later became the seed for the systematic notion of the "determinant."

Alexandre-Théophile Vandermonde (1771) was groundbreaking in studying the determinant as an object in its own right, providing ideas that became foundational for subsequent theory.

Later, Augustin-Louis Cauchy (1812) gave the definition as a multilinear alternating form and the systematic theory, completing the modern theory of determinants. In other words, the determinant was "discovered" through the process of solving systems of linear equations; it was not an abstract quantity defined from the outset.

References

4.2 The reduction process for a general 2×2 matrix

We first verify this for a simple 2×2 matrix. Apply forward elimination to a general 2×2 matrix $A = (a_{ij})$:

$$A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}$$

The operation $R_2 \leftarrow R_2 - \dfrac{a_{21}}{a_{11}} R_1$ yields the following upper triangular matrix (after combining fractions):

$$U = \begin{pmatrix} \bbox[#fff9c4,3px]{a_{11}} & a_{12} \\[0.8em] 0 & \bbox[#fff9c4,3px]{\dfrac{a_{11}a_{22} - a_{21}a_{12}}{a_{11}}} \end{pmatrix} \tag{4.1}$$

Taking the product of the diagonal entries, $a_{11}$ cancels:

$$u_{11} \times u_{22} = \cancel{a_{11}} \times \dfrac{a_{11}a_{22} - a_{21}a_{12}}{\cancel{a_{11}}} = a_{11}a_{22} - a_{21}a_{12} = \det(A)$$

4.3 The reduction process for a general 3×3 matrix

Next, we perform the same computation for a 3×3 matrix. Applying forward elimination to a general 3×3 matrix $A = (a_{ij})$ yields the following upper triangular matrix:

$$U = \begin{pmatrix} \bbox[#fff9c4,3px]{a_{11}} & a_{12} & a_{13} \\[1.2em] 0 & \bbox[#fff9c4,3px]{\dfrac{a_{11}a_{22} - a_{21}a_{12}}{a_{11}}} & \dfrac{a_{11}a_{23} - a_{21}a_{13}}{a_{11}} \\[1.2em] 0 & 0 & \bbox[#fff9c4,3px]{\dfrac{(a_{11}a_{22} - a_{21}a_{12})(a_{11}a_{33} - a_{31}a_{13}) - (a_{11}a_{32} - a_{31}a_{12})(a_{11}a_{23} - a_{21}a_{13})}{a_{11}(a_{11}a_{22} - a_{21}a_{12})}} \end{pmatrix}$$

The product of the diagonal entries is:

$$u_{11} \times u_{22} \times u_{33} = \cancel{a_{11}} \times \dfrac{\bcancel{a_{11}a_{22} - a_{21}a_{12}}}{\cancel{a_{11}}} \times \dfrac{\det(A)}{\bcancel{a_{11}a_{22} - a_{21}a_{12}}} = \det(A)$$

4.4 The general case

When Gaussian elimination is applied to an $n \times n$ matrix $A$:

  1. Forward elimination produces an upper triangular matrix $U$.
  2. The diagonal entries $u_{11}, u_{22}, \ldots, u_{nn}$ are computed in sequence.
  3. Their product satisfies $u_{11} \cdot u_{22} \cdots u_{nn} = \det(A)$ (correct the sign if row swaps were used).

Relation to Cramer's rule

Cramer's rule, $x_j = \dfrac{\det(A_j)}{\det(A)}$, is a tidy reorganization of the algebraic result of Gaussian elimination. The $\det(A)$ in the denominator is computed automatically in the course of elimination.

Historically, the concept of the determinant was extracted by tidying up the common expression that appeared in the denominator while solving systems of linear equations.

4.5 The meaning of a zero determinant

If, during Gaussian elimination, a diagonal entry becomes zero (and cannot be remedied by row swaps), so that the computation cannot proceed, then:

  • this means $\det(A) = 0$;
  • the system of linear equations has no unique solution (either no solution or infinitely many);
  • the inverse matrix $A^{-1}$ does not exist.

5. Pivoting and row swaps

5.1 Problem: zero diagonal entry

If we try to triangularize $\begin{pmatrix} 0 & 1 \\ 2 & 3 \end{pmatrix}$, the $(1,1)$ entry is $0$ and we cannot divide by it.

5.2 Solution: row swap

Swap rows to bring a nonzero entry into the diagonal position:

$$\begin{pmatrix} 0 & 1 \\ 2 & 3 \end{pmatrix} \xrightarrow{R_1 \leftrightarrow R_2} \begin{pmatrix} 2 & 3 \\ 0 & 1 \end{pmatrix}$$

Since rows were swapped once, the sign of the determinant flips:

$$\det\begin{pmatrix} 0 & 1 \\ 2 & 3 \end{pmatrix} = -\det\begin{pmatrix} 2 & 3 \\ 0 & 1 \end{pmatrix} = -(2 \times 1) = -2$$

5.3 When all diagonal entries can be made zero

If no row swap can place a nonzero entry at the diagonal, then $\det(A) = 0$.

6. Properties of the determinant viewed via row operations

6.1 $\det(I) = 1$

The identity matrix is already upper triangular, and every diagonal entry is $1$:

$$\det(I) = 1 \times 1 \times \cdots \times 1 = 1$$

6.2 $\det(AB) = \det(A) \det(B)$

Elementary row operations can be written as left multiplication by elementary matrices. Combining this fact with the effect of row operations on the determinant yields the product rule.

6.3 $\det(A^T) = \det(A)$

By applying the triangularization algorithm to columns instead of rows, one can see the relation between the transpose and the determinant.

7. Advantages and disadvantages of this approach

7.1 Advantages

  • Directly tied to a computational algorithm: an actually efficient $O(n^3)$ method.
  • Unified with Gaussian elimination: the same technique used for solving linear systems.
  • Applicable to numerical computation: implemented as LU decomposition.

7.2 Disadvantages

  • Procedural rather than conceptual: it is less clear "why this is correct."
  • Geometric meaning is indirect: the relation to volume is not obvious.
  • Prerequisites are required: the effects of elementary row operations must be known in advance.

8. Summary

Key points

  • Determinant of an upper triangular matrix = product of diagonal entries
  • Row swap: sign flips
  • Scalar multiplication of a row: determinant is multiplied by the same scalar
  • Adding a multiple of another row: determinant unchanged
  • Complexity: $O(n^3)$, efficient

Computational formula

$$\det(A) = (-1)^{(\text{number of row swaps})} \times (\text{product of diagonal entries of the upper triangular form})$$

Related pages:

Frequently Asked Questions

What is the procedure for computing a determinant via elementary row operations?

(1) Use a combination of row swaps (sign flips), scalar multiplications of rows, and row additions to form an upper triangular matrix $U$. (2) Compute $\det(A)=(-1)^s \cdot c_1\cdots c_k \cdot \prod_i u_{ii}$, where $s$ is the number of swaps and $c_i$ are the scalar factors. The procedure runs in $O(n^3)$ time and is foundational in numerical linear algebra.

What is pivoting in Gaussian elimination?

When a diagonal entry (pivot) is zero or extremely small in Gaussian elimination, numerical error grows. Partial pivoting (selecting the row with the largest absolute value as the pivot) or complete pivoting (selecting the largest entry in both rows and columns) is used to ensure numerical stability. The same care is required when computing determinants.

What is the relationship between LU decomposition and the determinant?

For LU decomposition $PA=LU$ (where $P$ is a permutation matrix), $\det(A)=\det(P^{-1})\det(L)\det(U)=(-1)^s\cdot 1\cdot\prod u_{ii}$ holds, since $L$ is unit lower triangular ($\det(L)=1$) and $s$ is the sign of the permutation. This is the most practical algorithm for computing determinants.