description/proof of that Latin square with each row regarded as permutation forms group iff composition of 2 rows is row, and group's multiplications table is generated by certain way from square
Topics
About: group
The table of contents of this article
- Starting Context
- Target Context
- Orientation
- Main Body
- 1: Structured Description
- 2: Natural Language Description
- 3: Proof
- 4: Note
Starting Context
- The reader knows a definition of Latin square of finite set.
- The reader knows a definition of group.
Target Context
- The reader will have a description and a proof of the proposition that any Latin square with each row regarded as the permutation forms a group if and only if the composition of each 2 rows is a row, and the group's multiplications table is generated in a certain way from the square.
Orientation
There is a list of definitions discussed so far in this site.
There is a list of propositions discussed so far in this site.
Main Body
1: Structured Description
Here is the rules of Structured Description.
Entities:
\(S\): \(= \{a_1, ..., a_n\}\), where \(a_j\) is any distinct object
\(M\): \(\in \{\text{ the Latin squares of } S\}\), with each row, \(M_j\), regarded as the permutation of \((a_1, ..., a_n)\)
//
Statements:
(
\(\forall j, k \in \{1, ..., n\} (\exists l \in \{1, ..., n\} (M_k \circ M_j = M_l))\)
\(\iff\)
\(\{M_1, ..., M_n\} \in \{\text{ the groups }\}\)
)
\(\land\)
(
\(\forall j, k \in \{1, ..., n\} (\exists l \in \{1, ..., n\} (M_k \circ M_j = M_l))\)
\(\implies\)
(
its multiplications table, \(M'\), is generated from \(M\) as this:
1) if and only if the 1st column of \(M_j\) is \(a_k\), \(M_j\) is denoted as \(M'_k\): after all, \(\{M_1, ..., M_n\} = \{M'_1, ..., M'_n\}\) in some possibly different orders
2) each \(a_j\) in \(M\) is replaced by \(M'_j\)
3) the column labels are \((M'_1, ..., M'_n)\)
4) the row labels are the 1st column of \(M'\)
)
)
//
For example, for \(M = \begin{pmatrix} a_2 & a_3 & a_1 \\ a_1 & a_2 & a_3 \\ a_3 & a_1 & a_2 \end{pmatrix}\), \(M' = \begin{array} {l|lll} & M'_1 & M'_2 & M'_3 \\ \hline M'_2 & M'_2 & M'_3 & M'_1 \\ M'_1 & M'_1 & M'_2 & M'_3 \\ M'_3 & M'_3 & M'_1 & M'_2 \end{array}\); of course, the rows can be reordered such that \(M' = \begin{array} {l|lll} & M'_1 & M'_2 & M'_3 \\ \hline M'_1 & M'_1 & M'_2 & M'_3 \\ M'_2 & M'_2 & M'_3 & M'_1 \\ M'_3 & M'_3 & M'_1 & M'_2 \end{array}\).
2: Natural Language Description
For any finite set of distinct objects, \(S := \{a_1, ..., a_n\}\), and any Latin square of \(S\), \(M\), with each row, \(M_j\), regarded as the permutation of \((a_1, ..., a_n)\), if and only if \(\forall j, k \in \{1, ..., n\} (\exists l \in \{1, ..., n\} (M_k \circ M_j = M_l))\), \(\{M_1, ..., M_n\}\) is a group, and its multiplications table, \(M'\), is generated from \(M\) as this: 1) if and only if the 1st column of \(M_j\) is \(a_k\), \(M_j\) is denoted as \(M'_k\): after all, \(\{M_1, ..., M_n\} = \{M'_1, ..., M'_n\}\) in some possibly different orders; 2) each \(a_j\) in \(M\) is replaced by \(M'_j\); 3) the column labels are \((M'_1, ..., M'_n)\); 4) the row labels are the 1st column of \(M'\).
3: Proof
Whole Strategy: Step 1: suppose that \(\forall j, k \in \{1, ..., n\} (\exists l \in \{1, ..., n\} (M_k \circ M_j = M_l))\); Step 2: see that there is an identity permutation in \(\{M_1, ..., M_n\}\); Step 3: see that for each \(M_j\), there is an inverse permutation in \(\{M_1, ..., M_n\}\); Step 4: conclude that \(\{M_1, ..., M_n\}\) is a group; Step 5: suppose that \(\{M_1, ..., M_n\}\) is a group; Step 6: conclude that \(\forall j, k \in \{1, ..., n\} (\exists l \in \{1, ..., n\} (M_k \circ M_j = M_l))\); Step 7: see that \(M'\) generated in the way is indeed the multiplications table of the group.
Step 1:
Let us suppose that \(\forall j, k \in \{1, ..., n\} (\exists l \in \{1, ..., n\} (M_k \circ M_j = M_l))\).
Note that compositions of permutations are associative, because any permutation is a map and compositions of maps are associative.
Step 2:
Let us see that there is an identity permutation in \(\{M_1, ..., M_n\}\).
\(\{M_1, ..., M_n\}\) are distinct permutations.
Let \(j \in \{1, ..., n\}\) be any. \(\{M_j \circ M_1, ..., M_j \circ M_n\}\) are distinct permutations, because if \(M_j \circ M_k = M_j \circ M_l\) for some \(k \neq l\), \({M_j}^{-1} \circ M_j \circ M_k = {M_j}^{-j} \circ M_j \circ M_l\) (although \({M_j}^{-1}\) has not been proved to be in \(\{M_1, ..., M_n\}\) yet, that does not prevent us from doing the operations), so, \(M_k = M_l\), a contradiction.
As \(M_j \circ M_k = M_l\), \((M_j \circ M_1, ..., M_j \circ M_n)\) is a permutation of \((M_1, ..., M_n)\). So, there is a \(k\) such that \(M_j \circ M_k = M_j\). Then, \({M_j}^{-1} \circ M_j \circ M_k = {M_j}^{-1} \circ M_j\), so, \(M_k = id\). So, \(M_k\) is an identity permutation.
Step 3:
Let us see that for each \(M_j\), there is an inverse permutation in \(\{M_1, ..., M_n\}\).
As \(\{M_j \circ M_1, ..., M_j \circ M_n\}\) is a permutation of \((M_1, ..., M_n)\) and there is \(id\) in \(\{M_1, ..., M_n\}\), there is a \(k \in \{1, ..., n\}\) such that \(M_j M_k = id\). Then, also \(M_k M_j = id\) is true, because for each \(a_m\), while \(M_k\) maps \(a_l\) to \(a_m\), \(M_j\) maps \(a_m\) to \(a_l\), and so, \(M_k M_j\) maps \(a_m\) to \(a_m\).
So, \(M_k\) is an inverse permutation of \(M_j\).
Step 4:
So, \(\{M_1, ..., M_n\}\) is closed under operations, the operations are associative, there is an identity element, and there is an inverse for each element, and so, \(\{M_1, ..., M_n\}\) is a group.
Step 5:
Let us suppose that \(\{M_1, ..., M_n\}\) is a group.
Step 6:
\(\forall j, k \in \{1, ..., n\} (\exists l \in \{1, ..., n\} (M_k \circ M_j = M_l))\) is guaranteed by the definition of group.
Step 7:
Let us see that \(M'\) is indeed the multiplications table.
\(\{M_1, ..., M_n\} = \{M'_1, ..., M'_n\}\) is true, because the 1st column of \(M\) is a permutation of \((a_1, ..., a_n)\).
For each \(j, k \in \{1, ..., n\}\), \(M'_k M'_j = M'_l\) means that \(M'_k M'_j\) maps \(a_1\) to \(a_l\), but \(M'_j\) maps \(a_1\) to \(a_j\), so, \(M'_k\) maps \(a_j\) to \(a_l\), which means that \(a_l = M_m^j\) where \(M'_k = M_m\). As \(M'_k\) corresponds to the \(m\)-th row of \(M'\) and \(M'_j\) corresponds to the \(j\)-th column of \(M'\), the \((m, j)\) component of \(M'\) needs to be \(M'_l\). So, replacing \(M_m^j = a_l\) with \(M'_l\) indeed generates the multiplications table of the group.
4: Note
As an immediate corollary, replacing the components of \(M'\) as \(M'_j \mapsto a_j\) generates a multiplications table to make \(\{a_1, ..., a_n\}\) a group, because that is just replacements of symbols, which do not break the conformance to the definition of group. That means that for \(M\), adding the column labels, \((a_1, ..., a_n)\), and the row labels that equal the 1st column of \(M\) generates a multiplications table to make \(\{a_1, ..., a_n\}\) a group.
