Feeds:
Posts

## Non-canonical isomorphisms

I find non-canonical isomorphisms very interesting, but I wish I knew more examples. To be vague, an isomorphism (perhaps in a category) is said to be non-canonical if it requires making an “arbitrary choice.” One of the reasons I find them interesting is that we often think of objects only up to isomorphism, but in order for certain things to make more sense we must distinguish between objects that are non-canonically isomorphic. Here are the examples I know of.

Vector space duality

Finite-dimensional vector spaces are non-canonically isomorphic to their duals. This is one of the simplest examples to explain, but I think it is often ignored in elementary linear algebra courses. The dual $V^{*}$ of a vector space is the space of linear functionals $V \to \mathbb{K}$ to the base field, and of course by linearity a linear functional is uniquely determined by what it does to each element of a basis; in other words, $\dim V$ numbers. So all we have to do is pick a basis and we can write down the space of linear functionals, which looks just like the original space.

But this is just an illusion. Here’s the simplest way I can think of to clarify the difference: if vector spaces are column vectors, then their duals are row vectors.

Usually no distinction is made between row and column vectors because when we write vectors down numerically (which, you’ll note, also requires a choice of basis), taking transposes takes us from one to the other and they both look pretty much the same. But matrices (that is, linear transformations) don’t act the same on row and column vectors! A given square matrix acts on column vectors from the left and row vectors from the right, and these actions are different unless the matrix is symmetric. Of course, there’s also a transpose operation here, but what becomes very clear now is that the transpose operation is basis-dependent, so until we learn to talk about it in an abstract way we shouldn’t trust what it does numerically.

So here’s the abstract language: if we call column vectors “vectors,” then row vectors aren’t really vectors – they’re called covectors, which is another word for dual vectors. Covectors don’t behave the same as vectors because they transform covariantly under change of basis, whereas vectors transform contravariantly. This is a fancy way to distinguish the left and right action of matrices. This distinction is important in mathematical physics, but I don’t have the background to really discuss why in detail.

Here’s why I like covectors: they do a good job of motivating the dot product and the tensor product. There is a natural pairing $V \times V^{*} \to \mathbb{K}$ of vectors and covectors (it’s just evaluation) which is bilinear, and a dot product arises once you identify the dual space with the original space (non-canonically, of course). Generalizing instead of specifying, there is a universal way to talk about bilinear maps $V \times W \to \mathbb{K}$ called the tensor product (another thing often ignored in linear algebra courses), and combining it with duality allows us to think of certain constructions in various equivalent ways. For example, a linear operator $V \to V$ is uniquely specified by a list of vectors that we assign to each element of a basis. If we change basis, this list of vectors changes covariantly – so it’s really a list of covectors! More formally, the following is true.

Proposition: The space of linear maps $V \to V$ is canonically isomorphic to the tensor product $V \otimes V^{*}$.

This isomorphism is called canonical because, while it can be defined by an arbitrary choice of basis, the final isomorphism does not depend on the choice of basis. So now we can explain the transpose operation: to find a transpose, write a linear operator as an element of $V \otimes V^{*}$ after picking a basis, and then switch vectors and covectors.

I didn’t finally get around to learning all of this stuff until I read Linear Algebra via Exterior Products by Sergei Winitzki, which is freely available at the URL; you can find all the details of what I’ve been talking about there. I found it an extremely interesting supplement to what I already knew about linear algebra; in particular, it “explains” the determinant formula in a way that I haven’t seen a standard linear algebra text try to tackle (via, as the title suggests, the exterior product). Rota once wrote that Noether’s contributions to the study and development of abstract algebra is the reason we learn Galois theory instead of tensor algebra. I wonder if this is necessarily a good thing.

Permutations and total orders

On finite sets, permutations are non-canonically isomorphic to total orders. Now, I have to be somewhat careful what I mean when I say this: one way to make this precise is that they have the same generating function (there are $n!$ permutations and total orders on a set with $n$ elements), but as combinatorial species they are not related by a natural transformation.

