Determinant Calculation

Choosing a Method for the Matrix Size

The determinant definition leads to several calculation methods. $Direct formulas$ cover small matrices. For a large dense matrix, elimination or an $\mathrm{LU}$ factorization reduces the matrix to triangular form and avoids the factorial growth of recursive cofactor expansion.

Basic Case of a First Order Matrix

For matrices of size $1 \times 1$ , the determinant is very simple. If $A \in \mathbb{R}^{1 \times 1}$ with $A = (a_{11})$ , then:

\det A = a_{11}

For a $1\times1$ matrix, the determinant is its $only entry$ . Determinants of larger matrices are reduced to smaller cases through expansion or elimination.

Submatrix Concept

Before discussing the cofactor expansion method, we need to understand the concept of $submatrix$ . For matrix $A \in \mathbb{R}^{n \times n}$ and indices $i, j \in \{1, 2, \ldots, n\}$ , submatrix $A_{ij}$ is a matrix of size $(n-1) \times (n-1)$ obtained by removing row $i$ and column $j$ from matrix $A$ .

Look at an example for a $3 \times 3$ matrix. Suppose we have:

A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}

To get submatrix $A_{12}$ , we remove row $1$ and column $2$ :

A_{12} = \begin{pmatrix} \cancel{a_{11}} & \cancel{a_{12}} & \cancel{a_{13}} \\ a_{21} & \cancel{a_{22}} & a_{23} \\ a_{31} & \cancel{a_{32}} & a_{33} \end{pmatrix}

For submatrix $A_{23}$ , we remove row $2$ and column $3$ :

A_{23} = \begin{pmatrix} a_{11} & a_{12} & \cancel{a_{13}} \\ \cancel{a_{21}} & \cancel{a_{22}} & \cancel{a_{23}} \\ a_{31} & a_{32} & \cancel{a_{33}} \end{pmatrix}

This process applies to all combinations of rows and columns that are removed.

Cofactor Expansion

Cofactor expansion computes the determinant from smaller minors. We may expand along any fixed row $i$ :

