In finite group theory, there is an interesting fact due to Brauer. First of all, some notations. We denote the symmetry group acting on numbers . For any field , there is a natural action of on the vector space , that is, the action on the canonical base is just as follows: the element takes to the base . Extended to the whole vector space, we denote the matrix obtained as . It is easy to verify that is a representation of . It is clear that if are conjugate in , then are also conjugate. Amazingly, the converse is true, that is
are conjugate if and only if are conjugate as matrices.
One common way to show if two matrices are conjugate or not is to use the Jordan standard forms, or the similarity invariants. But here the problem is that two conjugate permutation matrices don’t necessarily have another permutation matrix as their conjugate. So the solution should study these permutation matrices to get some information about the permutation itself. On the other hand, how can we decide if two permutations are conjugate? There is one simple criterion, that is write them in the form of disjoint cycles and see if every possible length of cycles appear the same number of times. That is, if the cycle representation of has length data as , the there is , then we have to examine if these two set of numbers are the same after possibly a permutation. But obviously, we can not get directly from these informations. But look at . If they are conjugate, what are the possible invariants? Now consider a simple case where . So what can we say about ? Since has order , so is . So . So this inspires us to consider the eigenvalues and eigenvectors of . It has one eigenvector(up to a multiplication of a non-zero scalar) with eigenvalue . So we have . Clearly for any other matrix conjugate to , this quantity must also be . Can we generalize this to general situations? The answer is yes. Suppose that , then we still have that . But if where are two cycles disjoint, then a simple speculation give that . So we can generalize this to other situation: if has disjoint cycles, then . So, we at last get some information on . Through , we know at least that the cycle representation of has how many disjoint cycles. Then, since are conjugate, so are alll their powers. Perhaps their powers can also give us some more information.
But before that, let’s see what happens when takes powers. Still start from the simplest case, . Then what are ? Another simple speculation will show that for , it will have cycles disjoint, with each cycle of length . We have said that two cycles are conjugate if and only if their length are the same. But recalling what we have done above(we get some information on the number of cycles of an element), we tend to think if we can use another way to characterize an integer ? There are many, but one suits here, that is all its factors. That is to say, if we know two sets of factors of two integers are the same, then we are sure that these two integers are identical. So for . The sequence gives all the possible positive factors of , thus determines , and also determines up to conjugacy. Now what about the general situation? That is to say, suppose that where is a cycle of length unknown for the present and these cycles are disjoint and even the number of cycles is unknown, too. Now we calculate , which gives us the number of cycles in , that is . Then we can calculate , this gives us . Continue in this way, we obtain a sequence . So can we recover those with the help of these ? We can write this in the form of a matrix. We define where each entry is . And there is a column vector such that . The problem is then to show that this matrix is invertible. If it is indeed the case, then we can recover , so this means that determines (note counts the number of equal to , which is enough to determine up to conjugacy). In fact, this is a theorem due to Smith(1876), that is
The matrix is invertible.
There is a proof which uses an ingenious idea of decomposing into the product of two upper triangular matrices. In fact, if we note the Euler function which counts the number of integers which is prime to . There is a nice formula concerning this function, that is
One way to see this is to consider these rationals . Write each of these rationals in the reduced form, for each , all the rationals in with denominator must have a nominator prime to , and if is a positive integer smaller than but is prime to , then surely will appear in . So the number of rationals in with denominator is then , which gives that .
So for each entry , the last identity is a very important observation, which enables us to rewrite as where and if we define , otherwise . And we define . So we get . So in fact, is a product of two matrices, that is with . Note that these two matrices are in fact triangular. In deed, for , if , then . But since , we can not have , so we must have that . Similarly for , if , we have that . So we have that , thus is invertible.
So in this way, we proved the theorem of Smith and also the result due to Brauer.
This is really an interesting result. This result shows that for those permutation matrices, the conjugacy will automatically mean the conjugacy in the group theoretic sense.
Concerning the theorem of Smith, there are various generalizations. In the proof, we have used the relation that divides , defining a partial order on . What we have really utilized is the Mobius function. Specifically, if is a partial order set with the order , then for any function , we define . how can we define a Mobius function on ? Or more fundamentally, can we define a Mobius function on ? Recall one property of the Mobius function on the positive integers: where if , and is otherwise. We can generalize this formula to the case . Using the function defined in the proof, if , and is otherwise, we can rewrite this formula as . Note that the function is in fact an unit in the set of real-valued functions on with the addition being the point-wise addition, and the multiplication being the convolution(more precisely, , . Here we can take ). To be compatible with the above definition of functions on , we define the two-variant Mobius function(using thesame notation), with if is an integer and is otherwise. So the above identity can be written as . So, in this way, the Mobius function being a unit is more obvious. So, we want to generalize this definition to other partial order sets. The function is easy to define, while the function (note that it is a unit in the point-wise multiplication), it is not hard to generalize, either. For a partial order set(poset, for short), we define with if , and is otherwise. So, we can define the Mobius function on to be the inverse of the (point-wise multiplicative unit) , that is to say .
Having thus defined the Mobius function, next perhaps we should consider the Mobius inversion formula, that is,
(Mobius Inversion Formula) if two functions on such that , then we have that .
In fact, we don’t need the condition in the summation since is a function on , its definition requires that if . The proof of this formula is very simple, just using the convolution once we have noticed that . And thus we omit it.
For references on the Mobius functions on a poset, we can read this