# 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.

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

^{T}= B^{T}A^{T}.Show that for any matrix A, both of AA

^{T}and A^{T}A exist and are symmetric.Prove or disprove: If AA

^{T}= A^{T}A, 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.

- Prove that if S is convex and T is convex, then S∩T is convex.
- Give an example that shows even if S and T are convex, S∪T is not necessarily convex.
Show that for any vector z and constant b, the

**half-space**H = { x | x⋅z≤b } is convex.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}

When x and y are vectors, the notation x≤y means that x

_{i}≤y_{i}for all indices i. (1)