Suppose we have a business operating in six cities around the Pacific Rim: San Diego, San Francisco, Tokyo, Shanghai, Manila, and Honolulu. We are interested in counting the number of ways we can travel from one city to another with at most n stopovers. We look up all the direct flights and put them in a table: Destination San Diego San Francisco San Francisco San Diego, Tokyo, Shanghai, Manila, Honolulu Tokyo San Francisco, Shanghai, Manila Shanghai San Diego, San Francisco, Tokyo, Manila Manila Tokyo, Shanghai, Honolulu Honolulu San Francisco, Shanghai, Manila Let's say we want to get from San Diego to Manila with at most three stops along the way. For example the trip going from San Diego through San Francisco, then Honolulu, then Shanghai, then Manila is a trip with exactly three stops Exercise 3.2 List all possible ways to get from San Diego to Manila with exactly three stops Doing that last exercise by hand is a pain because there are so many cases to check and this is a relatively simple example. If we want to do this efficiently, linear algebra is the perfect tool, We'll start by encoding the data from our table into what's called an adjacency matrix The first step is to number our cities in the order they are listed: San Diego is 1, San Francisco is 2, and so on. We now determine the entries of our adjacency matrix, which we will call A, using the following rule: if there is a flight from city i to city j, then the entry A, is set to 1. Otherwise, we set that entry to 0. We will also set all of the diagonal entries to 0, since you can't take a flight from a city to itself. This procedure gives us the following matrix A 0100 0 0 0 101 1 0 0 01 1 0 1 0101 1 0 What's neat about this is that the powers of A2ae lie, the entry of A in the third row and sixth column). We compute this as Let's look at the terms here: A As is 1 if and only if both Au and As are 1. This means we get a 1 for the kth term if and only if we can fly from Tokyo (city 3) to city k and from city k to Honolulu (city 6) Thus, (A33s counts the number of ways to fly from Tokyo to reasoning shows that the number of ways of flying from city i to city j with exactly n stops is just Honolulu with exactly one stop. Similar Exercise 3.3 a. Enter the above adjacency matrix A into MATLAB. By looking at the entry of A in the first row and the fifth column, find the number of ways to get from San Diego to Manila with exactly three stops. Does your answer here agree with your explicit count in the previous exercise? If not, find the missing trips, Include your input and output in your document b. Now use MATLAB find the number of ways to get from San Francisco to Tokyo with at most four stops. (This is not the same as finding the number of ways with exactly four stops) Include all of your commands and output in your write-up Note 3.1 As you may have realized, the method we've just used counts silly trips like San Francisco- Shanghai-San Francisco-Shanghai as a trip with two stops.