Once upon a time, in the Kingdom of Verona, there lived two star-crossed lovers Romeo and Juliet. More than anything else, the lovers wanted to be together. 

The only problem was that their families shared centuries-old rivalry and their parents didn't want them to be together and forbade them from seeing each other in the hopes that the separation would eventually extinguish the flame of emotion between them. 

This however did not happen, as the distance made their feelings for each other even stronger, leading both lovers long to see each other.

Stay away from my son!!!

Don't come near her!

Psst! Romeo!

Beware of the guards!!!!

Romeo was out for a walk when her heard Juliet's nurse calling his name, confused he went to her.

She handed him a weird-looking table, with numbers calling it a map and a note. Before he can ask questions, she turns and leaves, leaving  Romeo wondering what lies before his eyes. 

Romeo reads the note:

"Juliet wishes for you to visit her in her room tonight. You must traverse through the Capulet's castle. 

And lastly, whatever you do, you must not pass through more than 3 hallways before arriving to Juliet's room, or an ill fate shall befall you. Beware and goodluck."

Romeo is still standing there and wondering what to do with the map when he sees Mercutio. "Hey Mercutio is smart, he'll know what to do!", Romeo thinks to himself and hurries to catch up to him.

After explaining the weird encounter with Juliet's nurse, Romeo shows Mercutio the apparent "map".

I know what this is, it's a matrix!

Really? What's that?

"A matrix is like a table with numbers, called the elements of the matrix. They are arranged in rows and columns. They are indicated by square brackets! Like this 2 by 3 matrix with 2 rows and 3 columns.

What you have is an adjacency matrix, a square matrix used to represent a graph with vertices and edges. The vertices are the rooms of the castle and the edges are the hallways. The elements in the matrix are 0’s and 1’s, and tell you whether or not the pairs of vertices have an edge connecting them.."

Okay, I think I understand, but that doesn't help me with the one that Juliet's nurse gave me

"Here's a simple demonstration; 

We can start off with a map with three rooms: A, B, and C. We can create a 3 by 3 matrix with the rows and columns labelled A, B and C. Since a room cannot connect to itself, there will be a 0 in row A and column A. We can see there is a path connecting from rooms A to B so there will be a 1 in Row A and Column B. There is no path connecting rooms A and C so Row A and Column C will have a 0."

"We can repeat this process for the remaining rows. For row B, we know rooms A and B connect so row B, column A will have a 1. Room B does not connect to itself so it will get a 0 in row B, column B. Room B does connect to Room C so row B, column C will get a 1. For row C, we know that room C connects to only room B so row C and column B will get a 1 and the remaining spaces will get a 0."

So now you have an adjacency matrix!

Ah, I get it now. Thanks Mercutio!

Hmm… looking at the map Juliet’s nurse gave me. I can see that the gates connect to the ballroom, the kitchen and Capulet’s room since there is a 1 in Row A, columns B, E and I.

The kitchen connects to the gates, the dining room, the ballroom, the dungeon and Capulet’s room.

No problem! Now we can create the map from the adjacency matrix given by Juliet’s Nurse.

And then the Dining room connects to the kitchen, the watchtower, the ballroom and Juliet’s room. Now I can do this for the remaining rooms and I will get the map. I’ve now got a map of Capulet’s Castle! But I still have to find a way to Juliet’s room without passing more than three hallways...

What is it?

Don't worry! I have the trick right up my sleeve!

M - "We can use multiplication of an adjacency matrix by itself to find a way to Juliet’s room without passing more than three hallways"

R - "Multiply an adjacency matrix? I have no idea how to do that and it seems so hard."

M - "It is much simpler than it looks. Let’s take a look at a simple example of multiplying 2 by 2 matrices. Now we have to multiply the first row of the matrix A and the first column of matrix B."

"To get the next value in the first row of our new matrix, we have to multiply the first row of matrix A and second column of matrix B, getting us the matrix on the right.  Now we can move on to the second row of matrix A to get the values of the second row of a new matrix."

 Using the same techniques, our new matrix will look like this! See how easy it is, Romeo!

Yes, it looked so difficult at first. So now can we find a way without passing through three hallways using matrix multiplication?