Math 19B: linear algebra and probability

Oliver Knill, Spring 2011

Problem 1) TF questions (20 points) 1) 2) 3) T T T T T T T T T T T T T T T T T T T T T F F F F F F F F F F F F F F F F F F F F F A random variable on the probability space = {1, 2, . . . , 10 } satisfying P[X = k ] = 10!/(k !(10 k )!210 ) has the expectation E[X ] = 10/2. There is a system of linear equations Ax = b which has exactly 2 solutions. If the sum of all geometric multiplicities of a 3 3 matrix A is equal to 3, then A is diagonalizable. If a system of linear equations Ax = b has two dierent solutions x, then the nullety of A is positive. If a matrix A is invertible then its row reduced echelon form is also invertible. All symmetric matrices are invertible. All symmetric matrices have simple spectrum in the sense that all of the eigenvalues are dierent. The geometric multiplicity is always larger or equal than the algebraic multiplicity. The Google matrix is a Markov matrix If a 3 3 matrix has positive entries and is symmetric, then all eigenvalues are dierent. If a 2 2 matrix has positive entries, then both eigenvalues are real and dierent. If two random variables X, Y are independent then [X + Y ] = [X ]+ [Y ]. An exponentially distributed random variable has positive expectation. The variance of the Cauchy distributed random variable is 1. If two events A, B satisfy that P[A|B ] = P[A] then A, B are independent. For the Monty-Hall problem, it does not matter whether you switch or not. The winning chance is the same in both cases. A random variable on a nite probability space {1, 2, 3 } can be interpreted as a vector with three components. The composition of two reections in the plane is an orthogonal transformation. If P[A|B ] and P[A] and P[B ] are known, then we can compute P[B |A]. If the P -value of an experiment is less than 15 percent, then the null hypothesis is rejected. Its not 15 percent.

5/6/2011: Final exam

Your Name:
Please enter your name in the above box. You have to do this exam on your own. You can write the solutions on your own paper. Make sure you write your name on each page and staple it together at the end. Please write neatly Answers which are illegible for the grader can not be given credit. Unless stated, give computations, details reasons. The suggested exam time is Friday, the 6th of May. No calculators, computers, or other electronic aids are allowed. There is no time limit but 3 hours should suce. Bring your exam to my oce in 434 on Monday May 9th, 2011 until noon 12. I need to get the paper in Person this can be done on Friday at 4 or Monday between 10 and 12 AM. The exam is open book in the sense that you can use any of the distributed class lecture notes and any of your handwritten notes but no other books or text resources. 1 2 3 4 5 6 7 8 9 10 11 12 13 Total: 20 10 10 10 10 10 10 10 10 10 10 10 10 140

4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19) 20) 21)

Problem 2) (10 points) a) (5 points) Which matrices are diagonalizable? Which ones are Markov matrices? Matrix 1/2 2/3 1/2 1/3 1/2 2/3 1/2 1/2 1/2 2/3 1/2 1/3 1 2 0 1 1 0 0 1 diagonalizable Markov

Problem 3) (10 points) Systems of linear equations Consider the following system of linear equations: 3x + y + z = x x + 3y + z = y x + y + 3z = z You can interpret the above system as an eigenvalue problem Ax = x for a 3 3 matrix A. What are the eigenvalues and what are the eigenvectors?

Problem 4) (10 points) Bayesan statistics We throw 5 fair dice. Let A be the event that the sum of the rst four dice is 5. Let B be the event that the sum of the last two dice is 6. a) (4 points) Find the probabilities P[A], P[B ]. b) (3 points) Find the conditional probability P[B |A]. c) (3 points) What is the conditional probability P[A|B ]?

b) (3 points) Match the transformation with the trace and determinant: trace 1 0 0 1 2 -2 det enter A-F 0 -1 1 1/4 1 1 label A B C D E F transformation reection at the origin rotation by -90 degrees projection onto x-axes dilation by 1/2 reection at a line vertical shear

Problem 5) (10 points) Basis and Image Dene the solar matrix
A=

c) (2 points) Draw the image of the picture to the left under the linear transformation given by 1 1 the matrix A = . Make sure to indicate clearly which arrow goes where. 1 2

2 1 1 1 1 1 1 1 1 1

1 1 0 0 0 0 0 0 0 0

1 0 1 0 0 0 0 0 0 0

1 0 0 1 0 0 0 0 0 0

1 0 0 0 1 0 0 0 0 0

1 0 0 0 0 1 0 0 0 0

1 0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 1 0 0

1 0 0 0 0 0 0 0 1 0

1 0 0 0 0 0 0 0 0 1

