[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. Affine transformations

An affine transformation is a function f:ℝm→ℝn of the form f(x) = Mx + b where M is an n×m matrix and b is a column vector.

  1. Prove or disprove: if f:ℝm→ℝn and g:ℝn→ℝk are both affine transformations, then (g∘f) is also an affine transformation.

  2. Prove or disprove: if f:ℝn→ℝn is an affine transformation and f-1 exists, then f-1 is also an affine transformation.

1.1. Solution

  1. Proof: Let f(x) = Ax+b and g(y) = Cy+d. Then g(f(x)) = g(Ax+b) = C(Ax+b)+d = (CA)x + (Cb+d).
  2. Proof: Let f(x) = Ax+b. We'll find an inverse for f by solving the equation y = Ax+b for x in terms of y: this gives x = A-1(y-b) = A-1y - A-1b. This has the right form to be an affine transformation, provided A-1 exists. If A-1 does not exist, then either A is not surjective or not injective. If A is not surjective, then there is some y such that no x satisfies Ax = y. But then no x satisfies Ax + b = y+b, which means f isn't surjective either. If A is not injective, then there exist distinct x and y such that Ax = Ay. But then f(x) = Ax + b = Ay + b = f(y), so f is also not injective. So under the assumption that f-1 exists, A-1 exists as well, and we have f-1 = A-1y - A-1b is affine.

2. Pythagoras goes mod

Let x and y be vectors in (ℤp)n, where p is a prime.

Show that if (x+y)⋅(x+y) = x⋅x + y⋅y, then either x⋅y = 0 (mod p) or p = 2.

2.1. Solution

Calculate (x+y)⋅(x+y) = x⋅x + x⋅y + y⋅x + y⋅y = (x⋅x + y⋅y) + 2(x⋅y). For this to equal (x⋅x + y⋅y), we need 2(x⋅y) = 0 (mod p), or p|(2(x⋅y)). Since p is prime, it divides a product if and only if it divides one of the factors. If p|2, then p = 2; otherwise, p|(x⋅y), which means (x⋅y) = 0 (mod p).

3. Convexity

A set of points S in ℝn is convex if, for any x,y∈S, and any 0 ≤ λ ≤ 1, the point λx + (1-λ)y is in S. (Intuitively, this means that the line segment between any two points in S is also in S; visually, S has no dimples or holes.)

  1. Prove or disprove: If f:ℝn→ℝm is a linear transformation, and S is convex, then f(S) = { f(x) | x∈S } is convex.

  2. Prove or disprove: If f:ℝn→ℝm is a linear transformation, and f(S) is convex, then S is convex.

3.1. Solution

  1. This one is just calculation: Let f(x) and f(y) be in f(S), and let 0 ≤ λ ≤ 1. Then λx + (1-λ)y is in S, so f(λx + (1-λ)y) = λf(x) + (1-λ)f(y) is in f(S).
  2. Disproof: Let f(x) = 0. Then f is linear (f(ax) = af(x) = 0, f(x+y) = 0 = f(x) + f(y)), and f(S) is convex for all S, since for any x,y∈S we have λf(x) + (1-λ)f(y) = 0 ∈ f(S). But we can easily find a non-convex S (e.g. { (0), (1) } in ℝ1), giving a counterexample to the claim.

2014-06-17 11:57