\det A = \sum_{j=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Alternatively, we may expand along any fixed column $j$ :

\det A = \sum_{i=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

The term $(-1)^{i+j}\det A_{ij}$ is the $cofactor$ of $a_{ij}$ . The factor $(-1)^{i+j}$ creates the alternating checkerboard pattern of signs. Choosing a row or column with many zeros reduces the number of minors we need to evaluate.

Cofactor Expansion for a Third Order Matrix

Look at an example of cofactor expansion for a $3 \times 3$ matrix:

A = \begin{pmatrix} 2 & 1 & 3 \\ 0 & 4 & 1 \\ 1 & 2 & 0 \end{pmatrix}

We choose the $first row$ for expansion:

\begin{aligned} \det A &= 2 \cdot (-1)^{1+1} \det A_{11} \\ &\quad{}+ 1 \cdot (-1)^{1+2} \det A_{12} \\ &\quad{}+ 3 \cdot (-1)^{1+3} \det A_{13} \end{aligned}

The expansion may use any row or column. Every zero entry makes one cofactor term zero, so a row or column with many zeros leaves fewer terms to calculate.

Triangular and Diagonal Matrices

For some special types of matrices, determinant calculation becomes very simple. The shape of the matrix removes most of the terms before you expand anything, so the work shrinks to a $single product$ . Recognizing the shape first is what saves the effort.

For upper triangular matrix $R$ :

R = \begin{pmatrix} r_{11} & * & \cdots & * \\ 0 & r_{22} & \cdots & * \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{pmatrix}

Its determinant is:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

For lower triangular matrix $L$ :

L = \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ * & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ * & * & \cdots & l_{nn} \end{pmatrix}

Its determinant is:

\det L = l_{11} \cdot l_{22} \cdot \ldots \cdot l_{nn}

For diagonal matrix $D$ :

D = \begin{pmatrix} d_{11} & 0 & \cdots & 0 \\ 0 & d_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{nn} \end{pmatrix}

Its determinant is:

\det D = d_{11} \cdot d_{22} \cdot \ldots \cdot d_{nn}

For all three types of matrices, the determinant equals $the product of all main diagonal elements$ .

Elementary Matrices

Elementary matrices are matrices obtained from the identity matrix with one elementary row operation. The determinants of elementary matrices have values that are easy to calculate:

$Row-scaling matrix$ $S_i(\lambda)$ , with $\lambda \neq 0$ , that multiplies row $i$ by $\lambda$ :

$\det S_i(\lambda) = \lambda$
$Row-swap matrix$ $Q_i^j$ that swaps rows $i$ and $j$ :

$\det Q_i^j = -1$
$Transvection matrix$ $P_i^j(\lambda)$ that performs $R_i \leftarrow R_i + \lambda R_j$ :

$\det P_i^j(\lambda) = 1$

For swaps and transvections, the indices refer to $two distinct rows$ , so $i\neq j$ . A single row swap changes the sign of the determinant, while adding a multiple of one row to another leaves the determinant unchanged.

Gaussian Elimination for Determinant Calculation

Gaussian elimination, or equivalently an $\mathrm{LU}$ factorization, transforms a dense matrix into $upper triangular form$ . The determinant then follows from the diagonal entries and the recorded row operations.

Suppose we use only row additions and row swaps to transform $A$ into an upper triangular matrix $R$ . If there are $p$ row swaps, then:

\det A = (-1)^p \cdot \det R

Since $R$ is an upper triangular matrix:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

The calculation gives:

\det A = (-1)^p \cdot r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

If an algorithm scales a row during elimination, that scale factor must also be recorded and removed from the final product. In numerical computation, partial pivoting is normally used to avoid a zero pivot and reduce the effect of roundoff errors.

Operation Count

For a dense $n \times n$ matrix, the elimination or $\mathrm{LU}$ factorization requires about $\frac{2}{3}n^3 + O(n^2)$ floating-point operations. Multiplying the resulting diagonal entries requires only $O(n)$ additional work. A naive recursive cofactor expansion can grow like $O(n!)$ .

For a large unstructured matrix, the $cubic$ operation count of elimination is lower than the factorial growth of recursive cofactor expansion.

Computing a Third Order Determinant by Elimination

The following example computes a determinant with Gaussian elimination:

A = \begin{pmatrix} 0 & 3 & 3 \\ 2 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}

$Step 1$ : Swap rows $1$ and $3$ to get a $nonzero pivot$ :

\begin{pmatrix} 1 & 0 & 1 \\ 2 & 2 & 0 \\ 0 & 3 & 3 \end{pmatrix}

$Step 2$ : Eliminate the first column by subtracting $2$ times row $1$ from row $2$ :

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 3 & 3 \end{pmatrix}

$Step 3$ : Eliminate the second column by subtracting $1.5$ times row $2$ from row $3$ :

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 6 \end{pmatrix} = R

Since there is $one row swap$ ( $p = 1$ ):

\det A = (-1)^1 \cdot \det R

Choosing a Method for the Matrix Size

Basic Case of a First Order Matrix

For matrices of size $1 \times 1$ , the determinant is very simple. If $A \in \mathbb{R}^{1 \times 1}$ with $A = (a_{11})$ , then:

\det A = a_{11}

For a $1\times1$ matrix, the determinant is its $only entry$ . Determinants of larger matrices are reduced to smaller cases through expansion or elimination.

Submatrix Concept

Look at an example for a $3 \times 3$ matrix. Suppose we have:

A = \begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}

To get submatrix $A_{12}$ , we remove row $1$ and column $2$ :

A_{12} = \begin{pmatrix} \cancel{a_{11}} & \cancel{a_{12}} & \cancel{a_{13}} \\ a_{21} & \cancel{a_{22}} & a_{23} \\ a_{31} & \cancel{a_{32}} & a_{33} \end{pmatrix}

For submatrix $A_{23}$ , we remove row $2$ and column $3$ :

A_{23} = \begin{pmatrix} a_{11} & a_{12} & \cancel{a_{13}} \\ \cancel{a_{21}} & \cancel{a_{22}} & \cancel{a_{23}} \\ a_{31} & a_{32} & \cancel{a_{33}} \end{pmatrix}

