Why are the characters of the symmetric group integer-valued?

I remember one of my professors mentioning this fact during a class I took a while back, but when I searched my notes (and my textbook) I couldn't find any mention of it, let alone the proof.

My best guess is that it has something to do with Galois theory, since it's enough to prove that the characters are rational - maybe we have to find some way to have the symmetric group act on the Galois group of a representation or something. It would be nice if an idea along these lines worked, because then we could probably generalize to draw conclusions about the field generated by the characters of any group. Is this the case?

-
What exactly do you mean by "the characters of the symmetric group are integers"? They're functions on the conjugacy classes to $\mathbb{C}$. They're even indexed by partitions of integers (Well, irreducible ones are) but I'm not seeing right off in what way they can be called integers. – Charles Siegel Jan 3 2010 at 23:49
I meant that their values are integers. – zeb Jan 3 2010 at 23:53
You should have said "Z-valued" or "integer-valued" instead of "integers". – Chandan Singh Dalawat Jan 4 2010 at 6:46

If $g$ is an element of order $m$ in a group $G$, and $V$ a complex representation of $G$, then $\chi_V(g)$ lies in $F=\mathbb{Q}(\zeta_m)$. Since the Galois group of $F/\mathbb{Q}$ is $(\mathbb{Z}/m)^\times$, for any $k$ relatively prime to $m$ the elements $\chi_V(g)$ and $\chi_V(g^k)$ differ by the action of the appropriate element of the Galois group.

If $G$ is a symmetric group and $g$ an element as above, then $g$ and $g^k$ are conjugate: they have the same cycle decomposition. So $\chi_V(g)=\chi_V(g^k)$ whenever $(k,m)=1$, and thus $\chi_V(g)\in \mathbb{Q}$.

-
Simpler then I expected. I guess the general fact for arbitrary groups is that if $g^k$ is conjugate to $g$, then $\chi(g)$ is in the fixed field of $\zeta \rightarrow \zeta^k$. – zeb Jan 4 2010 at 0:42

I just want to emphasize that this question points at the rationality theory of representations and characters that is exposed so beautifully in Chapters 12 and 13 of Serre's book Linear Representations of Finite Groups.

In particular, one has the following facts.

[Section 13.1, Corollary 1]: The following are equivalent:
(i) Every character of $G$ is $\mathbb{Q}$-valued.
(ii) Every character of $G$ is $\mathbb{Z}$-valued.
(iii) Every conjugacy class of $G$ is rational: for every $g \in G$ and positive integer $k$ prime to the order of $g$, $g^k$ is conjugate to $g$.

As noted above, since raising an element of the symmetric group $S_n$ to a power prime to its order does not change the cycle decomposition, condition (iii) holds and the implication (iii) $\implies$ (ii) answers the question. [The proof is the basic Galois-theoretic argument given in some other answers. The implication (ii) $\implies$ (iii) is deeper in that it uses the irreduciblity of the cyclotomic polynomials.]

Some others have said that the shortest or simplest proof arises from knowing that all of the irreducible representations of $S_n$ can be explicitly constructed and therefore seen to be realizable over $\mathbb{Q}$. I respectfully disagree. This is a nontrivial theorem of Young which Serre refers to but does not prove in his book (Example 1, p. 103).

Moreover, Serre explains that the condition of rationality of characters is in general weaker than rationality of representations: there are obstructions here in the Brauer group of $\mathbb{Q}$! Namely, by Maschke's Theorem the group ring $\mathbb{Q}[G]$ is semisimple, say a product of simple $\mathbb{Q}$-algebras $A_i$ which are in bijective correspondence with the irreducible $\mathbb{Q}$-representations $V_i$. By Schur's Lemma, $D_i = End_G(V_i)$ is a division algebra, and one has $A_i \cong M_{n_i}(D_i)$. Then:

[Section 12.2, Corollary]: The following are equivalent:
(i) Each $D_i$ is commutative.
(ii) Every $\mathbb{C}$-representation of $G$ is rational over the abelian number field generated by its character values.

Thus just knowing that the character table is $\mathbb{Z}$-valued is not enough. The standard example [Exercise 12.3] is the quaternion group $G =$ {$\pm 1, \pm i, \pm j, \pm k$} for which

$\mathbb{Q}[G] \cong \mathbb{Q}^4 \oplus \mathbb{H}$,

where $\mathbb{H}$ is a division quaternion algebra over $\mathbb{Q}$, ramified at $2$ and $\infty$. It corresponds to an irreducible $2$-dimensional $\mathbb{C}$-representation with rational character but which cannot be realized over $\mathbb{Q}$.

-

The characters of any representation are always algebraic integers since they are sums of roots of unity. Over the symmetric group, every representation is defined over $\mathbb{Q}$, and the integers are integrally closed. Indeed, the irreducibles can be constructed by using Young projectors that use only rational numbers.

(Another way to see that every representation is defined over $\mathbb{Q}$ is that all conjugacy classes are rational; this is what Charles indicated in his answer.)

-

One way to prove that you get integers is to prove that the corresponding simple modules are defined over $\mathbb Z$ (this is of course much stronger than their having characters with values in $\mathbb Z$), and this is what you get by constructing them 'combinatorially'. This is done in G. D. James's book on the representation theory of symmetric groups, for example. There he even constructs actual matrices giving the action of elements of $S_n$ on the simple modules---the so called Young orthogonal form.

-
It has always seemed to be almost scary that we know so much of the symmetric groups that we can write down the representing matrices of its elements in all simple modules! – Mariano Suárez-Alvarez Jan 4 2010 at 0:02

The quickest answer is because all of the irreducible representations of the symmetric group can be constructed over the field of rational numbers. See the wikipedia article on Young symmetrizers for example http://en.wikipedia.org/wiki/Young_symmetrizer

More generally, one can say that representations of any finite Weyl group can be constructed over the rational numbers. This is explained in one of Springer's papers: http://www.ams.org/mathscinet-getitem?mr=491988

Another reason is that one write down an explicit combinatorial formula for the values of these characters. This is the Murnaghan-Nakayama rule and can be found in many sources. One such source is Stanley's Enumerative Combinatorics volume 2, Section 7.17, and Section 7.18 for its connection to the symmetric group.

-
This points to an unusual property of symmetric groups and other Weyl groups which is much stronger than the fact that their characters take values in $\mathbb{Z}$: the representing matrices can actually be written over $\mathbb{Q}$. Of course, the price of this stronger statement is doing more work than just showing that character values (always algebraic integers) are rational. – Jim Humphreys Nov 21 2010 at 18:13