Professor Shai Simonson

CSC 202

Discrete Math for Computer Scientists II

Assignment 5

Due:  Last day of class.

Pettofrezzo text:  3.4 - 2, 4, 6.  3.5 - 6.  4.1 - 2, 4, 6, 8, 10.   4.3 - 1.  4.4 - 2, 4, 6, 7.   4.5 - 2, 4, 6, 7

1.  What is the 2x2 matrix that rotates shapes by 60 degrees counterclockwise?  Show how to write this matrix as a product of elementary matrices.  Explain whether each elementary matrix is a reflection, shear, or dilation/magnification, and in what directions.

2. Find matrices P and D that diagonalize each matrix A below.  That is, find a diagonal matrix D, such that A = PDP-1. Use your result to calculate A10.

2    0   -2                    .25    .9                1    0
0    3    0                    .75    .1               -1    2
0    0    3

3.  Recall that an n by n matrix is diagonalizable if it has n distinct eigenvalues.   Prove that the general 2 by 2 matrix

a    b
c    d

is diagonalizable if (a-d)2 + 4bc is positive.

4.  Prove that the eigenvalues of a triangular matrix are the same as the entries of the main diagonal. 

5.  Two matrices A and B are said to be similar if there is an invertible matrix C such that AC = CB. 
    a.  Prove that if X is similar to Y and Y is similar to Z, then X is similar to Z. 
    b.  Prove that two similar matrices have the same determinant and the same eigenvalues.

6.  In the RI/CT/MA area, 5% of MA residents move to CT each year, and 5% move to RI.  In CT each year, 15% of the residents move to MA, and 10% to RI.  In RI each year, 10% move to MA and 5% to CT.  Assuming that no one moves in or out of  these 3 states from an outside state, model this as a Markov Process, and calculate what percent of the total population live in each state after a long period of time.  Note that it does not matter how the population distribution begins.

7.  Imagine that a mouse is in a maze with 9 "rooms" that looks like a Tic-Tac-Toe board.  The rooms are connected through the edges of the board but not diagonally.  For example, the center room connects right, left, above and below.  The outer rooms have doors that exit the maze.  The side rooms have one exit door each and the corner rooms have two. Once the mouse exits the maze it is free.  Assume that the chances of moving into any new room from a given room, as well as the chance of exiting the maze or staying put are all equal.  Thus your matrix has one absorbing state.  Assuming the mouse is dropped into the center room to start off, and that it makes a random move every minute. 
a.  Calculate the expected number of moves before the mouse exits the maze.
b.  Calculate the expected number of times that the mouse will be in each given room before it exits.
c.  If all the exit gates are closed, so that there is no absorbing state, calculate the chances of being in each of the 9 rooms after the probabilities converge.

You should use an online matrix calculator, or Maple, or Matlab to help you do your calculation.

8.  Assume you are trying to decode a matrix cipher that your intelligence people have determined is encoded in blocks of 3 characters using a 3x3 matrix with (0, 0, 0) shift.  Decode HPAFQGGDUGDDHPGODYNOR if the first 9 letters are known to decode to "IHAVECOME".  Note: Assume that A is 1, B is 2, ... and Z = 0.

9.  Find the best fitting line of the following points using the method of linear regression (least squares) we did in class.  The points are:  (2, 5) (3, 6) (6, 12) (8, 15) (11, 19).

10.  Write down a 3x3 matrix that will rotate a picture 30 degrees about the y-axis.  Then move it 4 coordinates right (x-axis) and 3 coordinates down (z-axis).  Then stretch it in all dimensions by a factor of 2.  You should write each piece of the transformation as a 3x3 matrix, and combine them together with appropriate multiplications and/or additions, to get a single transformation Ax + B, where A is 3 by 3, x is 3 by 1, and B is 3 by 1..