Sharpening Math AND Programming Skills at the Same Time 🤓

Motivation

Knowing how to program opens you up to some really interesting problems. If you’re like me and came to software engineering from another career, looking back on problems from your previous discipline take on a new light. Solving problems with physical implications is a terrific motivator for sharpening your coding and algorithm skills.

What We’re Covering

Matrix determinants are a crucial first step in many linear algebra applications. Determinants are used in the Cross Product calculation of force and lever vectors to determine stresses in structures, and useful in determining the eigenvalues and eigenvectors of a matrix. This is a critical first step in understanding Primary Component Analysis and Dimensionality Reduction in machine learning as well.

I’ll show a Go implementation as part of a math library I’m building for some ML and computation projects I’m working on. Go offers strong performance benefits and type safety without all the boilerplate of Java. Go also presents an interesting challenge layer to this problem because of the way Go handles slices. You could probably knock this implementation out in less lines of Python or whatever your favorite language is, but the solution concept will hold up no matter how you code it.

Determinants

The determinant is a property of a square matrix that describes transformation and scaling of a matrix. Geometrically, the absolute value of the determinant is the n-dimensional area or volume of the n vectors involved in a nxn matrix.

In machine learning, we can solve for the eigenvalues of a matrix by setting the determinant of A-λ I = 0 and solving for λ where A is a matrix and λI is a diagonal matrix of λs. This gives us a way to figure the eigenvectors which happen to be the principle components in datasets with a large number of features.

the absolute value of the determinant is the n-dimensional area / volume of the n vectors involved in a nxn matrix

Calculation

Let’s notate our matrices alphabetically like so and list our rules and base cases.

  • The determinant can only be performed on a square matrix
  • The determinant of a 1x1 matrix is simply the one element
  • The determinant of a 2x2 matrix is the formula a*d + b*c
  • For a 3x3 matrix we introduce this idea of a minor matrix to be used in the calculation
This looks like a job for recursion! [source]
  • The pattern for concatenating the result of each sub problem is +-+- (i.e. if i % 2 == 0 then we add otherwise we subtract)

For any matrix with more than 3 dimensions, the determinant is this equation that contains a value from the ith row multiplied by the determinant of a minor matrix containing all elements not in ith row or ith column of the matrix. In the above example, we already know how to get the determinants of the 2x2 matrices because of our rule from above for 2x2 determinants

The Code

func Determinant(mat [][]float64) (float64, error) { // Base cases and rules if len(mat) != len(mat[0]) {
return 0.0, errors.New("determinant can only be performed on square matrices")
}
if len(mat) == 1 {
return (mat[0][0]), nil
}
if len(mat) == 2 {
return (mat[0][0] * mat[1][1]) - (mat[0][1] * mat[1][0]), nil
}
s := 0.0 // accumulator for i := 0; i < len(mat[0]); i++ {

sm := subMat(mat[1:][:], i) // peel off top row before passing
z, err := Det(sm) // get determinant of sub-matrix

if err == nil {
if i%2 != 0 {
s -= mat[0][i] * z
} else {
s += mat[0][i] * z
}
}
}
return s, nil
}

To start with a problem like this, let’s define our function signature and look at the base cases and rules. The function should take a slice of slices. I went with float64so we don’t lose any precision in the calculation but you could also get away with int or float32. It returns one number because the determinant is a scalar value. In 2d it represents the area between 2 vectors after a shift, and in 3d its the volume shared by 3 vectors.

Next set up an accumulator s := 0to accumulate our results concatenation and enumerate through each column. Create a method to figure the minor matrix out given all the rows except the first row, we’ll get to that in a sec. Finally code up the rule that either adds or subtracts based on the column we’re in.

func subMat(mat [][]float64, p int) [][]float64 {
stacks := make([]stack, len(mat))
for n := range mat {
stacks[n] = stack{}
for j := range mat[n] {
if j != p {
stacks[n].push(mat[n][j])
}
}
}
out := make([][]float64, len(mat))
for k := range stacks {
out[k] = stacks[k].ToSlice()
}
return out
}

Determining a submatrix is done by taking the part of the original matrix without the first row and iterating over all rows and columns. This method also takes a value p to denote our “pivot” column. This is the column denoted by the white squares in our wikipedia figure. We want to build a new matrix consisting of every value in our matrix that is not in the first row (hence we dont even pass it in with this function) and not in the p column. We’ll go over each row, for each item in the row, add it to our new matrix if the column value is not p.

