Cofactors and Cofactor Expansion

Overview

In this article, I will explain the basic concepts of cofactors and cofactor expansion of matrices. These concepts play important roles in linear algebra and machine learning, especially in recommender systems. Through specific examples, I will also demonstrate implementation in Python.

github

  • The Jupyter Notebook file can be found here

google colaboratory

  • To run it on Google Colaboratory, click here

Execution Environment

The OS is macOS. Note that the options may differ from Linux or Unix commands.

!sw_vers

ProductName:		macOS
ProductVersion:		13.5.1
BuildVersion:		22G90

!python -V

Python 3.9.17

To make pandas tables more readable, I will configure CSS settings for HTML tables.

Importing basic libraries and using watermark to check their versions. I will also set the seed for random numbers.

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import random

import scipy
import numpy as np

import matplotlib
import matplotlib.pyplot as plt

seed = 123
random_state = 123

random.seed(seed)
np.random.seed(seed)

from watermark import watermark

print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))

Python implementation: CPython
Python version       : 3.9.17
IPython version      : 8.17.2

matplotlib: 3.8.1
numpy     : 1.25.2
scipy     : 1.11.2

Watermark: 2.4.3

Definition and Properties of Cofactors

A cofactor is a type of determinant associated with elements of a matrix. Specifically, given $a_{ij}$ as the $(i,j)$ element of matrix $\mathbf{A}$, the cofactor $C_{ij}$ is defined as follows:

$$ C_{ij} = (-1)^{i+j} \det(\mathbf{A}_{ij}) $$

Here, $\mathbf{A}_{ij}$ is the submatrix obtained by removing the $i$-th row and $j$-th column from $\mathbf{A}$. This definition leads to the cofactor matrix $\mathbf{C}$, which is a matrix composed of the cofactors of each element of $\mathbf{A}$.

Example

For instance, consider the $3 \times 3$ matrix $\mathbf{A}$ as follows:

$$ \mathbf{A} = \begin{pmatrix} 1 & 2 & 3 \ 0 & 1 & 4 \ 5 & 6 & 0 \end{pmatrix} $$

In this case, the cofactor $C_{11}$ corresponding to the element $a_{11}$ is calculated as follows:

$$ \mathbf{A}_{11} = \begin{pmatrix} 1 & 4 \ 6 & 0 \end{pmatrix} $$

$$ C_{11} = (-1)^{1+1} \det(\mathbf{A}_{11}) = \det(\begin{pmatrix} 1 & 4 \ 6 & 0 \end{pmatrix}) = 1 \cdot 0 - 4 \cdot 6 = -24 $$

Python Implementation Example

import numpy as np

def minor(matrix, i, j):
    minor_matrix = np.delete(matrix, i, axis=0)
    minor_matrix = np.delete(minor_matrix, j, axis=1)
    return minor_matrix

def cofactor(matrix, i, j):
    minor_matrix = minor(matrix, i, j)
    return ((-1) ** (i + j)) * np.linalg.det(minor_matrix)

A = np.array([[1, 2, 3],
              [0, 1, 4],
              [5, 6, 0]])

C11 = cofactor(A, 0, 0)
print("C11 =", round(C11, 2))

C11 = -24.0

Definition and Properties of Cofactor Expansion

Cofactor expansion is a method of calculating the determinant of a matrix along its rows or columns. The determinant $\det(\mathbf{A})$ of matrix $\mathbf{A}$ is expanded using cofactors as follows:

$$ \det(\mathbf{A}) = \sum_{j=1}^{n} a_{ij} C_{ij} $$

Here, $i$ is the index of the fixed row, and $j$ is the index of each column in that row. This formula holds for any row $i$.

Example

Using the matrix $\mathbf{A}$ again, the determinant is calculated through cofactor expansion along the first row:

$$ \det(\mathbf{A}) = a_{11}C_{11} + a_{12}C_{12} + a_{13}C_{13} $$

Each cofactor is calculated as follows:

$$ C_{11} = -24, \quad C_{12} = (-1)^{1+2} \det(\begin{pmatrix} 0 & 4 \ 5 & 0 \end{pmatrix}) = 20, \quad C_{13} = (-1)^{1+3} \det(\begin{pmatrix} 0 & 1 \ 5 & 6 \end{pmatrix}) = -5 $$

Therefore,

$$ \det(\mathbf{A}) = 1 \cdot (-24) + 2 \cdot 20 + 3 \cdot (-5) = -24 + 40 - 15 = 1 $$

Python Implementation Example

def determinant(matrix):
    n = len(matrix)
    if n == 1:
        return matrix[0, 0]
    elif n == 2:
        return matrix[0, 0] * matrix[1, 1] - matrix[0, 1] * matrix[1, 0]
    else:
        det = 0
        for j in range(n):
            det += matrix[0, j] * cofactor(matrix, 0, j)
        return det

det_A = determinant(A)
print("det(A) =", round(det_A, 2))

det(A) = 1.0

Applications of Cofactors and Cofactor Expansion

Cofactors and cofactor expansion are also important for calculating the inverse of a matrix. Specifically, the inverse $\mathbf{A}^{-1}$ of matrix $\mathbf{A}$ is expressed using the cofactor matrix $\mathbf{C}$ and the determinant $\det(\mathbf{A})$ as follows:

$$ \mathbf{A}^{-1} = \frac{1}{\det(\mathbf{A})} \mathbf{C}^T $$

This relationship is useful for analyzing the properties of matrices. It is particularly important in linear algebra applications in machine learning, such as constructing models for recommender systems.

Example

To find the inverse of matrix $\mathbf{A}$, we use the cofactor matrix and the determinant.

Python Implementation Example

def cofactor_matrix(matrix):
    n = len(matrix)
    C = np.zeros(matrix.shape)
    for i in range(n):
        for j in range(n):
            C[i, j] = cofactor(matrix, i, j)
    return C

C = cofactor_matrix(A)
det_A = determinant(A)
A_inv = (1 / det_A) * C.T
print("A^(-1) = \n", A_inv.round(2))

A^(-1) =
 [[-24.  18.   5.]
 [ 20. -15.  -4.]
 [ -5.   4.   1.]]

Conclusion

In this article, I explained the definitions, properties, and specific applications of cofactors and cofactor expansion. These concepts are powerful tools for analyzing the properties of matrices and are particularly important in the field of machine learning.

References