So what’s the non-canonical isomorphism (that is, bijection)? Actually, there are quite a lot of them (which is sort of what “non-canonical” means in the first place!). For example, one representation of a permutation is its “word,” which is the sequence $\sigma(1) \sigma(2) ... \sigma(n)$ describing the image of each element of the underlying set. Reading the word from left to right gives you a total order on the set. Easy enough, right? But until we name the elements of the set, they are anonymous: labeling them $1, 2, ... n$ is the non-canonical choice being made. (In fact, it’s a non-canonical choice of total order!)

Another representation of a permutation is its cycle decomposition. There is a unique way to write down a cycle decomposition so that each cycle begins with the smallest element and the cycles themselves are ordered by their smallest elements (which, again, requires a non-canonical choice of total order), and reading a cycle decomposition as a word gives us another permutation, or another total order. Stanley calls this the “fundamental bijection.”

Stanley also discusses a fascinating q-analog of the connection between permutations and total orders relating complete flags in vector spaces over finite fields (the analog of total orders) to the corresponding linear groups (the analog of permutations) that I haven’t yet digested.

Torsors

Vector spaces are non-canonically isomorphic to their underlying affine spaces. Like the relationship to dual spaces, the distinction between affine and vector spaces is occasionally ignored, which only causes confusion. There is a very nice generalization of this relationship that goes by the name of a torsor associated to a group. A torsor for a group is a G-set where the action is both transitive and free, meaning for any two elements $x, y$ in the underlying set there is exactly one group element such that $gx = y$. Thus, while it is not possible to “add” elements of the set, one can “subtract” two set elements and get a group element, or “add” a group element and an element of the set to get a set. As Baez explains so well in the link above, this relationship shows up everywhere in physics, and the distinction between affine and vector spaces is just a special case. The non-canonical choice here is the choice of an identity or origin (in the affine case): if we fix some element $e$, then we can identify any other element of the set $x$ with the unique $g$ such that $ge = x$. But often we don’t want to make this non-canonical choice; as Baez notes, a simple example is the usual way we write down antiderivatives.

Sometimes vectors are defined in terms of affine spaces. Take the difference between two points and get a vector; add a point and a vector and get a point. Confusingly, people often write down both vectors and points using coordinates, but there are two non-canonical choices involved in writing down points as coordinates: you must choose both a basis and an origin.

Torsors are very cool. They even generalize the second example: the set of total orders on a set with $n$ elements is nothing other than an $S_n$-torsor. The choice of an “identity” total order (as we saw above) provides the non-canonical isomorphism. But if we use the torsor language, we don’t have to make any such choices; we don’t even have to name the elements of the set!

Generalizing

Is there a concept that generalizes both “torsority” and “duality”? What other non-canonical choices are common in mathematics?

For example, there is the notion of Hodge duality, which depends on a non-canonical choice of orientation and orthonormal basis, but in some sense Hodge duality is just a fancier vector space duality. Explicitly, given an orthonormal basis $e_1, ... e_n$ of a vector space $V$ the wedge product defines a bilinear pairing $\wedge^k V \times \wedge^{n-k} V \to \wedge^n V$, and since $\wedge^n V$ is one-dimensional (it is spanned by $e_1 \vee e_2 ... \vee e_n$), identifying it with $V$ (the simplest case of Hodge duality) gives the other cases of Hodge duality immediately. Hodge duality is fun because it explains two other mysteries of basic linear algebra: determinants and cross products (and the relationship between the two).

Perhaps a sufficiently general version of duality does the trick. Given a pairing $f : A \times B \to C$, one can either think of elements of $B$ as parameterizing functions $f_b : A \to C$ or think of elements of $A$ as parameterizing functions $f_a : B \to C$; these perspectives are “dual.” We get vector space duality by setting $A = V, B = V^{*}, C = \mathbb{K}$, with the pairing given by evaluation and “torsority” by setting $A = G, B = S, C = S$ with the pairing given by the group action. The non-canonicity arises by picking certain elements of $A, B$. But I can’t help but feel like there’s more to the picture, and I can’t currently think of any genuinely distinct examples.

