ads Computation

Section C.2 Computation

Our definition of determinant can be applied to estimate the worst case for the time to evaluate an

n \times n

determinant. Let

M (n)

be the number of multiplications to evaluate an

n \times n

determinant. Then we have

M (2) = 2 .

To determine the value of

M (3)

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,

M (3) = 3 M (2) + 3 = 9 .

Using the same logic in general, we have

M (n) = n M (n - 1) + n .

The formula can be derived to be

M (n) = n! \sum_{k = 1}^{n} \frac{1}{k!} .

For large

n

this is approximately

e \cdot n! .

Fortunately, there are ways to reduce the number of multiplications using properties of determinants, which we list here without proof.

🔗

Theorem C.2.1. Properties of Determinants.

🔗

Let

A

and

B

n \times n

matrices, where

n \geq 2 .

$| A |$ can be found by expanding along any row or any column.
If two rows (or columns) of $A$ are interchanged, $| A |$ changes sign.
The value of a determinant is unchanged if a multiple of one row (or column) of $A$ is added to another row (or column) of $A$ .
If one row (or column) of a matrix $A$ is multiplied by a constant $c,$ then the value of $| A |$ is multiplied by $c .$
$| A B | = | A | \cdot | B | .$
$| I | = 1$ where $I$ is the $n \times n$ identity matrix.

🔗

Based on these properties, here are a few corollaries.

🔗

Corollary C.2.2. Further Properties.

🔗

Let

A

and

B

n \times n

matrices, where

n \geq 2 .

If a row (or column) of $A$ consists entirely of zeros, then $| A | = 0 .$
If a matrix $A$ has two equal rows (or columns) then $| A | = 0 .$
If any row (or column) of $A$ is a scalar multiple of any other row (or column) of $A,$ then $| A | = 0 .$
$| A^{- 1} | = \frac{1}{| A |}$ , if $A^{- 1}$ exists.

Example C.2.3. Computatation of a determinant by row reduction.

We will apply some of these properties, most notably the first and third of Theorem 1, 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

A = (\begin{matrix} 1 & 3 & 4 & 7 \\ 1 & 3 & 4 & 4 \\ 6 & 6 & 7 & 8 \\ 3 & 3 & 7 & 5 \end{matrix})

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,

B,

which has the same determinant.

xxxxxxxxxx
 
A=matrix([[1,3,4,7],[2,3,4,4],[5,6,7,4],[3,3,7,5]])
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.

xxxxxxxxxx
 
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.

| A | = | C | = 1 \cdot (- 3 \cdot (- 1 \cdot 4 - 3 \cdot (- 1))) = 3

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

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

You have attempted of activities on this page.

Prev Top Next