Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A Cayley table of an finite group has to have every element exactly once in every row and exactly once in every column.

Proof that every element of a group has to be at most once in every row and at most once in every column:

Let $(G, \circ)$ be a group and $a, b, c, d \in G$ with:

(I) $a \circ b = d$

(II) $a \circ c = d \Leftrightarrow a = d \circ c^{-1}$

Then:

$\begin{align} (a \circ c) \circ (a \circ b) &= d \circ d \\ \Leftrightarrow d \circ (d \circ c^{-1} \circ b) &= d \circ d \\ \Leftrightarrow d \circ c^{-1} \circ b &= d\\ \Leftrightarrow c^{-1} \circ b &= e\\ \Leftrightarrow b &= c \end{align}$

As the group is finite, this also means it is exactly once in every row/column ($\forall a,b \in G: a \circ b = x$ with $x \in G$).

Now my question is:

Does a group with an infinite number of elements exist, that has not every element in every row/colum of its cayley chart?

(I know that cayley charts usually get used only for finite groups. But if set of the group has a countable number of elements, you can imagine an cayley table. For example, $(\mathbb{Z}, +)$ has obviously every element in every row/column).

share|improve this question
    
Cayley tables are only for finite groups as far as I know –  Belgi Aug 29 '12 at 18:42
    
@Belgi: If you read my post, you would have noticed that I knew this. (Read the last paragraph of my question.) –  moose Aug 29 '12 at 19:36

2 Answers 2

up vote 7 down vote accepted

The term Cayley table is generally restricted to finite groups. However, it’s certainly possible to generalize the idea. For a group $G$ and an element $a\in G$, the $a$ ‘row’ of the table is essentially just the function $$f_a:G\to G:b\mapsto ab\;,$$ and the $a$ ‘column’ is essentially just the function $$f^a:G\to G:b\mapsto ba\;.$$ If $G$ is countably infinite, you can visualize the Cayley table as an infinite matrix.

Let $G$ be any group, and fix $a\in G$. For each $b\in G$ you have $b=a(a^{-1}b)$, so $b$ appears in row $a$ in column $a^{-1}b$. Similarly, $b=(ba^{-1})a$, so $b$ appears in column $a$ in row $ba^{-1}$. It follows that $b$ appears in every row and column. The cardinality of the group doesn’t matter.

Added: You didn’t ask, but it’s also clear that each element of $G$ appears only once in each row and column: if $ax=ay$ or $xa=ya$, then $x=y$. Thus, each of the maps $f_a$ and $f^a$ for $a\in G$ is a bijection from $G$ onto itself, i.e., a permutation of $G$. The set of all permutations of $G$ is denoted by $\operatorname{Sym}(G)$ and is a group under composition of functions; the maps

$$G\to\operatorname{Sym}(G):a\mapsto f_a$$

and

$$G\to\operatorname{Sym}(G):a\mapsto f^a$$

are isomorphisms of $G$ to subgroups of $\operatorname{Sym}(G)$. This is Cayley’s theorem.

share|improve this answer
1  
In other words, the generalization is that $f_a$ and $f^a$ are permutations of $G$. –  lhf Aug 29 '12 at 18:53
    
@lhf: Exactly so. –  Brian M. Scott Aug 29 '12 at 18:57

In the general setting, having at least one element in every row and column just means that given any $g$ and any $a$, there exists a $b$ and $b'$ such that $ab = g$ and $b'a = g$. This is true because you can let $b = a^{-1}g$ and $b' = ga^{-1}$.

Having exactly one element in each row or column is equivalent to $ac = g$ and $ac' = g$ implying that $c = c'$. This is because $ac = g = ac'$. Multiplying $a^{-1}$ to both side gives $c = c'$. Do the same thing for $ca = g$ and $c'a = g$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.