This process applies to all combinations of rows and columns that are removed.

Cofactor Expansion

Cofactor expansion computes the determinant from smaller minors. We may expand along any fixed row $i$ :

\det A = \sum_{j=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Alternatively, we may expand along any fixed column $j$ :

\det A = \sum_{i=1}^{n} (-1)^{i+j} a_{ij}\det A_{ij}

Cofactor Expansion for a Third Order Matrix

Look at an example of cofactor expansion for a $3 \times 3$ matrix:

A = \begin{pmatrix} 2 & 1 & 3 \\ 0 & 4 & 1 \\ 1 & 2 & 0 \end{pmatrix}

We choose the $first row$ for expansion:

\begin{aligned} \det A &= 2 \cdot (-1)^{1+1} \det A_{11} \\ &\quad{}+ 1 \cdot (-1)^{1+2} \det A_{12} \\ &\quad{}+ 3 \cdot (-1)^{1+3} \det A_{13} \end{aligned}

The expansion may use any row or column. Every zero entry makes one cofactor term zero, so a row or column with many zeros leaves fewer terms to calculate.

Triangular and Diagonal Matrices

For upper triangular matrix $R$ :

R = \begin{pmatrix} r_{11} & * & \cdots & * \\ 0 & r_{22} & \cdots & * \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{pmatrix}

Its determinant is:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

For lower triangular matrix $L$ :

L = \begin{pmatrix} l_{11} & 0 & \cdots & 0 \\ * & l_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ * & * & \cdots & l_{nn} \end{pmatrix}

Its determinant is:

\det L = l_{11} \cdot l_{22} \cdot \ldots \cdot l_{nn}

For diagonal matrix $D$ :

D = \begin{pmatrix} d_{11} & 0 & \cdots & 0 \\ 0 & d_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{nn} \end{pmatrix}

Its determinant is:

\det D = d_{11} \cdot d_{22} \cdot \ldots \cdot d_{nn}

For all three types of matrices, the determinant equals $the product of all main diagonal elements$ .

Elementary Matrices

Elementary matrices are matrices obtained from the identity matrix with one elementary row operation. The determinants of elementary matrices have values that are easy to calculate:

$Row-scaling matrix$ $S_i(\lambda)$ , with $\lambda \neq 0$ , that multiplies row $i$ by $\lambda$ :

$\det S_i(\lambda) = \lambda$
$Row-swap matrix$ $Q_i^j$ that swaps rows $i$ and $j$ :

$\det Q_i^j = -1$
$Transvection matrix$ $P_i^j(\lambda)$ that performs $R_i \leftarrow R_i + \lambda R_j$ :

$\det P_i^j(\lambda) = 1$

Gaussian Elimination for Determinant Calculation

Suppose we use only row additions and row swaps to transform $A$ into an upper triangular matrix $R$ . If there are $p$ row swaps, then:

\det A = (-1)^p \cdot \det R

Since $R$ is an upper triangular matrix:

\det R = r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

The calculation gives:

\det A = (-1)^p \cdot r_{11} \cdot r_{22} \cdot \ldots \cdot r_{nn}

Operation Count

For a large unstructured matrix, the $cubic$ operation count of elimination is lower than the factorial growth of recursive cofactor expansion.

Computing a Third Order Determinant by Elimination

The following example computes a determinant with Gaussian elimination:

A = \begin{pmatrix} 0 & 3 & 3 \\ 2 & 2 & 0 \\ 1 & 0 & 1 \end{pmatrix}

$Step 1$ : Swap rows $1$ and $3$ to get a $nonzero pivot$ :

\begin{pmatrix} 1 & 0 & 1 \\ 2 & 2 & 0 \\ 0 & 3 & 3 \end{pmatrix}

$Step 2$ : Eliminate the first column by subtracting $2$ times row $1$ from row $2$ :

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 3 & 3 \end{pmatrix}

$Step 3$ : Eliminate the second column by subtracting $1.5$ times row $2$ from row $3$ :

\begin{pmatrix} 1 & 0 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 6 \end{pmatrix} = R

Since there is $one row swap$ ( $p = 1$ ):

\det A = (-1)^1 \cdot \det R