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

## 1.1. Solution

We want to show that ((AB)

^{T})_{ij}= (AB)_{ji}= (B^{T}A^{T})_{ij}. From the definition of matrix multiplication we have (AB)_{ji}= ∑_{k}A_{jk}B_{ki}and (B^{T}A^{T})_{ij}= ∑_{k}(B^{T})_{ik}(A^{T})_{kj}= ∑_{k}A_{jk}B_{ki}= (AB)_{ji}.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^{T}A (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})^{T}A^{T}= AA^{T}and similarly (A^{T}A)^{T}= A^{T}(A^{T})^{T}= A^{T}A.Disproof: Let A = . Then an easy computation shows AA

^{T}= A^{T}A = 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^{T}A. Let A = and compute AA^{T} and A^{T}A. Matching up entries gives a^{2}+b^{2} = a^{2}+c^{2} from which b^{2} = c^{2}; d^{2}+b^{2} = d^{2}+c^{2}; 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^{2} = c^{2}, 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^{n} - ∑ A^{k} = -A^{0} = -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.

- 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}

## 3.1. Solution

- 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.
Consider the sets S = { 0 } and S = { 1 } in ℝ

^{1}; then S∪T does not contain (1/2)0 + (1/2)1 = 1/2.- 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.
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.

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

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