Use Python, NumPy, and Matplotlib to complete the following Tasks:

3.4. Multiplying a Matrix Times a Vector 51

3.4.1 Applications of Multiplying a Matrix Times a Vector

The geometric applications of multiplying a matrix by a vector are very impor- tant and interesting, but too complex for a short discussion here. These are discussed in Chapter 6.

The simplest applications of M ·�v are those for which we are interested in the dot product of each of the rows with the vector separately. For instance, in Application 2.4 (grocery shopping), let B be a matrix of shopping baskets, where B [i , j ] is the number of item j that person i is buying, and let �p be a vector of prices, where �p [ j ] is the price of item j . Then B ·�p is a vector of total cost for each person; that is, (B · �p )[i ] is the cost of the shopping basket for person i .

Similarly, let P be a matrix of prices of items at stores, where P [i , j ] is the price of item j at store i , and let �b be the vector of a shopping basket, where �b [ j ] is the number of item j to be bought. Then P ·�b is the vector of the cost of the basket by store; that is (P ·�b )[i ] is the cost of the shopping basket at store i .

More interesting, perhaps, are the applications in which M represents a transformation of the vector as a whole.

Application 3.3 (Transition matrix). Let �v represent the populations of a col- lection of cities at a given time. Let M be an annual transition matrix for pop- ulations. That is, for any two cities i and j , if i �= j , M [i , j ] is the fraction of the inhabitants of j who move to i . M [i , i ] is the fraction of the inhabitants of i who remain at i . Ignoring births and deaths, what is the population of city i after a year? First, there are the people who stayed in i ; there are M [i , i ] ·�v [i ] of these. Then there are the people who immigrated to i ; from each city j , the number of people who have immigrated to i is M [i , j ]�v [ j ]. Therefore, the total number of people in i is

∑ j M [i , j ] ·�v [ j ] = M [i , :] •�v , and M�v is the vector of

populations after a year. For instance, suppose there are three cities A, B, and C, with the following

transitions:

• Of the population of A, 70% remain in A; 20% move to B, and 10% move to C.

• Of the population of B, 25% move to A; 65% remain in B, and 10% move to C.

• Of the population of C, 5% move to A; 5% move to B, and 90% remain in C.

Thus, the transition matrix is⎡ ⎣ 0.7 0.25 0.050.2 0.65 0.05

0.1 0.1 0.9

⎤ ⎦ .

52 3. Matrices

If initially there are 400,000 people in A, 200,000 in B, and 100,000 in C, then after a year, the population vector will be given by

⎡ ⎣ 0.7 0.25 0.050.2 0.65 0.05

0.1 0.1 0.9

⎤ ⎦·

⎡ ⎣ 400, 000200, 000

100, 000

⎤ ⎦ =

⎡ ⎣ 335, 000215, 000

150, 000

⎤ ⎦ .

Note that each column of the matrix adds up to 1; this corresponds to the fact that total number of people remains constant. A matrix whose columns add to 1 is known as a stochastic matrix; we study these in greater depth in Chapter 10.

Application 3.4 (Smoothing a signal). Let �v be a time sequence of a numeric quantity, as in Application 2.2. Suppose that we wish to eliminate noise from a signal. One standard way to do this is to estimate the true value of the signal at each point of time by using the weighted average of the signal at nearby points; this is known as smoothing the signal. The width of the range depends both on the frequencies of the noise and the signal and on the signal-to-noise ratio; ideally, we want to average over a range larger than the wavelength of the noise, smaller than the wavelength of the signal, and over a set of points large enough that the noise will average out to zero.

Let �d [t ] be the data at time t and let �s [t ] be the estimate of the signal. If the signal frequency is very high and the noise is fairly small, then we might estimate the signal at time t , �q [t ] = 1/3·( �d [t −1]+ �d [t ]+ �d [t +1]). Of course, at

1 2 3 4 5 6 7 8 9 10 11 −0.2

0

0.2

0.4

0.6

0.8

1

1.2

Figure 3.1. Smoothing. The noisy points are the circles on the solid line. The smoothed points are the asterisks on the dashed line.

3.4. Multiplying a Matrix Times a Vector 53

the beginning of the time range, where �d [t −1] is not recorded, and at the end, where �d [t + 1] is not recorded, we have to do something different; what we do is just set �q [1] = �d [1] and �q [k ] = �d [k ].

Each of these sums is a weighted average of the data; the entire transforma- tion of signal to noise is thus the multiplication of the data vector by a smooth- ing matrix. For instance, consider the following artificial data. The true signal �s is just the quadratic function �s [i ] = 1 − ((i − 6)/5)2 for i = 1, . . . , 11; thus, �s = ⟨0, 0.36, 0.64, 0.84, 0.96, 1, 0.96, 0.84, 0.64, 0.36, 0⟩. The noise �n is generated by the MATLAB expression � 9� � " ����+���� � 9�. The data �d =�s +�n = ⟨0.0941, 0.4514, 0.6371, 0.9001, 0.8884, 0.9844, 1.0431, 0.8984, 0.7319, 0.3911, −0.0929⟩.

We smooth the data by carrying out the following multiplication (Figure 3.1):⎡ ⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

1 0 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0

0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 1/3 1/3 1/3 0 0 0 0 0 0 0 0 0 0 1

⎤ ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

·

⎡ ⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

0.0941 0.4514 0.6371 0.9001 0.8884 0.9844 1.0431 0.8984 0.7319 0.3911 −0.0929

⎤ ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

=

⎡ ⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣

0.0941 0.3942 0.6629 0.8085 0.9243 0.9720 0.9753 0.8912 0.6738 0.3434 −0.0929

⎤ ⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦

.

The correlation of the data with the ideal signal is 0.9841. The correlation of the smoothed data with the ideal signal is 0.9904.

Application 3.5 (Time-shifting a signal). Another operation on time sequences that can be modeled as matrix multiplication is time-shifting. Suppose you have a signal �s of length n and wish to construct the same signal shifted q units later; that is, �z [i ] =�z [i−q ]. This can be viewed as multiplication by an n×n ma- trix M such that M [i +q , i ] = 1 for i = q +1, . . . , n and M [i , j ] = 0 for all j �= i +q . For example, with n = 6, q = 2,⎡

⎢⎢⎢⎢⎢⎢⎢⎣

0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0

⎤ ⎥⎥⎥⎥⎥⎥⎥⎦ ·

⎡ ⎢⎢⎢⎢⎢⎢⎢⎣

2 8 5 7 1 4

⎤ ⎥⎥⎥⎥⎥⎥⎥⎦ =

⎡ ⎢⎢⎢⎢⎢⎢⎢⎣

0 0 2 8 5 7

⎤ ⎥⎥⎥⎥⎥⎥⎥⎦

.

This may seem like quite an elaborate and verbose way of formulating a very simple operation, and if all you want to do is a time-shift, it certainly would be. But the point is that you can then combine it with other matrix operations and apply the results of matrix theory to these combinations.