A cool group theory problem.

I found the following problem in a group theory textbook. A friend and I solved it over lunch.

Let G be a finite group and suppose that φ is an automorphism of G which is its own inverse, and which has no nontrivial fixed points. Prove that φ(x) = x^-1 for each x in G, and that G is abelian.

We will write the binary operation by juxtaposing elements of G, and the identity element will be denoted by e. First, define a function F: G → G by F(x) = x^-1φ(x). Then F is one-to-one. To see this, suppose F(x) = F(y) for some x, y ∈ G; this yields φ(x)φ(y)^-1 = xy^-1, and since φ is a homomorphism, we get φ(x)φ(y)^-1 = φ(xy^-1). So xy^-1 is a fixed point for φ, and since φ only fixes e, we must have xy^-1 = e, or x = y. Therefore F is one-to-one; and F is onto (as a set map) because it injectively maps G to G. (This a cool argument my friend came up with, based on the finiteness of G and the pigeonhole principle.)

Since F is a permutation of G, we understand the following: to each element x ∈ G, there exists g ∈ G such that x = g^-1φ(g). From this, we check that

φ(x) = φ(g^-1φ(g)) = φ(g)^-1φ(φ(g)) = φ(g)^-1g.

Then, notice xφ(x) = g^-1φ(g)φ(g)^-1g = e, so that φ(x) = x^-1. This holds for each element x of G, so the first result is proven.

Now to see that G is abelian, suppose x, y ∈ G. Then, because φ is a homomorphism, we get

xy = (y^-1x^-1)^-1 = φ(y^-1x^-1) = φ(y^-1)φ(x^-1) = yx

so that G is abelian. □

Optimization on convex regions

For a while, I’ve been wondering why people love to talk about convex sets and functions. I’ve read that, often, a problem will be changed so that it accommodates convexity, in order to make the problem “nicer”. I never understood why. Today I learned an explicit reason for why convexity is such a nice property to expect and I want to detail that here. NOW IS THE TIME.

A set V ⊆ ℝⁿ is convex when, for any x, y ∈ V and λ ∈ [0, 1], we have λx + (1 - λ)y ∈ V. Geometrically, a set is convex when it contains the line segment between every pair of its points. Another way to state this follows: if x, y ∈ ℝⁿ, we define the line segment L[x, y] := {λx + (1 - λ)y : λ ∈ [0, 1]}; a convex set is a set V ⊆ ℝⁿ such that L[x, y] ⊆ V for any points x, y ∈ V. The intersection of convex sets is convex, but in general, the union of convex sets is not.

A convex function is any function F: ℝⁿ→ ℝ such that, for any x, y ∈ ℝⁿand λ ∈ [0, 1], we have F(λx + (1 - λ)y) ≤ λF(x) + (1 - λ)F(y). This requires that the graph of the function lies below any line segment connecting points on the graph.

Now let (P) denote the following optimization problem: given a set V ⊆ ℝⁿ, we want to find the minimum value of a function F: V → ℝ. More explicitly, we want the value of min{F(x) : x ∈ V}, so long as the value exists. The set V is called the feasible region of (P), and the function F is called the objective function for (P).

We say that a point x₀ ∈ V is locally optimal for (P) if there exists a number δ > 0 such that, when x ∈ V and ||x - x₀|| < δ, we have F(x) > F(x₀). More concisely, if x ∈ V ∩ D(x₀, δ), then F(x) > F(x₀), where D(p, r) := {x ∈ ℝⁿ : ||x - p|| < δ}. We say x₀ is globally optimal for (P) when x₀ yields a minimum value for F on the whole feasible region of (P), i.e. F(x) > F(x₀) for every point x ∈ V. The best part about convexity is that the these two notions are equivalent when V and F are convex:

Prop. Suppose that F is a convex function, V is a convex set, and x₀ ∈ V. Then x₀ is locally optimal for (P) if and only if x₀ is globally optimal for (P).

Proof. The necessity of the condition is clear. To see sufficiency, suppose x₀ is locally optimal for (P): there exists δ > 0 such that, if x is feasible for (P) and ||x - x₀|| < δ, we have F(x) > F(x₀). Suppose that x₀ is not globally optimal; i.e. there exists a point y ∈ V such that F(x₀) > F(y) (so y gives a better objective value for (P)). We must have ||y - x₀|| ≥ δ.

To achieve a contradiction, we will take a point near x₀ and on the line segment from x₀ to y. Take λ := δ/(2||y - x₀||) so that 0 < λ < 1, and let x := λy + (1 - λ)x₀. Then x ∈ V since V is convex, so x is feasible for (P). Also,

||x - x₀|| = ||λy + (1 - λ)x₀ - x₀|| = λ||y - x₀|| = δ/2 < δ,

so we must have F(x) > F(x₀). But F is a convex function, so

