733: 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

<The previous article in this series | The table of contents of this series | The next article in this series>

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:
(
$\mathrm{\forall }j,k\in \{1,...,n\}(\mathrm{\exists }l\in \{1,...,n\}(M_k\circ M_j=M_l))$
$⟺$
$\{M_1,...,M_n\}\in \{\text{ the groups }\}$
)
$\wedge$
(
$\mathrm{\forall }j,k\in \{1,...,n\}(\mathrm{\exists }l\in \{1,...,n\}(M_k\circ M_j=M_l))$
$⟹$
(
its multiplications table, $M^{\prime }$, 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^{\prime }$: after all, $\{M_1,...,M_n\}=\{M_1^{\prime },...,M_n^{\prime }\}$ in some possibly different orders
2) each $a_j$ in $M$ is replaced by $M_j^{\prime }$
3) the column labels are $(M_1^{\prime },...,M_n^{\prime })$
4) the row labels are the 1st column of $M^{\prime }$
)
)
//

For example, for $M=\left(\begin{array}{ccc}{a}_2& a_3& a_1\\ a_1& a_2& a_3\\ a_3& a_1& a_2\end{array}\right)$, $M^{\prime }=\begin{array}{llll}& M_1^{\prime }& M_2^{\prime }& M_3^{\prime }\\ M_2^{\prime }& M_2^{\prime }& M_3^{\prime }& M_1^{\prime }\\ M_1^{\prime }& M_1^{\prime }& M_2^{\prime }& M_3^{\prime }\\ M_3^{\prime }& M_3^{\prime }& M_1^{\prime }& M_2^{\prime }\end{array}$; of course, the rows can be reordered such that $M^{\prime }=\begin{array}{llll}& M_1^{\prime }& M_2^{\prime }& M_3^{\prime }\\ M_1^{\prime }& M_1^{\prime }& M_2^{\prime }& M_3^{\prime }\\ M_2^{\prime }& M_2^{\prime }& M_3^{\prime }& M_1^{\prime }\\ M_3^{\prime }& M_3^{\prime }& M_1^{\prime }& M_2^{\prime }\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 $\mathrm{\forall }j,k\in \{1,...,n\}(\mathrm{\exists }l\in \{1,...,n\}(M_k\circ M_j=M_l))$, $\{M_1,...,M_n\}$ is a group, and its multiplications table, $M^{\prime }$, 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^{\prime }$: after all, $\{M_1,...,M_n\}=\{M_1^{\prime },...,M_n^{\prime }\}$ in some possibly different orders; 2) each $a_j$ in $M$ is replaced by $M_j^{\prime }$; 3) the column labels are $(M_1^{\prime },...,M_n^{\prime })$; 4) the row labels are the 1st column of $M^{\prime }$.

---

3: Proof

Whole Strategy: Step 1: suppose that $\mathrm{\forall }j,k\in \{1,...,n\}(\mathrm{\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 $\mathrm{\forall }j,k\in \{1,...,n\}(\mathrm{\exists }l\in \{1,...,n\}(M_k\circ M_j=M_l))$; Step 7: see that $M^{\prime }$ generated in the way is indeed the multiplications table of the group.

Step 1:

Let us suppose that $\mathrm{\forall }j,k\in \{1,...,n\}(\mathrm{\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\ne 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:

$\mathrm{\forall }j,k\in \{1,...,n\}(\mathrm{\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^{\prime }$ is indeed the multiplications table.

$\{M_1,...,M_n\}=\{M_1^{\prime },...,M_n^{\prime }\}$ 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^{\prime }{M}_j^{\prime }=M_l^{\prime }$ means that $M_k^{\prime }{M}_j^{\prime }$ maps $a_1$ to $a_l$, but $M_j^{\prime }$ maps $a_1$ to $a_j$, so, $M_k^{\prime }$ maps $a_j$ to $a_l$, which means that $a_l=M_m^j$ where $M_k^{\prime }=M_m$. As $M_k^{\prime }$ corresponds to the $m$-th row of $M^{\prime }$ and $M_j^{\prime }$ corresponds to the $j$-th column of $M^{\prime }$, the $(m,j)$ component of $M^{\prime }$ needs to be $M_l^{\prime }$. So, replacing $M_m^j=a_l$ with $M_l^{\prime }$ indeed generates the multiplications table of the group.

---

4: Note

As an immediate corollary, replacing the components of $M^{\prime }$ as $M_j^{\prime }\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.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>