CXD Analytics - Essential Matrix Algebra for Data Science and Quantitative Finance: Determinants

Introduction

Data science and quantitative finance professionals need to have a strong mathematical foundation to best perform their work. Linear algebra is a foundational concept in data science, so let's explore the linear algebra concepts of:

Properties of Determinants
Laplace expansion
Leibniz Formula
Determinant via Gaussian Elimination

I created this blog post while studying the MITx MicroMasters Program in Finance. I return to this blog post from time to time to keep these topics fresh in my mind. This post is not meant to be a complete "course" on the topic. It is more in the form of my notes that I (and you) can review to stay sharp on these topics, or as a guide for further study.

Properties of Determinants

Determinants are an important concept in matrix algebra that plays a crucial role in various applications for data scientists and quantitative finance professionals. The determinant of a square matrix can help us determine if a matrix has an inverse, solve systems of linear equations, and calculate eigenvalues and eigenvectors.

Properties of Determinants

There are three defining properties of a determinant are:

Determinant of an identity matrix is always equal to 1
\(det(I)=1\)
Determinant changes sign under row interchange

When interchanging two rows (or columns) in a matrix, the determinant changes its sign. In other words, if matrix B is obtained from matrix A by interchanging two rows (or columns), then \(det(B) = -det(A)\).
Determinant is a linear function of first row

The determinant is a linear function of the first row, holding all other rows fixed. Here we are indicating a determinant with vertical bars around the matrix.

\( \begin{vmatrix}ka & kb \\ c & d\end{vmatrix} = k \begin{vmatrix} a & b \\ c & d\end{vmatrix} = k (ad - bc)\)

\( \begin{vmatrix}a + a' & b + b' \\ c & d\end{vmatrix} = \begin{vmatrix} a & b \\ c & d\end{vmatrix} + \begin{vmatrix} a' & b' \\ c & d\end{vmatrix} \)

There following are additional properties of determinants that follow from the above defining three properties of determinants:

The determinant of a matrix is a linear function of all rows. There is nothing special about just the first row.
The determinant of a diagonal matrix is the product of its diagonal elements: \(det(D) = d_{11}d_{22}...d_{nn}\).
The determinant of a matrix is equal to the determinant of its transpose: \(det(A) = det(A^T)\).
For two square matrices A and B, \(det(AB) = det(A) \times det(B)\).
If a matrix has a row or column of zeros, its determinant is zero.
Adding a multiple of one row (or column) to another row (or column) does not change the determinant value.
Scaling a row (or column) by a scalar 'k' scales the determinant by the same factor: \(det(kA) = k^n det(A)\), where n is the order of the matrix.
If a matrix has two equal rows, its determinant is equal to zero. This property can be demonstrated by interchanging the two equal rows and observing that the determinant does not change due to the row interchange. Since the determinant changes its sign when two rows are interchanged, it must be equal to its negative, which is only possible if the determinant is zero.

Determinant of 2x2 Matrix

For a 2x2 matrix \(A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}\), the determinant is calculated as \(det(A) = ad - bc\).

The inverse of a 2x2 matrix is:

\[ A^{-1} = \frac{1}{det(A)}\begin{bmatrix}d & -b \\ -c & a \end{bmatrix} \]

It should also be noted that if the determinant is not zero, then the inverse exists and \(Ax=b\) has a unique soultion. Further, if the determinant is non-zero, then \(Ax=0\) only has the solution \(x=0\)

Determinant of 3x3 Matrix

For a 3x3 matrix \(B = \begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}\)

The determinant is calculated as \(det(B) = a(ei - fh) - b(di - fg) + c(dh - eg)\).

Laplace Expansion

Laplace expansion is a technique used to compute the determinant of an nxn matrix by recursively calculating the determinants of smaller (n-1)x(n-1) matrices. The formula for Laplace expansion along the i-th row is given by:

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

where \(A_{ij}\) is the matrix obtained by removing the i-th row and the j-th column from matrix A.

Example Laplace Expansion

Let's consider the given 4x4 matrix A:

\[A = \begin{bmatrix} 5 & 2 & 7 & 2 \\ 7 & 2 & 8 & 1 \\ 2 & 7 & 3 & 9 \\ 1 & 6 & 3 & 2 \end{bmatrix}\]

To compute the determinant of A using the Laplace expansion along the first row, we can follow the formula:

\[det(A) = \sum_{j=1}^{4} (-1)^{1+j} A_{1j} det(A_{1j})\]

Expanding the sum, we get:

\[det(A) = (-1)^{1+1} (5) det(A_{11}) + (-1)^{1+2} (2) det(A_{12}) + (-1)^{1+3} (7) det(A_{13}) + (-1)^{1+4} (2) det(A_{14})\]

Which simplifies to:

\[det(A) = 5 det(A_{11}) - 2 det(A_{12}) + 7 det(A_{13}) - 2 det(A_{14}) \]