F(x) ≤ λF(y) + (1 - λ)F(x₀) < λF(x₀) + (1 - λ)F(x₀) = F(x₀);

a contradiction. Therefore, such a point y ∈ V cannot exist, and so x₀ is globally optimal for (P). □

I can’t wait to learn more about the magic of convexity!

A proof of the connection between factorials and pi, from combinatorics

When life gives you lemmas, make lemmanade!

Carl Friedrich Gauss’s signature. Integral signs in his signature, like a BAUSS.

This a 1984 spaceship game called Elite.

Each spaceship in the game was a convex polygon, so the program was able to rapidly determine which direction the spaceship was facing in order to decide which polygons to draw on the ship. This helped create the awesome technically innovative 3D effect — super cool, back when the game was developed. You can see that the spaceships don’t look like “see-through” wireframes, instead they appear as three-dimensional polygons with solid surfaces.

So, convex sets allowed the game to run smoothly on a computer with the processing power of today’s greeting card (one that records stuff).

Fuck yeah convex sets! 

Alright, non-singular square matrices. Bring it on.

We are using every equivalent condition for matrix invertibility in my optimization class. There are a brazilian things equivalent to invertibility (non-singularity) of a matrix over a field Let’s prove the most interesting results. I’ll assume most preliminaries because this probably won’t be interesting for someone not interested in linear algebra anyway.

Proposition. Let T be an n-by-n matrix over the field K. The following are equivalent.

(1) T is invertible; i.e. there exists an n-by-n matrix U such that TU = UT = I, where I denotes the n-by-n identity matrix. (It can be shown that the matrix U is uniquely determined by T, and we write U = T^-1.)
(2) If x ∈ Kⁿ, then Tx = 0 if and only if x = 0.
(3) T is an injective map.
(4) The columns of T are linearly independent.
(5) The columns of T generate Kⁿ.
(6) For each y ∈ Kⁿ, there exists a unique x ∈ Kⁿ such that Tx = y.
(7) 0 is not an eigenvalue of T.
(8) The determinant of T is nonzero, i.e. det T ≠ 0.

Proof. (1) ⇒ (2). Suppose x ∈ Kⁿ with Tx = 0. Multiplying on the left by T^-1 yields x = T^-10 = 0. Conversely, if x = 0, clearly Tx = 0.

(2) ⇒ (3). We want to show that Tx = Ty if and only if x = y. We get 0 = Tx - Ty = T(x - y), so x - y = 0 by hypothesis; implying x = y, as required. So T is injective.

(3) ⇒ (4). Let T₁, T₂, …, T_n ∈ Kⁿ be the columns of T and x₁, x₂, …, x_n ∈ K be scalars such that x₁T₁ + x₂T₂ + … + x_nT_n = 0. Then Tx = 0 where x ∈ Kⁿ is the vector with entries x₁, x₂, …, x_n, and we necessarily have x = 0 since T is an injection. So, x₁ = x₂ = … = x_n = 0, and therefore T₁, T₂, …, T_n are linearly independent.

(4) ⇒ (5). The columns of T are linearly independent, defining a linearly independent set of n vectors in Kⁿ — so, this set is maximally linearly independent, hence a basis for Kⁿ, and therefore generates the space.

(5) ⇒ (6). Since there are n columns of T, they are linearly independent and hence a basis for Kⁿ. Therefore the range of T is Kⁿ and any y ∈ Kⁿ can be written as a unique linear combination of the columns of T. Since Tx represents a linear combination of the columns of T, we can find x ∈ Kⁿ such that y = Tx.

(6) ⇒ (7). We will try to find an eigenvector x ∈ Kⁿ for T with eigenvalue 0; i.e. a nonzero x ∈ Kⁿ such that Tx = 0x = 0. T0 = 0 so we can take x = 0. But then x must be unique, by hypothesis; thus there is no nonzero x such that Tx = 0. Therefore 0 cannot be an eigenvalue for T.

(7) ⇒ (8). A number is an eigenvalue for T if and only if it is a root of the characteristic polynomial for T. Since 0 is not an eigenvalue for T, det(T - xI) = 0 does not have x = 0 as a solution, i.e. det(T - 0I) = det T ≠ 0. Conversely, det T = 0, then 0 is a root of the characteristic polynomial for T and hence an eigenvalue of T.

(8) ⇒ (1). Let T_ij, denote the ij-th cofactor of T, and let U be the n-by-n matrix whose ijth entry is T_ji/(det T). This is defined since det T is nonzero. It can be (painfully) checked that TU = UT = I. □

I admit the last bit was very hand-wavy, but good lord the proof of that would be indexing hell. But I hope that this can be a decent collection of useful equivalences that may or may not come up in a class for which linear algebra is a prerequisite.

supergreat:

now I can die with my mind at peace  画

The mystery is solved