[FrontPage] [TitleIndex] [WordIndex

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.

1.1. Solution

  1. We want to show that ((AB)T)ij = (AB)ji = (BTAT)ij. From the definition of matrix multiplication we have (AB)ji = ∑k AjkBki and (BTAT)ij = ∑k (BT)ik(AT)kj = ∑k AjkBki = (AB)ji.

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

  3. Disproof: Let A = $\left[\begin{array}{cc}0 & 1 \\ -1 & 0\end{array}\right]$. Then an easy computation shows AAT = ATA = 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 AAT = ATA. Let A = $\left[\begin{array}{cc}a & b \\ c & d\end{array}\right]$ and compute AAT and ATA. Matching up entries gives a2+b2 = a2+c2 from which b2 = c2; d2+b2 = d2+c2; 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 b2 = c2, 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 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 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 ∑ Ak. 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 Ak = 0 for all k > n-1, implying the sum converges. But then we have (A-I)(∑ Ak) = A ∑ An - ∑ Ak = -A0 = -I. So (A-I)-1 = -∑ Ak.

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

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 ℝ1; 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 Ai⋅x ≤ bi for each i, where Ai is the i-th row of A. So the set of points S satisfying the inequality Ax≤b is the intersection of the sets Si = { x | Ai⋅x ≤ bi }. Since each set Si 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.

  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