The Frobenius-Cauchy lemma

Let V and W be sets, and S a subset of the Cartesian product $V\times W.$ If

$(v,.)=\{w\in W:(v,w)\in S\},$ and $(.,w)=\{v\in V:(v,w)\in S\},$

then it is self evident that

$$\sum_{u\in V}\vert (v,.)\vert =\vert S\vert =\sum_{w\in W} \vert (.,w)\vert .$$

[Indeed, we are merely expressing the cardinality of S in two different ways. First by fixing the first coordinate and summing over the second, then by initially fixing the second and summing over the first.] We call this two way counting.

Often the region S is rectangular, in which case we have $\vert (v,.)\vert =r,$ for all $v\in V,$ and $\vert (.,w)\vert =s,$ for all $w\in W.$ Then $\vert V\vert r=\vert S\vert =s\vert W\vert .$

Let the group G act on a set S. Denote by $F(g)=\{x\in S :g(x)=x\}$ the set of points in S fixed by the group element g. Denote by t the number of orbits of G on S.

The Frobenius-Cauchy Lemma The number of orbits of G on S is equal to the average number of points left fixed by the elements of G.

[In symbols, $t={1\over {\vert G\vert}}\sum_{g\in G}\vert F( g)\vert .]$

Proof: We count in two ways the cardinality of the set of pairs $B=\{(g,x):g(x)=x\},$ with g in G and x in S. Observe that in this case (g,.) is simply F(g), and (.,x) is G_x, the stabilizer of x in G. Therefore,

$\sum_{g\in G}\vert F(g)\vert =\vert B\vert =\sum_{ x\in S}\vert G_x\vert =\{$upon sorting by orbits $\}$

$=\vert G_{x_1}\vert\vert Gx_1\vert +\vert G_{x_ 2}\vert\vert Gx_2\vert +\cdots +\vert G_{x_t}\vert\vert Gx_t \vert =t\vert G\vert .$

Here the x_i's are representatives from distinct orbits. This ends the proof.

Theorem (Cayley)

Every group can be faithfully represented as a regular permutation group.

Proof: Let $G=\{1,g_2,\ldots ,g_n\}.$ Consider the square array of n² letters (elements of G) formed as follows:

1 g₂ g₃ g₄ $\ldots$ g_n

g₂ g₂² g₃g₂ g₄g₂ $\ldots$ g_ng₂

$\cdots$

g_n g₂g_n g₃g_n g₄g_n $\ldots$ g_n²

If we consider the permuatations by way of which each row in this array is obtained from the first, we obtain a permuatation group on n letters. Each permutation besides the identity involves all of the n letters (i. e., it has no fixed points). The representation is faithful since no two of the resulting permutations are the same. Furthermore, each letter of G is replaced once and only once by every other letter. The resulting permutation group is transitive and regular. End of proof.

In a similar manner one can act with the group G, by multiplication on the left, on the left cosets of a subgroup H of G. Let the set of cosets be $S=\{g_1H,g_2H,\ldots ,g_mH\},$ where where g₁=1 and $m=\vert G:H\vert .$ An element $g\in G$ is represented as $(gg_1H,gg_2H,\ldots ,gg_mH).$ The kernel of this representation consists of $g\in G$ such that gg_iH=g_iH, for all i. In particular gg₁H=g₁H, or gH=H, which shows that the kernel is in H. Generally such a representation is not faithful. It becomes faithful, however, if the only normal subgroup of G contained in H is 1, since in that case the kernel of the representation must necessarily be 1.