Today's random subject is the skew-symmetric matrix. It is a matrix satisfying (of course, for the dimensions to match has to be square.) In words, each entry in the matrix is the negative of the one symmetrically positioned with respect to the main diagonal.

A particular point of interest is that, since entries on the main diagonal are their own symmetric opposites, the main diagonal must be all entries.

For example:



And there are lots of interesting things about this type of matrix, I think, but today we're going to look at their determinant.

Okay, I give up trying to present this stuff in a manner that suggests one could have just come up with it magically. Odd-order determinants of skew-symmetric matrices are zero. This is easy from naively plugging in the definition: where is the order of , because if you multiply all entries of a row by a constant, the determinant gets multiplied by that constant too. And therefore, if is odd we're done! . That was easy, but not really interesting.

The interesting thing happens for even , when it turns out the determinant will be the square of a polynomial in the matrix entries. This polynomial is called the Pfaffian. (Actually, this can't be a satisfactory definition in my opinion because there's a remaining sign ambiguity, but that is also not a very interesting issue. Also, don't ask me how to pronounce that thing.)

So, to get somewhere --- anywhere --- from just the determinant, let's write out all the terms with the Leibniz formula. Why not?



And now we look for terms to cancel. We hope that the skew-symmetry will create a lot of terms in this formula that are opposites of each other and sum to .

First: obviously, we can get rid of all the terms whose permutation contains any fixed point, since the diagonal entries are all zero.

Next: let's look at what we can do to permutations to find some that cancel.

Of course, if we want two permutations and to cancel out, they have to contain the same variables. Here we're saying that and are the same variable, in a sense. They depend on each other; one can be treated as free while the other is its dependent negative. Actually, since we'll be dealing a lot with signs here, let's just arbitrarily fix to be positive and to be negative. So, to try to cancel out the term of the permutation , which contains entries like , we want terms with some entries like .

What if we inverted the permutation? That way, we'd have one term with and one with . Well, the two terms' permutations would have the same sign, and each of the variables would be negated... so since is even, the two terms are really the same. Darn. But actually, this method is not entirely fruitless. We don't need to invert the entire permutation ; we can try inverting one cycle to get . Since the number of cycles doesn't change, the two permutations will have the same sign. However, if the inverted cycle has length , each of terms will be negated. Thus, if we invert an odd-length cycle of a permutation, we get a permutation whose term cancels out with the original one!

So, by arbitrarily picking a canonical way to select an odd-length cycle from each permutation that has one (e.g. the odd-length cycle containing the smallest number among all numbers in odd-length cycles), and inverting it, we can pair up all permutations that contain at least one odd-length non-singleton cycle, canceling out their terms. Permutations with singleton cycles can't all be paired in this manner, but as we know, their terms are zero anyway.

Okay, what's left? We have all the permutations consisting only of even-length cycles. No matter how we might invert the cycles in them, the signs of the permutations won't change and the negations will cancel out completely.

Well, we're looking to factor the terms into two parts. One reasonably symmetric way that jumps to mind is to take every other term in each cycles. Example: in the cycle , i.e. the cycle is , we take every other arrow and we color them for the lulz:



separating the terms into and . What works great here is that each part will have entries, each of which has two indices. This is indices, and each of the possibilities appears once. Thus, the terms in each part should correspond to a pairing up of the indices.

There's going to be a lot of weird stuff about these pairings below, so let's give them a name. Wikipedia tries to refer to them as partitions, which are of the into pairs, but the partition doesn't seem as important as the pairing-ness. Well. There's a quick, stupid way to compromise; let's call them PAIRtitions. That name sucks, but I need to choose something really painstakingly clear or things will get worse and I swear by the end of this random sequence of derivations nobody on the planet will have any idea which self-invented term that was meant to refer to. Actually even with this name I think it'll happen to some degree. Blah blah blah.

For example: and are PAIRtitions that combine to form the cycle . The mappings to , to , and to are produced from the first pairing. The mappings to , to , and to are produced from the second pairing. Note that, in general, we won't know in which direction each of the pairs will appear in the final permutation from one of the pairings alone.

First we need to make sure that the number of times each possible term appears is the same.

A particular set of variables in the determinant can be specified as a bunch of even cycles. However, since we're deliberately conflating entries with swapped indices as negatives of each other, each of the cycles with length at least 4 can be inverted without changing the set of variables, so each set of cycles appears in permutations, producing a term with multiplicity , where is the number of cycles with length at least 4. Note that inverting a length-2 cycle, or a transposition, doesn't produce a different cycle.

Meanwhile, each cycle can be partitioned into two sets of pairs ("subPAIRtitions"), and these groups are identical only for length-2 cycles. Thus, for each cycle of length at least 4, there are two ways to assign one of the subPAIRtitions to each factor, while for cycles of length 2 there is only one. Thus the multiplicity should also be where is the number of cycles of length at least 4.

Good, the magnitudes of the coefficients match if the Pfaffian contains one term for each PAIRtition. Unfortunately, every coefficient also contains a sign, and this is only if every single sign of every term matches up, and signs are very annoying to deal with. So now we hope to come up with a method of assigning signs to every PAIRtition so that the terms form the right sign every time. Is my math subconscious starting to deliver assonance now?

First, a sanity check. If we have the same PAIRtition on both sides, will the term be positive? If this is the case, the permutation will consist of transpositions, and thus the parity of the permutation will be that of . But each cycle consists of two entries that are negatives of each other, so the sign will be further multiplied by , canceling the permutation sign out. Excellent.

Now, remember that we're working with the definition of the Pfaffian as a square root of sorts, so there will be a final sign ambiguity; we can't directly determine whether any particular pairing should have a positive or negative sign. What we can do is figure out whether two pairings have the same or opposite sign. We do this by comparing very similar pairings.

For example, suppose we compare the signs of two pairings that are identical except for two particular pairs, involving the indices . Then the two pairs will definitely form a 4-cycle, and everything else forms parity-effectless 2-cycles.

Remember that, to have a reference point for each variable, we decided we would consider to be "positive" iff . This corresponds to the cycle/permutation having such that , which is called an "excedance" when one wants to sound smart or wants to use slightly less wordy ways of saying things. Well, we should be counting the negative variables, but since there are obviously the same parity of both since there are an even number of variables and I couldn't find a fancy term for them, I stuck with these. (edit: Google suggests "anti-excedance". lame.)

Then we see that there is one negative variable in the cycle , so its product is "negative", while there are two negative variables in and in so they are "positive". So, we can use them to compare the signs of two pairings that are the same except for the pairs including . Note that when we compare them, their collectively formed permutation is a single even-length cycle, which is odd as a permutation, hence their sign difference should be the negatives of the cycle variables. So the pairings and are the same sign, and the sign of is the opposite.

Now we might decide to define the sign of a pairing to be the parity of that pairing's numbers of "clasps" (I've run out of cool names but this can't be ambiguous or distracting, I hope), or number of pairs of pairs that interlock the way do.

So: to prove that the weird stuff we did above will create a Pfaffian whose square is indeed the determinant of the skew-symmetric matrix, we should prove that:

If a permutation consists of only even-length cycles, and its mapping relations are cut into two sets of disjoint pairings, then the sum of the permutation's number of inversions (this gives the permutation's original parity), the permutation's number of excedances, and the number of clasps entirely within each pairing is even.

