# Matrix Algebra

We've seen how to use MATLAB to row-reduce matrices and solve linear systems; now we're going to use it to perform other basic matrix operations. In a sense, matrices are a bit like real numbers: we can add, subtract, and multiply them, provided they have appropriate dimensions. Some square matrices also have a multiplicative inverse. But there are a handful of striking differences. For example, when multiplying matrices, it is not generally true that AB = BA, and A2 may be zero even when A is not the zero matrix. Keep these things in mind as you work through this lab.

## Basic Matrix Operations

You've learned in class by now that we can add two matrices of the same dimensions by just adding the corresponding entries. The operator MATLAB uses for matrix addition is the simple plus sign `+`, the same one used for regular addition of numbers. If we enter the matrices

```>> `A = [1 2 3 4; 5 6 7 8]`
>> `B = [8 7 6 5; 4 3 2 1]````

into MATLAB, we can then add them by typing

```>> `A+B`

ans =
9    9    9    9
9    9    9    9```

Matrix multiplication works as you would expect—you simply need the number of columns of the first matrix to be equal to the number of rows of the second one. For example, we could enter the following matrices into MATLAB:

```>> `C = [1 2; 1 0]`
>> `D = [0 1; 1 1]````

Now we can multiply them:

```>> `C*D`

ans =
2    3
0    1```

We can also exponentiate matrices (as in `A^3`). Lastly, we can ask MATLAB to compute the tranpose of a matrix with an apostrophe (`'`):

```>> `C'`

ans =
1    1
2    0```

## Matrix Inversion

One of the key differences between matrix multiplication and multiplication of real numbers is in the existence of multiplicative inverses. If x is a nonzero real number, then there's always another number (namely 1x) that you can multiply by x to get the multiplicative identity (1). With matrices, we'd like to do the same thing: given a matrix A, we want to find another matrix B such that AB = BA = I, where I is an identity matrix.

Just by looking at the condition AB = BA = I, we can see that A and its inverse B have to be square matrices of the same dimension. Unfortunately, even square nonzero matrices can fail to have an inverse. If an inverse exists, we say that A is invertible (or sometimes non-singular); otherwise, we say it is non-invertible (singular).

The MATLAB command `inv` finds the inverse of a matrix if it exists.  1. Try using the `inv` command to find the inverse of the matrix Notice the strange output. Include your command and the output in your write-up.

2. Now enter the following matrix A into MATLAB:

>> `A = [4 9; 5 11]`

Define B to be its inverse in MATLAB. Then run the commands

```>> `A*B`
>> `B*A````

to check that it satisfies the definition of inverse. Include your commands and their output in your write-up. (Note that MATLAB may give you entries like -0.0000 in your results. This still counts as 0 for our purposes.)

3. Enter the following column vector x:

>> `x = [5; 10]`

Use the following command to multiply A by x:

>> `y = A*x`

4. Without entering anything into MATLAB, what do you think you'll get if you multiply B by y? Explain your answer.

## Logistics: Route Planning

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. List all possible ways to get from San Diego to Manila with exactly three stops (see the explanations above) and no city occurring twice.

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 Aij 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: What's neat about this is that the powers of A have useful information too. For example, take the entry (A2)36 (i.e., the entry of A2 in the third row and sixth column). We compute this as

(A2)36 = A31A16 + A32A26 + A33A36 + A34A46 + A35A56 + A36A66

Let's look at the terms here: A3kAk6 is 1 if and only if both A3k and Ak6 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, (A2)36 counts the number of ways to fly from Tokyo to Honolulu with exactly one stop. Similar reasoning shows that the number of ways of flying from city i to city j with exactly n stops is just (An+1)ij .  1. Enter the above adjacency matrix A into MATLAB. By looking at the entry of A4 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 and include them here. Include your input and output in your document. [Note that a trip with some city occuring twice is still a valid trip even though few people would do that in real life.]
2. 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.

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. User beware!

## Political Science: Electoral Trends

We've already seen how linear algebra can be used to evaluate simple social networks. Now we're going to look at another kind of sociological situation, where we'll try to use matrices to model future population dynamics.

In California, when you register to vote, you declare a party affiliation. Suppose we have just four political parties: Democrats, Republicans, Independents, and Libertarians. Party registration data is public, so we can track what fraction of the voters in each party switch to a different party from one election to the next. Let's say we look up Democratic Party registration data and discover the following: 81% of Democrats remain Democrats, 9% become Republicans, 6% re-register as Independents, and 4% become Libertarians. We can do the same kind of calculation for the other three parties and then organize our data into a table:

Democrats Republicans Independents Libertarians
Democrats 0.81 0.08 0.16 0.10
Republicans 0.09 0.84 0.05 0.08
Independents 0.06 0.04 0.74 0.04
Libertarians 0.04 0.04 0.05 0.78

In this table, we've put our results in the columns, so the numbers reflect the proportion of voters in that column's political party who switch to the party listed to the left. For example, the entry in the "Republicans" row and the "Independents" column tells us that 5% of Independents become Republicans each electoral cycle. We're going to assume that these numbers do not change from one election to the next—not a very realistic assumption, but good enough for our simple model.

Naturally, we want to use this data to predict the outcomes of future elections and the long-term composition of the electorate. Think of the table above as a matrix, which we will call P. Let D0, R0, I0, and L0 denote the current shares of the electorate held by Democrats, Republicans, Independents, and Libertarians, respectively. In the next election, these numbers will change according to P, as follows:

D1 = 0.81 D0 + 0.08 R0 + 0.16 I0 + 0.10 L0
R1 = 0.09 D0 + 0.84 R0 + 0.05 I0 + 0.08 L0
I1 = 0.06 D0 + 0.04 R0 + 0.74 I0 + 0.04 L0
L1 = 0.04 D0 + 0.04 R0 + 0.05 I0 + 0.78 L0

Let xn be the vector (Dn, Rn, In, Ln)T. This vector represents the party distribution after n electoral cycles; the first entry is the portion who are Democrats, the second the portion who are Republicans, and so on. The equations we just wrote out above show us that x1 = Px0. In general, xn = Pnx0.  1. Let's use the results of the 2012 presidential election as our x0. Looking up the popular vote totals, we find that our initial distribution vector should be (0.5106, 0.4720, 0.0075, 0.0099)T. Enter the matrix P and this vector x0 in MATLAB:

```>> ```P = [0.8100 0.0800 0.1600 0.1000;
0.0900 0.8400 0.0500 0.0800;
0.0600 0.0400 0.7400 0.0400;
0.0400 0.0400 0.0500 0.7800]```

>> `x0 = [0.5106; 0.4720; 0.0075; 0.0099]````

According to our model, what should the party distribution vector be after three, six, and ten elections?

2. What about 30, 60, and 100 elections from now? How different are these three results from each other? Summarize what is happening with xk as k gets big.

## Conclusion

Hopefully, this lab has given you a little more intuition for the properties of matrices and their differences from real numbers. In the last exercise, you've also made some interesting observations about what happens when we apply the same matrix to a vector over and over again. In the next lab, we'll develop more mathematical tools to help explain this behavior.