a) (4 points) Find a basis for the eigenspace to the eigenvalue 1 that is the kernel of B = A I10 . b) (3 points) Find a basis for the image of B . c) (3 points) Find the determinant of A.

Problem 6) (10 points) Inverse and Coordinates

a) (5 points) Verify that if B 0 0 A= 0 C 0 0 0 D

a) (3 points) Find the determinant of the matrix

0 A= 0

where B, C, D are 2 2 matrices, then A1 b) (5points) Invert the matrix 2 1 0 0 0 0 3 2 0 0 0 0 0 0 3 2 0 0 A= 0 0 0 3 0 0 . 0 0 0 0 3 1 0 0 0 0 1 3

0 6 0 0 3 0

0 7 0 0

0 0 9 0

B 1 0 0 0 C 1 0 . 0 0 D 1

b) (3 points) Find the determinant of the matrix

A=

9 1 1 1 1 1 1 1

1 9 1 1 1 1 1 1

1 1 9 1 1 1 1 1

1 1 1 9 1 1 1 1

1 1 1 1 9 1 1 1

1 1 1 1 1 9 1 1

1 1 1 1 1 1 9 1

1 1 1 1 1 1 1 9

c) (4 points) Find the determinant of the matrix

Problem 7) (10 points) Expectation, Variance, Covariance We throw 5 fair dice and call Xk the number of eyes of dice k . As usual, the Xk are assumed to be independent. Let X = X1 + X2 + X3 denote the sum of the rst 3 dice and Y = X4 + X5 denote the sum of the last two dice. Find the correlation Cov[X, Y ] between the two random variables X, Y .

A=

1 1 1 1 1 1 1 1

2 0 2 2 2 2 2 2

3 3 0 3 3 3 3 3

4 5 6 7 4 5 6 7 4 5 6 7 0 5 6 7 4 0 6 7 4 5 0 7 4 5 6 0 4 5 6 7

8 8 8 8 8 8 8 0

Please indicate clearly the method you have used and as usual provide details for the computation. Problem 8) (10 points) Eigenvalues and Eigenvectors a) (7 points) Find all the eigenvalues and eigenvectors of the matrix

Problem 10) (10 points) Law of large numbers, Central limit theorem A dice is not fair and shows number 1 2 3 4 5 6 probability 1/7 1/7 1/7 1/7 2/7 1/7

A=

0 4 0 0 0 0 3

3 0 4 0 0 0 0

0 3 0 4 0 0 0

0 0 3 0 4 0 0

0 0 0 3 0 4 0

0 0 0 0 3 0 4

4 0 0 0 0 3 0

Hint: Write A as 3Q + 4QT for some orthogonal matrix Q for which you know how to compute the eigenvalues and eigenvectors. b) (3 points) Find the determinant of A.

a) (4 points) Find the mean m and standard deviation of X . Problem 9) (10 points) Determinants b) (3 points) If Xk shows the number of eyes of the k th dice, what is n ?
1 n n k =1 Xk

in the limit

c) (3 points) The random variables

(Xk m) n k =1 converge. In which sense and to what?

a) (1 point) The Bayes formula allows to compute P[A|B ] if P[A], P[B |A] and 1 are known.
converges to the 2 . b) (1 point) The central limit theorem assures that Sn

c) (1 point) The law of large numbers assures that Sn /n converges to 3 . d) (1 point) Chebyshevs theorem assures that P[|X E[X ]| c] 4 .

Problem 11) (10 points) Diagonalizable matrices Among all 2 2 upper triangular matrices for which the entries are 0 or 1. What is the probability that the matrix is diagonalizable? The probability space is 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 0 0 1 1 } 0 1

e) (1 point) Perron-Frobenius assures that a 5 matrix has a unique largest eigenvalue 1. f) (1 point) The spectral theorem tells that a 6 matrix has an orthonormal eigenbasis. 1 2 3 4 5 6 g) (4 points) These six main results have practical applications. Find a match between applications and results so that each result a) - f) appears exactly once. Application Estimating P-values of an experiment Google page rank Monte Carlo integration method Counting method in Blackjack Change basis to get uncorrelated random variables. Estimate the tail distribution P[|X | c] enter a)-f)

={

and we assume that we have the uniform distribution on .

Problem 12) (10 points) Markov matrices You are given a network A, B, C of 3 nodes where all neighboring nodes link to each other but B only links to C and not to A. Find the page rank for each nodes in the case when the damping factor is d = 0.5.

Problem 13) (10 points) Important theorems Complete the placeholders in the following sentences. As usual, we use the notation Sn = X 1 + X 2 + + X n and denote by X the normalized random variable X = (X E[X ])/ [X ] .