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. Transposes and symmetry

Recall that the transpose AT of an n×m matrix A is the m×n matrix whose entries are given by the rule (AT)ij = Aji. A matrix is symmetric if it equals its own transpose.

1. Use the definition of matrix multiplication to show that, for any compatible matrices A and B, (AB)T = BTAT.

2. Show that for any matrix A, both of AAT and ATA exist and are symmetric.

3. Prove or disprove: If AAT = ATA, then A is symmetric.

2. Finite paths

Recall that the adjacency matrix A of a directed graph G = (V,E), where V = {1..n}, is given by the rule Aij = 1 if ij∈E and 0 otherwise.

Use the fact that (Ak)ij counts the number of i-j paths in G of length k to show that if G is acyclic, then the matrix (A-I) is invertible. Hint: Count the total number of i-j paths in G.

3. Convex bodies

A set of vectors S is convex if, for any two vectors x and y in S, and any scalar a with 0≤a≤1, the vector ax+(1-a)y is also in S.

1. Prove that if S is convex and T is convex, then S∩T is convex.
2. Give an example that shows even if S and T are convex, S∪T is not necessarily convex.
3. Show that for any vector z and constant b, the half-space H = { x | x⋅z≤b } is convex.

4. Show that for any matrix A and column vector b (of appropriate dimensions), the set of all vectors x such that Ax≤b is convex.1

1. When x and y are vectors, the notation x≤y means that xi≤yi for all indices i. (1)

2014-06-17 11:57