Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

# 1. Diagonal matrices

A matrix A is a diagonal matrix if it is a square matrix with Aij=0 whenever i≠j.

1. Prove or disprove: If A and B are diagonal matrices of the same size, so is AB.
2. Let p(A)=Πi Aii. Prove or disprove: If A and B are diagonal matrices as above, then p(AB) = p(A)p(B).

# 2. Matrix square roots

1. Show that there exists a matrix A such that A≠0 but A²=0.
2. Show that if A²=0, there exists a matrix B such that B²=I+A. Hint: What is (I+A)²?

# 3. Dimension reduction

Let A be an n×m random matrix obtained by setting each entry Aij independently to ±1 with equal probability.

Let x be an arbitrary vector of dimension m.

Compute E[||Ax||²], as a function of ||x||, n, and m, where ||x|| = (x⋅x)1/2 is the usual Euclidean length.

# 4. Non-invertible matrices

Let A be a square matrix.

1. Prove that if Ax=0 for some column vector x≠0, then A-1 does not exist.

2. Prove that if the columns of A are not linearly independent, then A-1 does not exist.

3. Prove that if the rows of A are not linearly independent, then A-1 does not exit.

2014-06-17 11:57