1)Let M be the random walk matrix of an undirected regular graph G ( as defined in section 2.4.2)
a) lambda(G) as defined in 2.50, is the second largest eigenvalue of M
b) Let u be the vector (1/N,...,1/N) representing the uniform distribution.
Let v be a vector such that <u,v>=0.
Prove that <u,vM> =0.
2)Prove that for the spectral norm || || of an N*N matrix (dfn 4.5), we have for
matrices A,B ||A+B|| <= ||A|| + ||B||.
3) Use the connection between samplers and extractors (6.24) to show that the
sampler of Theorem 4.23 and Corollary 4.41 implies the following:
For some constant 0<a<1, an explicit (k=a*n,1/100)-extractor with seed length
d=O(log n ) and output length m = Omega(k).
4)Solve Problem 4.8.
5)Solve Problem 4.9.