### 10 Responses

1. Heh, I think I take back what I said — I think that map of Conway-Doyle is natural after all!

• Hi,

I am glad that you have read some of my book on “linear algebra via exterior products.” I just uploaded an updated version to my web site. There are many changes as well as corrections of some errors, of course. Would you be interested in writing a review for the book’s present form?

I indend to keep this book in its present form as well as any future revisions freely available, so any comments or corrections are welcome.

Sergei Winitzki

• Thanks for the update! Unfortunately, I am both too busy and insufficiently qualified to write a review at the moment.

2. Funny, I hadn’t even tried to formalize precisely what I meant until you asked now. I was only thinking that at some if-then-else juncture, at least one slightly artificial choice must be made to effect the construction. (Yes, I have looked a little at Doyle’s write-up of their joint work; I seem to recall Conway wouldn’t add his name to that write-up because he said it was “too full of fluff” or something.)

But let me think out loud here by contrasting it with another example. There is a perfectly canonical bijective proof that x + z = y + z implies x = y (all sets finite), where given a bijection x + z –> y + z, outputs in z are fed back in as inputs and by iterating the feedback, one can produce a bijection x –> y. This can be formalized via a general notion of traced monoidal category: there is a tracing operation on the category of finite sets and bijections (with monoidal product +) which produces a map

hom(x + z, y + z) –> hom(x, y)

which is natural in x, y and dinatural in z, and satisfying various coherence conditions with respect to the symmetric monoidal structure.

Anyway, an initial stab at formalizing the non-canonicity of division by 2, say, is that I’m guessing that the Conway-Doyle prescription doesn’t give a map

hom(x + x, y + y) –> hom(x, y)

which is natural in the arguments x, y, and I’m also speculating there isn’t any such natural map. But I haven’t thought hard about this.

3. I am going through a few of your posts, Qiaochu, and I’m finding them rather interesting.

Speaking of non-canonical choices, I haven’t yet seen a bijective proof of “(2x = 2y) implies (x = y)” or “(3x = 3y) implies (x = y)” that seems fully canonical. I’m guessing there isn’t any.

• Thanks!

I can’t tell from that remark whether you’ve read Conway and Doyle’s paper on the subject. If you have, then is the problem that the standard argument doesn’t produce a correspondence that is functorial? (Functoriality isn’t obvious to me either in the positive or the negative, so I’d love to hear your thoughts.)

4. […] II: Orbits, sta… on GILA I: Group actions and equ…GILA I: Group action… on Non-canonical isomorphism…Qiaochu Yuan on Young diagrams, q-analogues, a…fermatprime on Young diagrams, q-analogues, […]

5. […] be two elements in the same orbit, and let denote stabilizer subgroup. Show that is a torsor for , and vice versa. What is the non-canonical choice that determines an isomorphism? How is this […]

6. on June 2, 2009 at 2:01 pm | Reply Qiaochu Yuan

That’s a nice example. I think it fits into the torsor framework, i.e. $\pi_1(X, x_0)$ acts as a torsor for $\pi_1(X, x_1)$ and vice versa, with the choice of f being the choice of “identity,” but as I understand it the natural generalization is to consider the fundamental groupoid rather than the fundamental group, which is a much richer object, so perhaps groupoids are the right way to go.

7. First of all congratulations for your blog!It comes to my mind the following simple topological example of a non-canonical isomorphism.
Let $x_{0}$, $x_{1}$ be points of a topological space $X$, and suppose there is a path $f : \textbf{I} \to X$ with endpoints $x_{0}, x_{1}$. It is easy to verify that $u_{f} : \pi_{1}(X, x_{0}) \to \pi_{1}(X, x_{1})$, defined by $u_{f}([\alpha]) = [\bar{f}*\alpha*f]$, is an isomorphism between the fundamental groups of $X$ at points $x_{0}$ and $x_{1}$.
Clearly this map can’t hope to be canonical in general, but it is iff $\pi_{1}(X, x_{0})$ is abelian.