Tricki
a repository of mathematical know-how

Prove the result for a representative of each equivalence class

Quick description

Sometimes one can prove a result for every element of a set with an equivalence relation on it by proving the result for a representative of each equivalence class and proving that if the result is true for some element then it is true for all elements that are equivalent to that element.

Prerequisites

Basic algebraic concepts, the notion of an equivalence relation. Other prerequisites vary from example to example.

Example 1: Jordan normal form

Two n\times n matrices A and B are similar if there is an invertible matrix P such that PAP^{-1}=B. A slightly strange result is that every n\times n matrix is similar to its transpose. It is strange because it is hard to interpret as a statement about linear maps. Given that it is true, it is also surprisingly hard to prove.

However, we can get a handle on the problem by observing that if A is similar to B and the result is true for A, then the result is true for B. Indeed, B is similar to A, which is similar to A^T, which is similar to B^T.

The relationship of similarity is an equivalence relation, so once we have made this observation, all we have to do is prove the result for one element of each equivalence class. A good idea under such circumstances is to try to find the "nicest" or "simplest" representative of each equivalence class.

This job is done for us by the Jordan normal form theorem, which says, as its name suggests, that every matrix is similar to a matrix in Jordan normal form. It is straightforward to prove the result for a Jordan block – take P to be the matrix that reverses the order of the basis elements (that is, the matrix with 1s on the "wrong" diagonal and zeros everywhere else) – and from that one can get the result for an arbitrary matrix in Jordan normal form. Therefore the result is proved.

Note iconContributions wanted This article could use additional contributions. This article could do with some more examples.

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications