ML Wiki

Determinants

A determinant is a value associated with a square matrix $A$

• it provides important information about invertability of the matrix
• it's denoted as $\text{det } A$ or sometimes $| A |$

Defining Properties

These properties define what a determinant is (they don't say how to compute it)

Property 1: Determinant of $I$

• $\text{det } I = 1$

Property 2: Sign Reversal

• let $A'$ be a matrix $A$ with two rows exchanged, then $\text{det } A' = \text{det } A$

Consequence of property 2:

• for a Permutation Matrix $P$
• $\text{det } P = 1$ if if has even number of row exchanges
• and $\text{det } P = -1$ is it has odd number of exchanges

Property 3: Linearity

• determinant is a linear function of a row - if all other rows stays the same
• 3a) $\begin{vmatrix} t a_{11} & t a_{12} & t a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix} = t \cdot \begin{vmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix}$

• 3b) $\begin{vmatrix} a_{11} + a'_{11} & a_{12} + a'_{12} & a_{13} + a'_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix} = \begin{vmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix} + \begin{vmatrix} a'_{11} & a'_{12} & a'_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix}$

• applies to all the rows: we always can put any row to the first position (property 2), then apply the property 3, and then put the row back

Other properties

These properties are consequences of the defining properties

Property 4: Equal Rows

• if 2 rows are equal, then $\text{det } A = 0$
• proof: if we exchange two rows, nothing happens to the matrix, but property 2 says the sign should be reversed

Property 5: Linear Combinations

• if we subtract a multiple of row $i$ from the row $k$, the determinant remains the same
• for Gaussian Elimination it means that $\text{det } A = \text{det } U$
• $\begin{vmatrix} a_{11} & a_{12} \\ a_{21} - c a_{11} & a_{22} - c a_{12} \\ \end{vmatrix} \ \mathop{=}\limits^{3^{\circ}} \ \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{vmatrix} - c \begin{vmatrix} a_{11} & a_{12} \\ a_{11} & a_{12} \\ \end{vmatrix} \ \mathop{=}\limits^{4^{\circ}} \ \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{vmatrix} - c 0 = \begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{vmatrix}$

Property 6: Zero Row

• if we have a rows full of zeros, then $\text{det } A = 0$
• $c \cdot \begin{vmatrix} a_{11} & a_{12} \\ 0 & 0 \\ \end{vmatrix} = \begin{vmatrix} a_{11} & a_{12} \\ c \cdot 0 & c \cdot 0 \\ \end{vmatrix} = \begin{vmatrix} a_{11} & a_{12} \\ 0 & 0 \\ \end{vmatrix}$

• the only possible way for this to be valid is when the det is 0

Property 7: Determinant of $U$

• for upper-triangular matrix $U$, determinant of $U$ is the product of elements on the main diagonal
• $\begin{vmatrix} d_1 & 0 & 0 \\ a_{21} & d_2 & 0 \\ a_{31} & a_{32} & d_3 \\ \end{vmatrix} = \prod d_i$

Why?

