Tutorials, Hilary term, week 2

Here are some remarks on problem 7 (i) of Linear Algebra II, sheet 1. Let me know if you have a simpler proof.

————————————

Here are some further remarks. Recall that the key statement is this:

For \rho \in Sym(n), if

\rho=\tau_1\tau_2\cdots \tau_m,

then

m\geq n-c(\rho).

It is perhaps better to write it in the form

c(\rho)\geq n-m.

This is giving a lower bound for the number c(\rho) of cycles in \rho, saying that if m is small, then c(\rho) has to be big. I hope this makes intuitive sense: with just a few transpositions, you can’t create long cycles. Hence, there has to be many of them.

Note also that the strategy of proof (I learned from Matei’s answer) changes the perspective of the problem in a nice way. Instead of trying to prove a lower bound for the number of transpositions given a cycle decomposition, one tries to prove a lower bound for the number of cycles, given an expression in terms of transpositions. Possibly, this is easier because the cycle decomposition is essentially unique.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: