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.

1.1. Solution

1. We want to show that ((AB)^T)_ij = (AB)_ji = (B^TA^T)_ij. From the definition of matrix multiplication we have (AB)_ji = ∑_k A_jkB_ki and (B^TA^T)_ij = ∑_k (B^T)_ik(A^T)_kj = ∑_k A_jkB_ki = (AB)_ji.

2. Existence depends only on having compatible dimensions; if A is an n×m matrix, then A^T is an m×n matrix, and so both products AA^T (n×m by m×n) and A^TA (m×n by n×m) work. To show there are symmetric, use the answer to part 1 to observe that (AA^T)^T = (A^T)^TA^T = AA^T and similarly (A^TA)^T = A^T(A^T)^T = A^TA.

3. Disproof: Let A = . Then an easy computation shows AA^T = A^TA = I, but A is not symmetric.

How I found the counterexample matrix for the last part: Suppose A is a 2-by-2 matrix and AA^T = A^TA. Let A = and compute AA^T and A^TA. Matching up entries gives a²+b² = a²+c² from which b² = c²; d²+b² = d²+c²; and ac + bd = ab + cd. The second equation follows from the first, and the third can be made true by setting a = d = 0. This leaves b² = c², which we can make true without having b=c by setting b = -c.

Other counterexamples probably exist.

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

2.1. Solution

Following the hint, we compute ∑ A^k. No path can have more than n-1 edges without repeating vertices; so if the graph is acyclic, it follows that there are no paths of length k > n-1 and thus that A^k = 0 for all k > n-1, implying the sum converges. But then we have (A-I)(∑ A^k) = A ∑ Aⁿ - ∑ A^k = -A⁰ = -I. So (A-I)^-1 = -∑ A^k.

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

3.1. Solution

1. Let x and y be in S∩T. Then x,y∈S and convexity of S implies z=ax+(1-a)y ∈ S. Similarly x,y∈T implies z∈T. Thus z∈S∩T and S∩T is convex.

2. Consider the sets S = { 0 } and S = { 1 } in ℝ¹; then S∪T does not contain (1/2)0 + (1/2)1 = 1/2.

3. Let x⋅z≤b and y⋅z≤b. Then (ax+(1-a)y)⋅z = a(x⋅z) + (1-a)(y⋅z) ≤ ab + (1-a)b = b.

4. Observe that Ax≤b if and only if A_i⋅x ≤ b_i for each i, where A_i is the i-th row of A. So the set of points S satisfying the inequality Ax≤b is the intersection of the sets S_i = { x | A_i⋅x ≤ b_i }. Since each set S_i is convex (by the previous part) and the intersection of convex sets is convex (use part 1 plus induction on the number of sets), S is convex.