Borrowed from Wikipedia

To do this, we needed a data structure that would allow us to push values in. That way when we get to our middle column, we don’t have to concern ourselves with whether or not we’re in the middle and how many values we need to count. All we want to do is push the current value into the structure if it meets the criteria. Lets roll a stack!

type stack []float64func (s *stack) isEmpty() bool {
return len(*s) == 0
}
func (s *stack) push(n float64) {
*s = append(*s, n)
}
func (s *stack) pop() (float64, bool) {
if s.isEmpty() {
return 0, false
}
i := len(*s) - 1
n := (*s)[i]
*s = (*s)[:i]
return n, true
}
func (s *stack) ToSlice() []float64 {
return *s
}

Go doesn’t really have a stack interface like Python so we had to whip this up on the side. You can add it to wherever your determinant code is if you’re doing this all in one main.go file. What this is, is we define a new type called stack. That lets us do things like stack{} which instantiates a new []float64 array but we get to call it a stack. Then we add some methods. Those signatures will look weird if you’re coming from Java or JavaScript but the way to read them is

function (acts on type of pointer) pop() (return this type of item) {…}

or

function (acts on this type of pointer) push(this type of thing) {…}

Basically we’re just making an array but we’re making it feel like a stack which is going to help us later down the line and it makes code easier to understand conceptually. You may note this stack isn’t exactly how you’d do this in Go with capital letters for functions and types. I haven’t exported this anywhere and you only really need to capitalize names for things you want to export from another file. If you would like to do that, create a file called stack.go and add the above code, remembering to capitalize all the function names and Stack .

Because in our subMat function we handle appending values using a slice of stack objects, we need to convert that back to a [][]float64 so we can return it. Thats the reason we have the last loop calling a method that just casts the stack as the []float64 array we originally masked so it can honor the return value in the signature here func subMat(mat [][]float64, p int) [][]float64 {...}

Lets Fire it Up

Assuming you are doing this all in a big main.go file, stick this in the main function

func main() {
m1 := [][]float64{
{3.0, 8.0},
{4.0, 6.0},
}
m2 := [][]float64{
{6.0, 1.0, 1.0},
{4.0, -2.0, 5.0},
{2.0, 8.0, 7.0},
}
m3 := [][]float64{
{1.0, 3.0, 1.0, 2.0},
{5.0, 8.0, 5.0, 3.0},
{0.0, 4.0, 0.0, 0.0},
{2.0, 3.0, 2.0, 8.0},
}
d1, err := Det(m1)
if err != nil {
fmt.Println("error", err)
} else {
fmt.Println("The determinant of", m1, "is", d1)
}
d2, err := Det(m2)
if err != nil {
fmt.Println("error", err)
} else {
fmt.Println("The determinant of", m2, "is", d2)
}
d3, err := Det(m3)
if err != nil {
fmt.Println("error", err)
} else {
fmt.Println("The determinant of", m3, "is", d3)
}
}

This is our driver code. In Go there are no exceptions, so if a method can return an error, its usually returned as a second return value (Go does multiple return values too!) In this case, either everything is fine and error will be nil or something happened and error is not nil. If error exists, we’re expected to handle it. The compiler will yell at you if you don’t use this err variable.

In your console, navigate to your gopath and in the project directory type go run . and you should see

The determinant of [[3 8] [4 6]] is -14
The determinant of [[6 1 1] [4 -2 5] [2 8 7]] is -306
The determinant of [[1 3 1 2] [5 8 5 3] [0 4 0 0] [2 3 2 8]] is 0

Success!

If everything goes to plan, and you’ve installed Go correctly and were able to get it to run then you should now have a piece of code that is a solid foundation to solving problems in any dimensional space. You can use this as a building block for building calculators that determine matrix properties like cross products, and eigenvectors, or for machine learning and primary component analysis.

I decided to take this on as a personal challenge more than anything and if you’d like to see more numerical methods I’ve been collecting in Go, check out the project here. If you spot something wrong or want to talk about the project in depth hit me up here or here or create an issue on the repo.

Software Engineer | Product Leader