Monthly Archives: September 2013

Matrix Multiplication, A Novella: Chapter 3

There’s too many kids in the world!

See, you set up a great system going on for tracking a kid’s actions and determining how much coal or candy they get. It’s easy, and it’s foolproof. Why, it’s so good that Santa cut the budget for North Pole Behavior Psychology Lab, because he thinks you’re capable enough to do it without money.

Now, this is a problem. More and more kids are believing in Santa every day. And the computers you’ve got running the matrix multiplications to determine each kid’s presents? They’re slow. Relics from the 80s.

In fact, you just crossed a scary threshold — given the number of children Santa needs to deliver to next Christmas, you don’t have enough computing power and time to determine presents for every kid by Christmas Eve. Christmas can’t happen.

There’s three ways you can fix this problem:

  • Reduce the number of kids to compute presents for
  • Increase the number of computers to run math
  • Decrease the amount of time it takes a computer to compute presents

Unfortunately, thanks to budget cuts and your lack of desire to kill children, you can’t implement the first two solutions. Sounds like you have to make optimizations if you want to save Christmas again.

So let’s re-examine our pipeline. Identify anything we can simplify.

mat-3-1

Alright! So we go from knowing the actions per child (matrix A), to knowing the points per child (A*B), to knowing the presents per child (A*B*C).

Huh. So, when we look at our system this way… why do we even bother with matrix B, the points per action matrix? I mean, we cancel out both terms belonging to B when we multiply A*B*C — we don’t ultimately care about points or actions. Can we fold B into C? Create one presents per action matrix, and discard the idea of “points” entirely?

mat-3-2

Ooooooh. That’s a good idea.

Yes! That is totally possible! In fact, this is one of the most awesome and convenient things about matrix multiplication. All you need to do to combine B and C into a presents per action matrix is… multiply them.

mat-3-3

And if we multiply our actions per child matrix with this new presents per action matrix…

mat-3-4

It’s the same result as we got before! That’s our exact presents-per-child matrix from previous chapter, but we only did one matrix multiplication to get it!

This is called the associative property of multiplication — previously, we did (A*B)*C, and now we’re doing A*(B*C), and we get the same results. That is, matrix B can associate with A or C. If B and C are both constant matrices, we can just multiply them together into a new matrix D=B*C and use it everywhere.

So with one quick calculation of D=B*C, you just halved the amount of processing time your computers need to calculate presents per kid! You are really good at saving Christmas, dude.

Matrix Multiplication, A Novella: Chapter 2

Well, your days as an event planner are over. There was a lot of blood at Bacchanal S, and the police are looking for you. So you ditch town, fly to the North Pole, and find a job in Santa’s Behavior Psychology lab.

“Naughty” and “Nice” aren’t simple concepts, and Santa needs experts to determine which child is which. The lab tracks each child’s actions, and each action is associated with a naughtiness and niceness “score”… hey, does this look familiar to you?

matrices-1

Good lord, this is just like the spreadsheets you used as an event planner!

matrices-2

Okay, you just crushed some naughty/nice scores — but there’s more. There’s another spreadsheet that determines what Christmas presents a child gets for a given amount of naughtiness or niceness:

matrices-3

You can handle this! You have to take that naughtiness/niceness-score-per-child matrix you just generated, and multiply it by this matrix…

matrices-4

Wait. That can’t be right. Your math is correct, but those numbers are way too huge. There must be a logic error somewhere. Shoot, how does this matrix multiplication thing work, again?

  • Your first matrix is a spreadsheet representing amount of Y per X, for some set of items X and Y. For instance:
    • “Number of [tables/chairs/balloons] I need to rent per event, for [my 5 upcoming events]” (Y = items to rent, X = events to rent items for)
    • “Number of [punches/hugs/kisses] performed per child, for [every child Santa tracks]” (Y = actions children perform, X = children whose actions Santa tracks)
  • Your second matrix is a spreadsheet representing the amount of Z per Y. For instance:
    • “Price charged by [Vendor1/Vendor2/Vendor3], for each [table/chair/balloon]” (Z = vendor prices, Y = items to rent)
    • “How many [naughtiness/niceness points] you get, for each [punch/hug/kiss]” (Z = personality points, Y = actions children perform)
  • By multiplying the two matrices, you go from amount of Y per X to amount of Z per X
    • “I know how many [tables/chairs/balloons] each event requires, and I know how much [Vendor 1/Vendor 2/Vendor 3] charges to rent an individual [table/chair/balloon], so how much would it cost to use [Vendor 1/Vendor 2/Vendor 3] for each event?”
    • “I know how many [punches/hugs/kisses] each child performed, and I know how [naughty/nice] it is to perform an individual [punch/hug/kiss], so how [naughty/nice] has each child been?”

