17.3.2: Computation

Our definition of determinant can be applied to estimate the worst case for the time to evaluate an determinant. Let be the number of multiplications to evaluate an determinant. Then we have To determine the value of we observe that this requires the computation of three minors, each a two by two matrix, and then a multiplication of each of them by the entries in row 1. Therefore, Using the same logic in general, we have The formula can be derived to be For large this is approximately Fortunately, there are ways to reduce the number of multiplications using properties of determinants, which we list here without proof.

Theorem : Properties of Determinants

Let and be matrices, where

1. can be found by expanding along any row or any column.
2. If two rows (or columns) of are interchanged, changes sign.
3. The value of a determinant is unchanged if a multiple of one row (or column) of is added to another row (or column) of .
4. If one row (or column) of a matrix is multiplied by a constant then the value of is multiplied by
6. where is the identity matrix.

Based on these properties, here are a few corollaries.

Corollary : Further Properties

Let and be matrices, where

1. If a row (or column) of consists entirely of zeros, then
2. If a matrix has two equal rows (or columns) then
3. If any row (or column) of is a scalar multiple of any other row (or column) of then
4. , if exists.

Example : Computation of a Determinant by Row Reduction

We will apply some of these properties, most notably the first and third of Theorem , to compute a four by four determinant without doing as many multiplications as expected. We will use SageMath to do the calculations for us. In SageMath, as in Python, numbering starts at zero, so we will describe the process using that numbering system. Let 

Our strategy will be to create a column that is mostly zero so that we can expand along that column and only need to compute one cofactor. That will be the 0th column. To do that we do the following row operations. We subtract row 0 from row 1, replacing row 1 with that result. Then we subtract six time row 0 from row 2, producing a new row 2. Finally, three times row 0 is subtracted from row 3 to produce a new row 3. The SageMath code below accomplishes this and produces a new matrix, , which has the same determinant.

view sourceprint?

1	A=matrix([[1,3,4,7],[2,3,4,4],[5,6,7,4],[3,3,7,5]])

2	B=matrix([A[0],A[1]-2*A[0],A[2]-5*A[0],A[3]-3*A[0]]);B

Expanding this matrix along the column zero, we need only compute a single three by three cofactor. We will go one step further and do row operations to get a matrix with zeros in rows 2 and 3 of column 1. The SageMath code below tells what we are doing.

view sourceprint?

1	C=matrix([B[0],B[1],B[2]-3*B[1],B[3]-2*B[1]]);C

We are at a point where we can do the final calculation very easily.

SageMath has a determinant function, det, that we can use to verify this calculation:

view sourceprint?

1	A=matrix([[1,3,4,7],[2,3,4,4],[5,6,7,4],[3,3,7,5]])

2

det(A)