Simple Yet Complex Algorithm Example

Introduction
Problem
Quick Explanation of Matrix Multiplication
Sample Code (Javascript)
Conclusion

Introduction

We've all had our own individual learning experiences in programming, as well as algorithm related logic. One tricky aspect can be mathematical concepts, especially because of the varied backgrounds of aspiring software developers.

I just wanted to introduce a problem I recently encountered that has been tripping up many of my colleagues. I will try to explain the math behind it and then my simple (but not optimal) approach to solving it in Javascript.

Problem

Write a function that multiplies two matrices (2D arrays) in Javascript.
Check out the Wikipedia article on matrix multiplication.
Example:

function matrixProduct(matrix1, matrix2) {
  // Your code here!
}

// Testing example 
// Expected: 
// [ 5, 4 ]
// [11, 8 ]
console.table(
  matrixProduct(
    [
      [1, 2],
      [3, 2]
    ],
    [
      [3, 2],
      [1, 1]
    ]
  )
)

(BTW I love console.table)

The Wikipedia Article Is Too Confusing

That's okay. I will try to just explain the mechanics of matrix multiplication. If one knows the steps, they can perform it correctly even if they don't understand the mathematical background. I would refer to Wikipedia and other web resources for more background on matrices and linear algebra.

Dot Product

I just want to quickly introduce the operation of dot product. It's a form of vector multiplication which combines two vectors of the same size. Vectors in math are very similar to arrays in programming so I will use the square brackets to indicate my vectors.

 [a, b, c] * [d, e, f] = ad + be + cf

Two things to remember: the dot product results in a scalar, or just one number (instead of a vector or matrix). The other thing is that the two vectors must be the same length or the operation doesn't make sense.

We could also rewrite the second vector to be vertical:

 [a, b, c] * [d  = ad + be + cf 
              e
              f]

[a, b, c] is a bit different from [d, e, f] in that even though both are length 3, [a, b, c] is 1x3 (one row, three columns) and [d, e, f] is 3x1 (three rows and one column).

This distinction between rows (number of horizontal lines of numbers) and columns (number of vertical lines of numbers) is important to distinguish for matrices. This is because matrix multiplication is not commutative (which means order matters; AxB is not always the same as BxA).

Extending Dot Product to Matrix Multiplication

 [a, b, c] * [d  =  ad + be + cf 
              e
              f]

So as shown in the above example, the dot product of two same length vectors gives you a scalar. What if you wanted to do this multiple times? Let's add a second vertical vector, [g, h, i].

 [a, b, c] * [ d, g   =   [ ad + be + cf  ,  ag + bh + ci ]
               e, h
               f, i ]

We can just think of this as doing the dot product operation twice: taking the single vector on the left, and calculating the dot product of it and each vertical vector on the right. We just store the two solutions as a vector and each scalar's coordinate in the vector tells us which operation we did.

For example, we still have (ad + be + cf) from our first operation, in position 1. And our new dot product, (ag + bh + ci) is simply in position 2.

Basic Operation of Matrix Multiplication

We can extend this position idea to both the number of rows of the first matrix, and the number of columns to the second matrix (which [g, h, i] showed).

 [a, b, c] * [ d, g   =   [ ad + be + cf  ,  ag + bh + ci ]
 [1, 2, 3]     e, h       [ d + 2e + 3f   ,   g + 2h + 3i ]
               f, i ]

In this next example we simply add a new row to our left side vector, making it a 2x3 matrix. It is very similar to adding the column, [g, h, i], except the idea applies to rows instead of columns.

We notice that the answer has also added a row. As long as our vectors have length 3, the dot product operations won't have any mismatches. But having 2 row vectors multiplied by 2 column vectors gives us an answer that is 2x2. These values of 2, the number of rows of first matrix and the number of columns of second matrix, can be extended to any amount, as long as the columns of the first matrix match the rows of the second (so that dot products can be calculated).

Also, knowing the dimensions of the answer matrix, we can calculate any position's scalar value, for example, [X, Y], because we can simply dot product the Xth row of the left matrix and the Yth column of the right matrix.

How to code this? (Sample Javascript Code)

After the long winded explanation of the calculation, how do we actually code it? Firstly, I would recommend trying to correctly do these calculations on paper. Follow examples found on your search engine if you don't have a tool to check your work.

Secondly, keeping track of the rows and columns is the key to calculating the correct scalar value at position [X,Y] on the solution matrix. For the simple brute force solution, I expect to have two nested for loops to locate each position on the solution matrix, and then a third nested for loop that iterates through the two same-length vectors to calculate the dot product. This post won't discuss optimizations, but merely promotes basic understanding of the problem.

Try following my code's comments to see how I implemented this. There are better ways, such as if you could transpose, or rotate, the second matrix, but this is the most basic form of calculating each value of a matrix product using its positional coordinates.

function matrixProduct(matrix1, matrix2) {
  // Assumes matrix1 and matrix 2 can be multiplied
  // but one can check if the dimensions match here 

  // We know that for matrices [m x k] X [k x n] 
  // that the result is [m x n] and the k's are 
  // the dot product matching lengths
  let result = [] // if for loops are correct then the dims will be correct 

  // For intuition, m is the number of rows of matrix1
  // n is the number of columns of matrix2
  // And in our 2D arrays, number of rows is matrix.length (outer array)
  // number of columns is matrix[i].length (inner array or nested array)

  // For consistency, I will call X the index of row of matrix 1
  // and Y the index of column of matrix 2 
  for (let X = 0; X < matrix1.length; X++) {

    let newRow = [] // new row to add to result, and to add scalars to

    for (let Y = 0; Y < matrix2[0].length; Y++) {
      // Once we've "arrived" at position X, Y
      // we want to find the dot product of row X of matrix 1
      // and column Y of matrix 2 (which are the same length) 

      let newDotProd = 0 // add together products to get dot product

      for (let i = 0; i < matrix1[X].length; i++) {
        // note the switched positions of the i index
        newDotProd += matrix1[X][i] * matrix2[i][Y]

      }

      newRow.push(newDotProd) // should have pushed n times
    }

    result.push(newRow) // should have pushed m times
  }

  return result
} // end of matrixProduct()

Conclusion

I just wanted to introduce and explain the mechanics behind matrix multiplication, without getting into the much wider world of mathematics such as linear algebra and other uses for matrices. I hope this helps some get over the hurdle of simply getting stuck on the operation itself.