Now, let’s see what went wrong when you tried going from naughtiness/niceness-score-per-child to presents-per-child:

matrices-5

Look at that! These units are all wrong. So what are the right units?

Well, we know that matrix multiplication means “amount of Y per X * amount of Z per Y = Amount of Z per X“. We have the matrix [naughtiness/niceness score] per [each child Santa tracks], and we want to end up with the matrix [amount of coal/candy] per [each child Santa tracks]. So…

  • X = [each child Santa tracks]
  • Y = [naughtiness/niceness score]
  • Z = [amount of coal/candy]

Therefore, we want our second matrix, amount of Z per Y, to be [amount of coal/candy] per [naughtiness/niceness score]! Then,

matrices-6-1

So we want the amount of coal per naughtiness point, not the amount of naughtiness points per coal — we inverted the units, is all. In order to invert our matrix back to the correct position, we have to flip the rows and columns (this is called a transpose) and invert the numbers to match. And now we get:

matrices-6

Nice! You just solved what presents each kid is getting! You LITERALLY saved Christmas.

Matrix Multiplication, A Novella: Chapter 1

So you got hired as an event planner. Congratulations on your new job!

You’re a clever event planner, and therefore you know that your events need tables for people to eat at. You rent tables per-event from your favorite party supply place, Vendor 1. Here’s the spreadsheet you use to track costs:
matrices-1

(I hope you didn’t just ignore that spreadsheet. If your eyes glazed over, go back and read it. It’s simple.)

Everything looks great! However, two nights before Gala A, you wake up in a cold sweat: you forgot chairs. You figure out how many chairs each event needs, call Vendor 1 to get a price, and re-tool your spreadsheet. Nice save! Now your spreadsheet looks like this (click for bigger, and don’t ignore this one either):
matrices-2

It’s one night before Gala A, and your phone is ringing at 2AM. What could it be? It’s Vendor 1’s archrival, Vendor 2! She wants to scoop her old boss, and she has a deal for you: chairs cost $7 each, but tables are only $8 each. You can’t mix and match tables from Vendor 1 with chairs from Vendor 2 — ever since Vendor 2 keyed Vendor 1’s car, they won’t work together. (Click for bigger)
matrices-3

Looks like Vendor 2 is cheaper for Gala A, Soiree B, and Reception C. You should keep Vendor 1 for Banquet D, though!

Man, you’re good at this event planning stuff. Two months pass, and you’re an old pro. This is what your spreadsheet looks like now:
matrices-4

More events! vendors! More items to rent! This is intense. Frankly, now that you’re a big-shot, these labels are looking like overhead. So you clean it up:
matrices-5

These are the same spreadsheets, just with all the non-math information chopped out. You decide to call these math-only spreadsheets matrices. To keep things from getting confusing, you implement some rules:

  • Matrix A holds item-to-rent details per event. A row represents a single event, and a column represents the number of a single item-type to rent for each event.
  • Matrix B holds vendor prices per item-to-rent. A row represents a single item-type, and a column represents a vendor’s prices for each item.
  • If we want to add a new item-type (for instance, lamps) then we need to know how much each vendor charges per-lamp. This means that the number of columns in A (representing item-types) must match the number of rows in B (since they also represent item-types).

Now, you’ve removed everything but the sweet, sweet math. And once you do that, something surprisingly simple shows up:
matrices-6

That is… (click for bigger)
matrices-7

And you just invented matrix multiplication. Congratulations!