Now, for each \(A_{1j}\), we need to compute the determinant of the corresponding 3x3 matrix \(A_{1j}\), which can be done using the standard formula for 3x3 matrices:

\[A_{11} = \begin{bmatrix} 2 & 8 & 1 \\ 7 & 3 & 9 \\ 6 & 3 & 2 \end{bmatrix}, \quad A_{12} = \begin{bmatrix} 7 & 8 & 1 \\ 2 & 3 & 9 \\ 1 & 3 & 2 \end{bmatrix},\]

\[A_{13} = \begin{bmatrix} 7 & 2 & 1 \\ 2 & 7 & 9 \\ 1 & 6 & 2 \end{bmatrix}, \quad A_{14} = \begin{bmatrix} 7 & 2 & 8 \\ 2 & 7 & 3 \\ 1 & 6 & 3 \end{bmatrix}\]

Computing the determinants of these 3x3 matrices:

\(det(A_{11}) = (2)((3)(2) - (9)(3)) - (8)((7)(2) - (9)(6)) + (1)((7)(3) - (3)(6)) = 281\) \(det(A_{12}) = (7)((3)(2) - (9)(3)) - (8)((2)(2) - (9)(1)) + (1)((2)(3) - (3)(1)) = -104\) \(det(A_{13}) = (7)((7)(2) - (9)(6)) - (2)((2)(2) - (9)(1)) + (1)((2)(6) - (1)(7)) = -265\) \(det(A_{14}) = (7)((7)(3) - (3)(6)) - (2)((2)(3) - (3)(1)) + (8)((2)(6) - (1)(7)) = 55\)

Substituting the determinants back into the equation to get the final determinant of the 4x4 matrix A:

\(det(A) = 5 det(A_{11}) - 2 det(A_{12}) + 7 det(A_{13}) - 2 det(A_{14})\) \(det(A) = 5(281) - 2(-104) + 7(-265) - 2(55) = 1,405 + 208 - 1,855 - 110 = -352\)

So, the determinant of the given 4x4 matrix A is -352.

Leibniz Formula

The Leibniz formula provides a method for calculating the determinant of an nxn matrix using permutations. The formula is defined as follows:

\[det(A) = \sum_{\sigma \in S_k} (\text{sgn}(\sigma) \cdot \prod_{i=1}^n a_{i,\sigma(i)})\]

where \(\sigma\) is a permutation of the set \(\{1, 2, ..., n\}\), \(S_k\) is the set of all possible permutations of size \(k=n!\) and \(\text{sgn}(\sigma)\) is the sign of the permutation, which is +1 if the permutation is even and -1 if the permutation is odd.

A permutation is considered even if it can be expressed as an even number of transpositions (pairwise swaps), and it is considered odd if it can be expressed as an odd number of transpositions.

To calculate the sign of a permutation, you can use the inversion count method. The inversion count is the total number of pairs of elements that are out of order in the permutation. The sign of the permutation is +1 if the inversion count is even, and -1 if the inversion count is odd.

Here's a step-by-step explanation of how to calculate the sign of a permutation:

Start with the permutation, typically represented as a list or tuple of integers.
Initialize an inversion counter to zero.
Iterate through each element in the permutation, comparing it with the element that comes after it in the sequence:

If the current element is greater than the subsequent element, increment the inversion counter. Then move onto the next element in the permutation.

Determine the sign of the permutation based on the inversion count:

If the inversion count is even, the sign of the permutation is +1 (even permutation).
If the inversion count is odd, the sign of the permutation is -1 (odd permutation).

Example Using Leibniz Formula

Let's consider the given 4x4 matrix A:

\[A = \begin{bmatrix} 5 & 2 & 7 & 2 \\ 7 & 2 & 8 & 1 \\ 2 & 7 & 3 & 9 \\ 1 & 6 & 3 & 2 \end{bmatrix}\]

To compute the determinant of A using the Leibniz Formula, we first need to determine all possible permutations of size 4. There are 4! = 24 possible permutations. We will calculate the product of the matrix elements corresponding to each permutation and multiply it by the sign of that permutation. Finally, we sum up all these values to obtain the determinant.

The calculation involves 24 terms. We will show the first four here:

\[\text{sgn}((1, 2, 3, 4)) = +1, \quad \prod_{i=1}^4 a_{i,(1, 2, 3, 4)(i)} = a_{11}a_{22}a_{33}a_{44} = 5 \cdot 2 \cdot 3 \cdot 2\]

\[\text{sgn}((1, 2, 4, 3)) = -1, \quad \prod_{i=1}^4 a_{i,(1, 2, 4, 3)(i)} = a_{11}a_{22}a_{34}a_{43} = 5 \cdot 2 \cdot 9 \cdot 3\]

\[\text{sgn}((1, 3, 2, 4)) = -1, \quad \prod_{i=1}^4 a_{i,(1, 3, 2, 4)(i)} = a_{11}a_{23}a_{32}a_{44} = 5 \cdot 7 \cdot 7 \cdot 2\]