• if we can do $LU$ factorization, then we can do $LDU$ factorization as well
• and by property 5, $\text{det } A = \text{det } U = \text{det } D$
• $\begin{vmatrix} d_1 & 0 & 0 \\ 0 & d_2 & 0 \\ 0 & 0 & d_3 \\ \end{vmatrix} \ \mathop{=}\limits^{3^{\circ}} \ d_1 \cdot \begin{vmatrix} 1 & 0 & 0 \\ 0 & d_2 & 0 \\ 0 & 0 & d_3 \\ \end{vmatrix} = d_1 d_2 \cdot \begin{vmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & d_3 \\ \end{vmatrix} = d_1 d_2 d_3 \cdot \text{det } I = \prod d_i$

Consequence:

• the easiest way to compute the determinant is to apply $A = LU$ Factorization and then compute $\text{det } U = \prod_i d_i$
• note that you should be careful with row exchanges!
• what if some $d_i = 0$? then $\text{det } U = 0$

Property 8: Singularity Test

• when $A$ is singular, then $\text{det } A = 0$
• when $A$ is non-singular, then $\text{det } A \ne 0$
• it makes it a good test for invertability

Why?

• directly follows from property 7
• compute $A = LU$ factorization
• if the matrix is singular, then at least one $d_i = 0$, then $\text{det } U = 0$
• if $A$ is not singular, then no pivot is 0, thus $\text{det } U \ne 0$

Property 9: Product Rule

• $\text{det } AB = \text{det } A \cdot \text{det } B$

Proof:

• consider ratio $D(A) = \cfrac{\text{det } AB}{\text{det } B}$ (for $\text{det } B \ne 0$)
• note that $D(A)$ obeys the properties 1, 2, 3 of $\text{det } A$
• property 1: if $A = I$, then $D(A) = \cfrac{\text{det } IB}{\text{det } B} = 1$
• property 2: if we exchange two rows of $A$, the same rows are exchanged for $AB$, thus $\text{det } AB$ changes the sign, and so does $D(A)$
• property 3:
• 3a) multiply row 1 of $A$ by $c$, then row 1 of $AB$ also gets multiplied by $c$
• 3b) add $[a'_{11}, \ ... \ , a'_{1n}]$ to row 1 of $A$ - then row 1 of $AB$ gets row 1 of $A' B$ (where $A'$ is $A$ with row 1 replaced)
• illustration: $\text{det } \begin{bmatrix} a_{11} + a'_{11} & a_{12} + a'_{12} \\ ... & ... \\ \end{bmatrix} \begin{bmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \\ \end{bmatrix} =$ $\begin{vmatrix} (a_{11} + a'_{11}) b_{11} + (a_{12} + a'_{12}) b_{21} & (a_{11} + a'_{11}) b_{12} + (a_{12} + a'_{12}) b_{22}\\ ... & ... \\ \end{vmatrix} =$ $\begin{vmatrix} a_{11} b_{11} + a_{12} b_{21} & a_{11} b_{12} + a_{12} b_{22}\\ ... & ... \\ \end{vmatrix} +$ $\begin{vmatrix} a'_{11} b_{11} + a'_{12} b_{21} & a'_{11} b_{12} + a'_{12} b_{22}\\ ... & ... \\ \end{vmatrix}$

• thus $D(A)$ obeys the same properties as $\text{det } A$, so $D(A) = \text{det } A$ and we have $\text{det } AB = \text{det } A \cdot \text{det } B$

Consequence:

• $I = A^{-1} A$
• $\text{det }I = \text{det }A^{-1} A$
• $\text{det }A^{-1} \cdot \text{det } A = 1$
• $\text{det }A^{-1} = \cfrac{1}{\text{det } A}$

Consequence 2:

• now can take into account the permutation matrix $P$ in the $PA = LU$ decomposition
• $\text{det } PA = \text{det } LU$
• $\text{det } P \cdot \text{det } A = \text{det } L \cdot \text{det } U$
• $\text{det } P = \pm 1$, $\text{det } L = 1$ (elements on the diagonal of $L$ are 1's)
• so $\text{det } A = \text{det } P \cdot \text{det } U$

Property 10: Transposition

$\text{det } A^T = \text{det } A$

• The transpose of $A$ has the same determinant as $A$

Proof:

• consider $PA = LU$ factorization
• transpose: $A^T P^T = U^T L^T$
• take determinant, apply property 10 and compare $\text{det }P \cdot \text{det }A = \text{det } L \cdot \text{det } U$ with $\text{det }A^T \cdot \text{det }P^T = \text{det }U^T \cdot \text{det } L^T$
• $\text{det } L = \text{det } L^T = 1$ (both have 1's on the diagonal)
• $\text{det } U = \text{det } U^T = \prod d_i$ - they have the same elements on the diagonal
• finally $\text{det } P = \text{det } P^T$ because $P^T P = I$ ($P$ is orthogonal) and by property 9 have $\text{det } P^T \cdot \text{det } P = 1$. That happens only when they agree on the sign.
• thus, $\text{det } A^T = \text{det } A$

Consequence

• all the properties above are applied to rows, but the property #10 says that we can apply them to columns as well

Calculating Determinants

There are several possible ways to calculate determinants:

• the Determinant Formula
• the Pivot Formula
• Cofactors

Determinant Formula

Let's try to find out how we can compute the determinant using the properties

$2 \times 2$ case

• $\begin{vmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{vmatrix} = \ ...$

• can use the property 3 to divide the problem into smaller parts, and solve them separately
• $... \ = \begin{vmatrix} a_{11} + 0 & 0 + a_{12} \\ a_{21} & a_{22} \\ \end{vmatrix} \ \mathop{=}\limits^{3^{\circ}} \ \begin{vmatrix} a_{11} & 0 \\ a_{21} & a_{22} \\ \end{vmatrix} + \begin{vmatrix} 0 & a_{12} \\ a_{21} & a_{22} \\ \end{vmatrix} = \underbrace{\begin{vmatrix} a_{11} & 0 \\ a_{21} & 0 \\ \end{vmatrix}}_{0} + \begin{vmatrix} a_{11} & 0 \\ 0 & a_{22} \\ \end{vmatrix} + \begin{vmatrix} 0 & a_{12} \\ a_{21} & 0 \\ \end{vmatrix} + \underbrace{\begin{vmatrix} 0 & a_{12} \\ 0 & a_{22} \\ \end{vmatrix}}_{0} = \ ...$

• by property 6 (zero row) and 10 (determinant of transpose), we know that some parts are 0. so we're left with
• $... \ = \begin{vmatrix} a_{11} & 0 \\ 0 & a_{22} \\ \end{vmatrix} + \begin{vmatrix} 0 & a_{12} \\ a_{21} & 0 \\ \end{vmatrix} = \ ...$

• now can change the rows of the second summand by property 2 (sign reversal) and get
• $... \ = \begin{vmatrix} a_{11} & 0 \\ 0 & a_{22} \\ \end{vmatrix} - \begin{vmatrix} a_{21} & 0 \\ 0 & a_{12} \\ \end{vmatrix} = a_{11}a_{22} - a_{21}a_{12}$

$3 \times 3$ case

Can do the same for $3 \times 3$ matrices

• $\begin{vmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\\ \end{vmatrix} = \ ...$

• we follow the same divide and conquer approach
• most of the terms will go away because they will be equal to 0
• the "survivers" will have one non-zero entry from each row
• so for $3 \times 3$ we have:
• $... \ = \begin{vmatrix} a_{11} & 0 & 0\\ 0 & a_{22} & 0\\ 0 & 0 & a_{33}\\ \end{vmatrix} + \begin{vmatrix} a_{11} & 0 & 0\\ 0 & 0 & a_{23}\\ 0 & a_{32} & 0\\ \end{vmatrix} + \begin{vmatrix} 0 & a_{12} & 0\\ a_{21} & 0 & 0\\ 0 & 0 & a_{33}\\ \end{vmatrix} + \begin{vmatrix} 0 & a_{12} & 0\\ 0 & 0 & a_{23}\\ a_{31} & 0 & 0\\ \end{vmatrix} + \begin{vmatrix} 0 & 0 & a_{13}\\ a_{21} & 0 & 0\\ 0 & a_{32} & 0\\ \end{vmatrix} + \begin{vmatrix} 0 & 0 & a_{13}\\ 0 & a_{22} & 0\\ a_{31} & 0 & 0\\ \end{vmatrix}$

• let's have a closer look at each of them
• $\begin{vmatrix} a_{11} & 0 & 0\\ 0 & a_{22} & 0\\ 0 & 0 & a_{33}\\ \end{vmatrix} = a_{11}a_{22}a_{33}$, diagonal and nice

• $\begin{vmatrix} a_{11} & 0 & 0\\ 0 & 0 & a_{23}\\ 0 & a_{32} & 0\\ \end{vmatrix} = - a_{11}a_{23}a_{32}$ - need 1 row exchange to transform it to $I$-like form

• $\begin{vmatrix} 0 & a_{12} & 0\\ a_{21} & 0 & 0\\ 0 & 0 & a_{33}\\ \end{vmatrix} = - a_{12}a_{21}a_{33}$ - also 1 flip away

• $\begin{vmatrix} 0 & a_{12} & 0\\ 0 & 0 & a_{23}\\ a_{31} & 0 & 0\\ \end{vmatrix} = a_{12}a_{23}a_{31}$ - 2 exchanges,

• $\begin{vmatrix} 0 & 0 & a_{13}\\ a_{21} & 0 & 0\\ 0 & a_{32} & 0\\ \end{vmatrix} = a_{13}a_{21}a_{32}$ - 2 exchanges

• $\begin{vmatrix} 0 & 0 & a_{13}\\ 0 & a_{22} & 0\\ a_{31} & 0 & 0\\ \end{vmatrix} = -a_{13}a_{22}a_{31}$ - 3 exchanges

So, the formula for $3 \times 3$:

• $\begin{vmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\\ \end{vmatrix} = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33} - a_{13}a_{22}a_{31}$

• or, schematically:
• $n \times n$ case: "Big Formula"

The big formula:

• we consider all $n!$ possible permutation matrices $P$
• why $n!$? we can choose an element from the row 1 in $n$ ways, an element from the row 2 in $n - 1$ ways, ..., the last - in one way
• $\text{det } A = \sum\limits_{\text{$n!$permutations$P$}} \text{det } P \cdot a_{1\alpha_1} a_{2\alpha_2} ... a_{n\alpha_n}$
• where $\boldsymbol \alpha = (\alpha_1, \ ... \ , \alpha_n)$ is a Permutation of $(1, \ ... \ , n)$

The Pivot Formula

The easiest way is to use the properties 2, 5, 7 and 9:

• do the factorization $PA = LU$
• know that $\text{det } A = \text{det } P \cdot \text{det } U$
• if one of the pivots is 0, then $\text{det } A = 0$
• if $P$ is $\pm 1$, depending on the number of permutations, and $\text{det } U = \prod d_i$

Cofactors

Cofactors give a way to break $n \times n$ determinant to $(n - 1) \times (n - 1)$ determinants

$3 \times 3$ Case: Intuition

Suppose $A$ is a $3 \times 3$ matrix

• $\begin{vmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\\ \end{vmatrix} = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} - a_{11}a_{23}a_{32} - a_{12}a_{21}a_{33} - a_{13}a_{22}a_{31}$

• let's group them
• $\text{det } A = a_{11} (a_{22}a_{33} - a_{23}a_{32}) + a_{12} (-1) (a_{21}a_{33} - a_{23} a_{33}) + a_{13} (a_{21}a_{32} - a_{22}a_{31})$
• note that now in parentheses we have determinants of smaller matrices!
• for $a_{11}$ we have $a_{22}a_{33} - a_{23}a_{32} = \begin{vmatrix} a_{22} & a_{23}\\ a_{32} & a_{33}\\ \end{vmatrix}$

• for $a_{12}$ we have $- (a_{21}a_{33} - a_{23} a_{33}) = - \begin{vmatrix} a_{21} & a_{23}\\ a_{31} & a_{33}\\ \end{vmatrix}$ (note the $-$ sign!)

• for $a_{13}$ we have $a_{21}a_{32} - a_{22}a_{31} = \begin{vmatrix} a_{21} & a_{22}\\ a_{31} & a_{32}\\ \end{vmatrix}$

• these are co-factors of $a_{11}, a_{12}, a_{13}$ respectively
• so we can write this as
• $\begin{vmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\\ \end{vmatrix} = \begin{vmatrix} a_{11} & 0 & 0\\ 0 & a_{22} & a_{23}\\ 0 & a_{32} & a_{33}\\ \end{vmatrix} - \begin{vmatrix} 0 & a_{12} & 0\\ a_{21} & 0 & a_{23}\\ a_{31} & 0 & a_{33}\\ \end{vmatrix} + \begin{vmatrix} 0 & 0 & a_{13}\\ a_{21} & a_{22} & 0\\ a_{31} & a_{32} & 0\\ \end{vmatrix}$

Cofactors

a cofactor of $a_{ij}$ is $C_{ij}$

• $C_{ij}$ is a determinant of a $n - 1$ matrix - it's a matrix $A$ with row $i$ and column $j$ removed
• note that we can have a minus sign before some of the cofactors
• we have $C_{ij}$ with $-$ if $i+j$ is odd, and $+$ if $i+j$ is even
• so for $3 \times 3$ matrix we take signs this way: $\begin{vmatrix} + & - & + \\ - & + & - \\ + & - & + \\ \end{vmatrix}$

a minor of $a_{ij}$ is $M_{ij}$

• it's the same as cofactor, but always with the same sign

The Cofactor Formula

We can take co-factors along any row or column

• suppose we take it along row 1
• then the formula is $\text{det } A = a_{11} C_{11} + a_{12} C_{12} + \ ... \ + a_{1n} C_{1n}$

Applications

What can we do with determinants?

Cramer's Rule

through the Cramer's Rule:

Volume

$\text{det } A$ = volume of a parallelepiped formed by vector-rows of $A$

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

• $\mathbf r_1 = \Big[a_{11} \ \ a_{12} \ \ a_{13} \Big]$
• $\mathbf r_2 = \Big[a_{21} \ \ a_{22} \ \ a_{23} \Big]$
• $\mathbf r_3 = \Big[a_{31} \ \ a_{32} \ \ a_{33} \Big]$ $| \text{det } A|$ is the volume of the box formed by vectors $\mathbf r_1, \mathbf r_2, \mathbf r_3$

To check if this is indeed true, we need to verify that the volume obeys the 3 defining properties

• $A = I$ works, the volume is 1
• property 2: reversing two rows changes the sign (don't care), but the volume remains the same - true
• linearity:
• 3a. suppose we double one edge: the volume double
• 3b. see pictorially
• Area of Triangle

We know how to compute the area of a square

• so we can compute the area of a triangle!
• let $A$ be $2 \times 2$ matrix, $A = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \\ \end{bmatrix}$

• the area of a triangle that starts in origin is $\cfrac{1}{2} \text{det } A = \cfrac{1}{2} (a_{11} \, a_{22} - a_{12} \, a_{21})$
• What is it doesn't start in origin?

• • then we calculate it by taking the following determinant:
• $\begin{vmatrix} x_1 & y_1 & 1 \\ x_1 & y_1 & 1 \\ x_1 & y_1 & 1 \\ \end{vmatrix}$