Efficiently Computing the Determinant of a Matrix, Part 2: Determinant by Elementary Row Operations

By Nathan Reynoso on

Note: This post is part 2 of a 2-part series: part 1, part 2.

Computing the determinant by hand is often annoying, and using the cofactor method takes more time the larger the matrix. The most efficient way to compute the determinant of a matrix is through using elementary row operations. Through this process, we reduce the matrix to echelon form and take the operations we did on the rows to compute the determinant.

Our first step is to take any given matrix to echelon form, but we have to keep track of the row operations we apply to be able to use them later when computing the determinant. Below, I have a randomly generated a $3\times 3$ matrix:

$\begin{align*} \begin{bmatrix} 0 & 2 & 4\\ 7 & 24 & 1\\ 2 & 6 & 8 \end{bmatrix} \end{align*}$


The frst thing we would do is switch our top and bottom rows ($R_1$ and $R_3$). Then, we would divide our top row by 2 to get our pivot row for column $1$. We’ll need to keep a list of all numbers we divide any row by and the number of times we switch rows.

$\begin{align*} \begin{bmatrix} 1&3&4\\ 7&24&1\\ 0&2&4 \end{bmatrix} , \text{row divisors:(2), row swaps:(1)} \end{align*}$


Next we subtract $7\times R_{1}$ from $R_{2}$. After that we subtract $R_{2}$ from $R_{1}$.

$\begin{align*} \begin{bmatrix} 1&3&4\\ 0&3&20\\ 0&2&4 \end{bmatrix}, \text{row divisors:(2), row swaps:(1)} \end{align*}$


$\begin{align*} \begin{bmatrix} 1&0&-16\\ 0&3&-27\\ 0&2&4 \end{bmatrix}, \text{row divisors:(2), row swaps:(1)} \end{align*}$


Now we divide $R_{2}$ by 3, and subtract $2\times R_{2}$ from $R_{3}$. We can also divide $R_{3}$ by $22$ as well.

$\begin{align*} \begin{bmatrix} 1&0&-16\\ 0&1&-9\\ 0&0&1 \end{bmatrix},\text{row divisors:(2,3,22), row swaps:(1)} \end{align*}$


At this point we can see the matrix does reduce to the identity, so we can stop here. Now with the row divisors and swaps we collected we can use them to calculate the determinant. To get it, we take the product of the divisors and multiply it by $-1$ to the power of the number of row swaps:

$\begin{align*} (2\times 3\times 22)\times -1^{1} = -132 \end{align*}$


When computing the determinant using either the cofactor method or by using a calculator, we can see this is actually the determinant.

Implementation

Below is the actual code for computing the determinant via row operations that I implemented into my matrix class. The first thing it’s doing is making a copy of the matrix, so that we don’t mutate the original matrix. Then we make a variable called factors that will be what the method returns, and that’s what we multiply our dividing numbers by.

After, we ensure the matrix is square, otherwise you can’t compute the determinant. We then loop throw each row of the matrix, checking which row is the pivot row, and making sure the pivot row is where its supposed to be (in the position of the next column that needs a pivot). Once we have the pivot row in the correct position, we multiply the factors variable by the pivot number, and then reduce the column that number is in to $1$’s and $0$’s. Then we move on to the next row. After going through the whole matrix, we return the factors variable.

def calc_determinant(self):
    matrix = self.copy()
    factors = 1
    row_index = 0

    if matrix.num_cols != matrix.num_rows:
       return ("Non-square matrices have no determinant.")

    for col in range(matrix.num_cols):
        pivot = matrix.get_pivot_row(col)

        if pivot != None:
            if pivot != row_index:
                matrix = matrix.swap_rows(row_index, pivot)
                factors *= -1

            factors *= matrix.elements[pivot][col]
            matrix = matrix.normalize_row(row_index)
            matrix = matrix.clear_above(row_index)
            matrix = matrix.clear_below(row_index)
            row_index += 1

        else:
            mult_constant *= 0
            continue

    return factors


Time Complexity

When using this method to compute the determinant, the computation is relatively fast compared to other methods. Lets assume we have a $n \times n$ matrix that can be taken to echelon form, then we can easily find the maximum amount of computations needed to find the determinant using this method. Assuming that all the entries are not $1$, then for each row, you would divide by a number at some point, so that’s $n$ computations so far. For each row, you will also have to subtract it from all the other rows to make it the pivot row, which is $n-1$ more computations for $n$ rows, which is $n(n-1)$. This gives us $n+n(n-1) = n^2$ total computations.

This is much more efficient than computing the determinant via the cofactor method, which can take $n!$ operations.

Nathan Reynoso
-->