What is Matrix Multiplication?
Tags: matrix, multiplication
Published: 2020-05-05 00:42:29

# Simple Yet Complex Algorithm Example 

[Introduction](#ch1)
[Problem](#ch2)
[Quick Explanation of Matrix Multiplication](#ch3)
[Sample Code (Javascript)](#ch4)
[Conclusion](#ch5)

<a name="ch1">
## 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.

<a name="ch2">
## Problem 

Write a function that multiplies two matrices (2D arrays) in Javascript. 
Check out the [Wikipedia article on matrix multiplication](https://en.wikipedia.org/wiki/Matrix_multiplication).
Example: 
```js
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) 

<a name="ch3">
## 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.

<a name="ch4">
## 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.

```js
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()

```

<a name="ch5"> 
## 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.