\[\text{sgn}((2, 1, 3, 4)) = -1, \quad \prod_{i=1}^4 a_{i,(1, 3, 2, 4)(i)} = a_{12}a_{21}a_{33}a_{44} = 2 \cdot 7 \cdot 3 \cdot 2\]

\[ \vdots \]

After calculating all 24 terms and summing them (using python or your favorite programming language), we will obtain the determinant of matrix A:

\[det(A) = -352\]

This result is consistent with the determinant we calculated using the Laplace expansion in the previous example.

Computing Determinant Using Gaussian Elimination

Gaussian elimination, which is discussed more deeply here is a specific form of row reduction used to solve linear systems of equations and compute determinants. When computing the determinant using Gaussian elimination, the goal is to transform the matrix into an upper triangular form. As with row reduction, the determinant of an upper triangular matrix is the product of its diagonal elements.

To perform Gaussian elimination, follow these steps:

Find the pivot element in the first column, which is a nonzero element with the smallest possible row index. If no such element exists, the matrix is singular, and the determinant is zero.
If the pivot element is not in the first row, interchange the rows to bring it to the first row. Remember that this changes the sign of the determinant.
Eliminate all nonzero elements below the pivot element by subtracting appropriate multiples of the pivot row from the rows below it. This row operation does not affect the determinant.
Repeat steps 1-3 for the remaining submatrix obtained by eliminating the first row and column.

When the matrix is in upper triangular form, compute the determinant as the product of its diagonal elements.

Remember to account for any row interchanges or row scaling operations performed during the Gaussian elimination process, as these affect the determinant. Row interchanges change the sign of the determinant, and row scaling multiplies the determinant by the scaling factor.

Gaussian elimination is an efficient methods for computing the determinant of a matrix, especially for larger matrices where direct methods such as the Laplace expansion or the Leibniz formula become impractical.

Example Using Gaussian Elimination

Let's consider the given 4x4 matrix A:

\[A = \begin{bmatrix} 5 & 2 & 7 & 2 \\ 7 & 2 & 8 & 1 \\ 2 & 7 & 3 & 9 \\ 1 & 6 & 3 & 2 \end{bmatrix}\]

To compute the determinant of A using Gaussian Elimination, we will do the following:

Operate on Row 4: \( R_4 - \frac{1}{2}R_3 \rightarrow R_4 \)

Operate on Row 3: \( R_3 - \frac{2}{7}R_2 \rightarrow R_3 \)

Operate on Row 2: \( R_2 - \frac{7}{5}R_1 \rightarrow R_2 \)

This produces the matrix:

\[A = \begin{bmatrix} 5 & 2 & 7 & 2 \\ 0 & -\frac{4}{5} & -\frac{9}{5} & -\frac{9}{5} \\ 0 & \frac{45}{7} & \frac{5}{7} & \frac{61}{7} \\ 0 & \frac{5}{2} & \frac{3}{2} & -\frac{5}{2} \end{bmatrix}\]

Operate on Row 4: \( R_4 + \frac{50}{16}R_3 \rightarrow R_4 \)

Operate on Row 3: \( R_3 - \frac{450}{56}R_2 \rightarrow R_3 \)

This produces the matrix:

\[A = \begin{bmatrix} 5 & 2 & 7 & 2 \\ 0 & -\frac{4}{5} & -\frac{9}{5} & -\frac{9}{5} \\ 0 & 0 & -\frac{55}{4} & -\frac{23}{4} \\ 0 & 0 & -\frac{33}{8} & -\frac{65}{8} \end{bmatrix}\]

Operate on Row 4: \( R_4 + \frac{3}{10}R_3 \rightarrow R_4 \)

This produces the matrix:

\[A = \begin{bmatrix} 5 & 2 & 7 & 2 \\ 0 & -\frac{4}{5} & -\frac{9}{5} & -\frac{9}{5} \\ 0 & 0 & -\frac{55}{4} & -\frac{23}{4} \\ 0 & 0 & 0 & -\frac{32}{5} \end{bmatrix}\]

Now we have the upper triangular matrix. Note that we did not need to do any row interchanges so we did do not need to change the sign of the determinant we will calculate next. The determinant of an upper triangular matrix is the product of the elements in the diagnol of the matrix.

\[det(A) = (5)(-\frac{4}{5})(-\frac{55}{4})(-\frac{32}{5}) = -352\]

As you can see, this resulted in the same value as we calculated above using the Laplace expansion and by using the Leibniz Formula.

Conclusion

Mathematics serves as the backbone of data science and quantitative finance, empowering professionals with the tools and knowledge required to succeed in these fields.

We covered the following topics:

Properties of Determinants
Laplace expansion
Leibniz Formula
Determinant via Gaussian Elimination

By investing time and effort in mastering the essential topics of math outlined in this post, professionals will be well-prepared to excel in their careers, contribute to advancements in their fields, and make informed decisions based on quantitative analysis.

If you are interested in taking a course on these topics, I recommend: