/Solutions

1. Transposes and symmetry

Recall that the transpose A^T of an n×m matrix A is the m×n matrix whose entries are given by the rule (A^T)_ij = A_ji. 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 = B^TA^T.

2. Show that for any matrix A, both of AA^T and A^TA exist and are symmetric.

3. Prove or disprove: If AA^T = A^TA, 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 A_ij = 1 if ij∈E and 0 otherwise.

Use the fact that (A^k)_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.¹