I should probably express some open-ness or hope here that coming up with something like this isn't the "right" or "natural" way to deal with things in linear algebra here. Oh well, I already put so much time into typing this it'd be dumber to never post. So we keep on going...

First, let's examine the clasps again from one pair 's perspective. This pair forms a clasp with every pair that has exactly one of its endpoints inside , but since we're really looking at the parities, it wouldn't hurt to just count both endpoints of the pairs entirely inside , or thus every element that's in that range. This means, if we want to get a parity count of the number of clasps that is in, we can just count how many numbers there are between and exclusive. (This is NOT justification for us to count the clasps by summing this over all pairs, since that would count each clasp twice and completely miss the point.)

Now, we compare the clasps in several parts. In part one, let's compare the clasps that involve pairs from distinct cycles; we claim the parity of these are even because they're equal between the two PAIRtitions. To prove this, it suffices to prove it for two fixed cycles. As above, we observe that the parity of the number of such clasps formed by a pair in the red cycle is equal to the number of elements of the blue cycle that are in it. Hence, the parity of the number of times each blue element is counted is equal to the parity of number of times it's contained in a red cycle, which is equal to the parity of number of red points on either side. The sum of these parities is obviously the same in both PAIRtitions, so these parities cancel out in the sum.

Look, I give up trying to explain this in words, so have the crappiest combinatorical example diagram ever:



We want to know that the parity of times a top red path and top blue path cross (3) or a botttom red and bottom blue path cross (1) sum to an even number (4).

The blue numbers, in order 3, 7, 9, and 10, have 2, 5, 6, and 6 red numbers to their respestive lefts. These numbers are the same for eithehr pairing, and the parities of the clasps are equal to their sums, so the number of clasps cancels out.

In part two, we compare clasps involving pairs in a single cycle. We'll start dealing with the red cycle as an example. The parities we want it to contribute are as follows:

1 (for the cycle's parity, since even cycles have an odd number of inversions and are odd permutations) + (# of excedances) + (top clasps) + (bottom clasps) = even.

Well, actually this can be observed by starting at the lowest red index (1), moving along the cycle, and keeping track of how many previously-visited red numbers are to your left. Each encountered excedance leaves the number you left to the left (!), and each non-excedance doesn't, which is a +1; otherwise, numbers change sides for every "later" pair clasped with an "earlier" one, matching the clasps' parity as in our shifted-perspective counting, yielding an additional +1. When we return to the lowest red index, we have our starting index as a red number to our left (it was put there after an excedance and didn't switch sides in any pseudoclasping event) and nothing else, which is a parity change from the start, and the equation is proved!

Combining everything above and the fact that I'm just now really lazy, we're done! The Pfaffian consists of a term for every PAIRtition of the positive integers , consisting of the variables with those pairs as indices multiplied together, multiplied by if the PAIRtition contains an odd number of clasps.