## Monthly Archives: September 2011

### Facts about finite cyclic semigroups

Let $S$ be a finite cyclic semigroup. Show that $S$ has a unique maximal subgroup and compute it. Compute the kernel of $S$. Under what circumstances is $S$ a group? Deduce that every finite semigroup contains an idempotent.

Let $S$ be a finite cyclic subgroup with generator $s$. Now the map $\varphi : \mathbb{N}^+ \rightarrow S$ given by $k \mapsto s^k$ is a surjective semigroup homomorphism (where $\mathbb{N}^+$ is a semigroup under $+$). Since $\varphi$ cannot be injective, there exist pairs of distinct positive natural numbers $m+1 > n$ such that $s^{m+1} = s^n$. Let $(n,m+1)$ be such that $m+1$ is minimal among these pairs. (For such $m+1$, there is a unique $n < m+1$ with $s^n = s^{m+1}$, since otherwise $m+1$ is not minimal.)

We now prove a lemma.

Lemma 1: If $n,m \in \mathbb{N}^+$ with $n \leq m$, then there exists a unique $d \in \mathbb{N}^+$ such that $n \leq d(m+1-n) < m+1$. Proof: (Existence) Note that $m+1-n > 0$. By the Division Algorithm in $\mathbb{N}$, there exist natural numbers (that is, nonnegative integers) $q$ and $r$ such that $n = q(m+1-n) + r$ and $0 \leq r < m+1-n$. Letting $-t = r - (m+1-n)$ and $d = q+1$, we have $n = d(m+1-n) - t$, so that $0 \leq d(m+1-n) - n = t < m+1-n$, and thus $n \leq d(m+1-n) < m+1$. (Uniqueness) Suppose $n \leq d(m+1-n) < m$ and $n \leq e(m+1-n) \leq m$, we have $(d-e)(m+1-n) = 0$, so that $d-e = 0$, and so $d = e$. $\square$

This number $d(m+1-n)$ will turn out to be very special.

Lemma 2: For all $i \in \mathbb{N}$ and $k \in \mathbb{N}^+$, we have $s^{k(m+1-n)}s^{n+i} = s^{n+i}$. Proof: We proceed by induction on $k$. For the base case $k = 1$, if $i = 0$, then $s^{m+1-n}s^{n+i} = s^{m+1-n+n}$ $= s^{m+1} = s^n$ $= s^{n+i}$. If $i \neq 0$, then $s^{m+1-n}s^{n+i} = s^{m+1+i}$ $= s^{m+1}s^i$ $= s^ns^i$ $= s^{n+i}$. Now for the inductive step, suppose the result holds for some $k$. Then $s^{(k+1)(m+1-n)}s^{n+i} = s^{m+1-n}s^{k(m+1-n)}s^{n+1}$ $= s^{m+1-n}s^{n+i}$ $= s^{n+i}$. So the result holds for all $k \geq 1$. $\square$

Corollary 2.1: If $a,b \geq n$ and $a \equiv b$ mod $m+1-n$, then $s^a = s^b$. Proof: Without loss of generality, say $a > b$. Now $a-b = q(m+1-n)$ for some $q \geq 1$, and thus $a = q(m+1-n) + b$ and $b = n+i$ for some $i$. $\square$

Corollary 2.2: If $b \geq m+1$, then there exists $a$ such that $n \leq a < m+1$ and $s^b = s^a$. Proof: It suffices to show that there exists $a$ such that $n \leq a < m+1$ and $a \equiv b$ mod $m+1-n$. To that end, let $r$ be the least residue of $b-n$ mod $m+1-n$. That is, $b-n = q(m+1-n) + r$, where $q$ and $r$ are nonnegative. Letting $a = n+r$, we have Then $b = q(m+1-n) + a$ and $n \leq a < m+1$, so $s^b = s^a$. $\square$

Corollary 2.3: $S$ consists of the elements $\{s^1,s^2,\ldots,s^n,\ldots,s^m\}$, and these are pairwise distinct.

Lemma 3: If $a,b \geq n$ and $s^a = s^b$, then $a \equiv b$ mod $m+1-n$. Proof: Since $m+1-n \neq 0$ and $a-n, b-n \geq 0$, there exist nonnegative integers $q_1,q_2,r_1,r_2$ such that $a-n = q_1(m+1-n) + r_1$, $b-n = q_2(m+1-n) + r_2$, and $0 \leq r_1,r_2 < m+1-n$. Since $s^a = s^b$, we have $s^{q_1(m+1-n)+n+r_1} = s^{q_2(m+1-n)+n+r_2}$. Whether $q_1$ and $q_2$ are zero (trivially) or not (Lemma 2), we have $s^{n+r_1} = s^{n+r_2}$. Now $r_1,r_2 < m+1-n$, so that $r_1+n,r_2+n < m+1$. By the minimalness of $m+1$, we have $r_1 + n = r_2 + n$. Thus $a-n \equiv b-n$ mod $m+1-n$, and so $a \equiv b$ mod $m+1-n$. $\square$

Lemma 4: If $a < n$ and $b \in \mathbb{N}^+$ such that $b \neq a$, then $s^a \neq s^b$. Proof: If $b < m+1$ and $s^b = s^a$, we violate the minimalness of $m+1$. If $b \geq m+1$, then by Corollary 2.2, there is an integer $c$ with $n \leq c < m+1$ and $s^c = s^b = s^a$, again violating the minimalness of $m+1$. $\square$

Using Lemmas 3 and 4 and Corollary 2.1, we can now characterize the kernel of $\varphi$ as follows. The equivalence class $[a]$ is $\{a\}$ if $1 \leq a < n$, and is $\{b \geq n \ |\ b \equiv a\ \mathsf{mod}\ m+1-n\}$ if $a \geq n$.

Lemma 5: If $s^a$ is idempotent, with $1 \leq a \leq m$, then $a = d(m+1-n)$. (Where $d$ is as defined in Lemma 1.) Proof: If $1 \leq a < n$, then we have $a = 2a$, which has no solution in $\mathbb{N}^+$. If $n \leq a \leq m$, then $2a \equiv a$ mod $m+1-n$. So $a \equiv 0$ mod $m+1-n$, and then $a = q(m+1-n)$ for some $q$. By Lemma 1, $q = d$. $\square$

So $S$ has precisely one idempotent.

Lemma 6: Let $S$ be a semigroup. Let $E(S)$ denote the set of idempotents in $S$, and let $\mathsf{MG}(S)$ denote the set of maximal subgroups of $S$. Let $\psi : \mathsf{MG}(S) \rightarrow E(S)$ be defined by $G \mapsto 1_G$. Then $\psi$ is bijective. Proof: (Surjective) If $e \in S$ is idempotent, then the set $G_e = \{a \in S\ |\ ea = ae = a, ab = ba = e\ \mathrm{for\ some}\ b \in S\}$ is the $\subseteq$-greatest subgroup of $S$ having identity $e$ by 1.4.11. In particular, $G_e$ is a maximal subgroup, and $\psi(G_e) = e$. If $H \subseteq S$ is a subgroup with identity $e$, then $H \leq G_e$. If $H$ is maximal, then $H = G_e$. So $\psi$ is injective, and thus bijective. $\square$

Since our cyclic semigroup $S$ has only one idempotent, it has a unique maximal subgroup. Namely, $G_e$ where $e = s^{d(m+1-n)}$.

Lemma 7: $s^{d(m+1-n)}s^k = s^k$ if and only if $k \geq n$. Proof: The $(\Leftarrow)$ direction was proved in Lemma 2. Now suppose $s^{d(m+1-n) + k} = s^k$. Now $d(m+1-n) + k \geq n$, so that $k \geq n$ (using our characterization of $\mathsf{ker}\ \varphi$). $\square$

Lemma 8: If $k \geq n$, then there exists $\ell \geq n$ such that $s^ks^\ell = s^{d(m+1-n)}$. Proof: Choose $\ell \geq n$ such that $k+\ell \equiv 0$ mod $d(m+1-n)$. $\square$

Lemmas 7 and 8 demonstrate that $G_e = \{s^t\ |\ n \leq t \leq m\}$.

In particular, $S$ is a group if and only if $n = 1$.

Recall now that the kernel of a semigroup is the intersection of its two sided ideals.

Lemma 9: If $I \subseteq S$ is an ideal, then $G_e \subseteq I$. Proof: Suppose $s^a \in I$. For all $k \geq n$, there exists $b \geq 1$ such that $a+b \geq n$ and $a+b \equiv k$ mod $m+1-n$; then $s^bs^a = s^k$. So $G_e \subseteq I$. $\square$

Finally, using Corollary 2.2 if necessary, we can see that $G_e$ is itself an ideal of $S$. Thus the kernel of $S$ is $G_e$.

Finally, suppose $S$ is a finite semigroup and let $s \in S$. Now $(s)$ is a cyclic subsemigroup of $S$, and so must be finite. As we argued above, $(s)$, and thus $S$, contains an idempotent.

### Characterize the left ideal of a semigroup generated by a subset

Let $S$ be a semigroup and let $A \subseteq S$ be a nonempty subset. Recall that the left ideal of $S$ generated by $A$ is the intersection $L(A)$ of all the ideals which contain $A$, and similarly for right- and two-sided- ideals.

Prove that the left ideal generated by $A$ is $A \cup SA$ and that the two-sided ideal generated by $A$ is $A \cup SA \cup AS \cup SAS$.

Note that if $L$ is a left ideal containing $A$, then $SA \subseteq L$. In particular, $A \cup SA$ is contained in every left ideal which also contains $A$, and thus is contained in the left ideal generated by $A$. On the other hand, $S(A \cup SA) = SA \cup SSA \subseteq SA \subseteq A \cup SA$, and thus $A \cup SA$ is a left ideal of $S$ which certainly contains $A$. So the left ideal generated by $A$ is contained in $A \cup SA$, so that $L(A) = A \cup SA$.

Similarly, if $I$ is an ideal of $S$ containing $A$, then $A \cup SA \cup AS \cup SAS \subseteq I$. So $A \cup SA \cup AS \cup SAS$ is contained in the ideal $\langle A \rangle$ generated by $A$. And on the other hand, since $S(A \cup SA \cup AS \cup SAS) \subseteq A \cup SA \cup AS \cup SAS$, this set is a left ideal, and likewise a right ideal. So $A \cup SA \cup AS \cup SAS$ is a two sided ideal containing $A$. Hence $\langle A \rangle = A \cup SA \cup AS \cup SAS$.

### Groups are precisely those semigroups which are both left and right simple

Prove that a semigroup $S$ is a group if and only if it is both left and right simple. Exhibit a left simple semigroup which is not right simple.

We begin with a lemma.

Lemma: Let $S$ be a semigroup. Then $S$ is left simple (right simple) [simple] if and only if $Sa = S$ ($aS = S$) [$SaS = S$] for all $a \in S$. Proof: Suppose $S$ is left simple, and let $a \in S$. Certainly $SSa \subseteq Sa$, so that $Sa$ is a left ideal. Thus $Sa = S$ for all $a \in S$. Conversely, suppose $Sa = S$ for all $a \in S$, and let $L \subseteq S$ be a left ideal. Now $L$ is nonempty by definition; say $a \in L$. Then $Sa \subseteq L$, and so $S \subseteq L$. Thus $L = S$, and in fact $S$ is the only left ideal of $S$. So $S$ is left simple. The proofs for right simple and simple are similar. $\square$

Now let $S$ be a group and let $a \in S$. If $x \in S$, then we have $x = xe = xa^{-1}a$; in particular, $x \in Sa$. So $S = Sa$ for all $a$. By the lemma, $S$ is left simple. Similarly, $S$ is right simple.

Now suppose the semigroup $S$ is both left and right simple. Let $a \in S$. Since $Sa = S$, there exists an element $e \in S$ such that $ea = a$. Now let $b \in S$ be arbitrary. Since $aS = S$, there exists $c \in S$ such that $b = ac$. Now $b = ac = eac = eb$, so in fact $e$ is a left identity element of $S$. Similarly, there is a right identity element $f$, and we have $e = ef = f$, so that $e$ is a two-sided identity.

Now let $a \in S$ be arbitrary. Since $Sa = aS = S$, there exist elements $b,c \in S$ such that $ba = ac = e$. Now $b = be = bac = ec = c$, and we have $b = c$. Thus $a$ has a two sided inverse with respect to $e$. Since $a$ was arbitrary, every element has an inverse, and so $S$ is a group.

Now consider the semigroup $S = \{a,b\}$ with $xy = x$ for all $x,y \in S$. (That is, $S$ is the left zero semigroup on two elements.) Suppose $T \subseteq S$ is a left ideal. Now for all $x \in S$ and $y \in T$, we have $xy = x \in T$. Thus $T = S$, and so $S$ is left simple. However, $S$ is not a group, and so (by the previous argument) cannot be right simple.

### The semigroup of nonempty subsets of a semigroup

Let $S$ be a semigroup, and let $P(S)$ denote the set of all nonempty subsets of $S$. Show that $P(S)$ is a semigroup under the operation $AB = \{ab \ |\ a \in A, b \in B\}$. Which of the basic properties of $S$ are preserved by $P(S)$?

We need only show that this operator is associative. Indeed, $(AB)C = \{ab\ |\ a \in A, b \in B\}C$ $= \{(ab)c\ |\ a \in A, b \in B, c \in C\}$ $= \{a(bc)\ |\ a \in A, b \in B, c \in C\}$ $= A\{bc\ |\ b \in B, c \in C\}$ $= A(BC)$.

Suppose $S$ has a left identity $e$. Then for all $A \in P(S)$, we have $\{e\}A = \{ea \ |\ a \in A\}$ $= \{a \ |\ a \in A\}$ $= A$. That is, $\{e\}$ is a left identity in $P(S)$. Similarly if $e$ is a right identity in $S$, then $\{e\}$ is a right identity in $P(S)$. Then if $e$ is an identity in $S$, $\{e\}$ is an identity in $P(S)$.

Suppose $S$ has a left zero $z$. Then for all $A \in P(S)$, we have $\{z\}A = \{za\ |\ a \in A\}$ $= \{z\ |\ a \in A\}$ $= \{z\}$. Thus $\{z\}$ is a left zero in $P(S)$. Similarly, if $z$ is a right zero in $S$ then $\{z\}$ is a right zero in $P(S)$, and if $z$ is a zero in $S$ then $\{z\}$ is a zero in $P(S)$.

If $S$ is commutative, then for all $A,B \in P(S)$ we have $AB = \{ab \ |\ a \in A, b \in B\}$ $= \{ba \ |\ b \in B, a \in A\}$ $= BA$. Thus $P(S)$ is also commutative.

Suppose $e \in S$ is an identity element and $u \in S$ is a unit, with $uv = vu = e$. Then $\{u\}\{v\} = \{v\}\{u\} = \{e\}$, so that $\{u\}$ is a unit in $P(S)$.

Suppose $I \subseteq S$ is a left ideal. Now let $A \subseteq S$ and $B \subseteq I$ be nonempty subsets. Now $AB = \{ab \ |\ a \in A, b \in B\} \subseteq I$, since $B \subseteq I$, and moreover this set is nonempty since $A$ and $B$ are nonempty. That is to say, $AB \in P(I)$. So $P(I) \subseteq P(S)$ is a left ideal. Likewise if $I$ is a right ideal in $S$, then $P(I)$ is a right ideal in $P(S)$, and if $I$ is a two-sided ideal in $S$, then $P(I)$ is a two-sided ideal in $P(S)$. More generally, if $T \subseteq S$ is a subsemigroup, then $P(T) \subseteq P(S)$ is a subsemigroup.

Suppose $S$ is a left zero semigroup. That is, $ab = a$ for all $a,b \in S$. If $A,B \in P(S)$, then $AB = \{ab \ |\ a \in A, b \in B\}$ $= \{a \ |\ a \in A, b \in B\}$ $= A$. That is, $P(S)$ is also a left zero semigroup. Similarly, if $S$ is a right zero semigroup then so is $P(S)$. Suppose now that $S$ has a zero element $0$, and that $S$ is a zero semigroup. Now $\{0\}$ is a zero in $P(S)$, and for all $A,B \in P(S)$, we have $AB = \{ab \ |\ a \in A, b \in B\}$ $= \{0 \ |\ a \in A, b \in B\}$ $= \{0\}$. So $P(S)$ is also a zero semigroup.

If $S$ is simple, $P(S)$ need not be simple, as we show. Consider the group $G = Z_2 = \{1,x\}$. We can easily verify that the only two-sided ideal in $G$ is $G$ itself, so that $G$ is simple as a semigroup. Now $P(Z_2) = \{\{1\}, \{x\}, Z_2\}$, and evidently, $\{Z_2\}$ is an ideal in $P(Z_2)$, so that $P(Z_2)$ is not simple.

### Every square matrix over a Euclidean domain can be diagonalized by elementary row and column operations

Show that if $A$ is a matrix over a Euclidean domain $R$, then there is a sequence of elementary row and column operations (as described here and here) which, when performed on $A$, result in a matrix $\begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}$ such that $D = [d_{i,j}]$ is square and diagonal and if $d_{1,1},\ldots, d_{k,k}$ are the nonzero diagonal entries of $D$ ($k \leq n$), we have $d_{i,i} | d_{j,j}$ whenever $i \leq j$.

Conclude that if $M$ is a finitely generated $R$-module with relations matrix $A$ (see here for a discussion of relations matrices) then $M \cong R^{n-k} \oplus \bigoplus_{i=1}^k R/(d_i)$.

Let $N : R \rightarrow \mathbb{N}$ denote the Euclidean norm on $R$.

Note first that if $A = 0$, there is nothing to show. If $A \neq 0$, we proceed by induction on the number $m$ of rows of $A$.

For the base case $m = 1$, say $A = [a_{1,1}\ a_{1,2}\ \cdots\ a_{1,n}]$. If $n = 1$ there is nothing to show, so we assume $n \geq 2$. We now proceed by induction on $\sum_{i=2}^n N(a_{1,i})$. For the base case, if $\sum_{i=2}^n N(a_{1,i}) = 0$, then $a_{1,i} = 0$ for each $2 \leq i \leq n$, and so $A = [a_{1,1} | 0]$ has the desired form. For the inductive step, suppose that for all $1 \times n$ matrices $B = [b_{1,1}\ b_{1,2}\ \cdots\ b_{1,n}]$ such that $\sum_{i=2}^n N(b_{1,i}) \leq K$, $B$ can be diagonalized by some sequence of elementary row and column operations. Now suppose $\sum_{i=2}^n N(a_{1,i}) = K+1$. Using column operation 1 (swap two columns), rearrange the columns of $A$ so that $a_{1,1}$ has minimal norm. By the Division Algorithm, there exist $q_i$ and $r_i$ such that $a_{1,i} = q_ia_{1,1} + r_i$ and either $r_i = 0$ or $N(r_i) < N(a_{1,1})$ for each $2 \leq i \leq n$. Using column operation 2 (add a multiple of one column to a different one) $n-1$ times, one for each column after the first, we can put $A$ in the form $[a_{1,1}\ r_2\ \cdots\ r_n]$. Now $\sum_{i=2}^n N(r_i) < \sum_{i=2}^n N(a_{1,1}) \leq \sum_{i=2}^n N(a_{1,i})$. By the inductive hypothesis, there is a sequence of elementary row and column operations which diagonalize this new matrix, and so there is a sequence of elementary row and column operations which diagonalizes $A$. This proves our base case, where $A$ has one row.

Suppose now that the result holds for every matrix having at most $m$ rows, and let $A$ be an $(m+1) \times n$ matrix. Say $A = \begin{bmatrix} a_{1,1} & R_1 \\ C_1 & A_1 \end{bmatrix}$, where $R_1 = [r_{1,2}\ cdots\ r_{1,n}]$ and $C_1 = [c_{2,1}\ \cdots\ c_{m+1,1}]^\mathsf{T}$.

We next claim that there is a sequence of elementary row and column operations which transforms $A$ into a matrix of the form $\begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix}$. To prove this, we proceed by induction on $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i})$. (Note that it may be the case that $n = 1$. In this case the sum over the $r$ is empty and thus 0. However, the sum over the $c$ is not empty.) If $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = 0$, then we have $c_{i,1} = r_{1,j} = 0$ for each $2 \leq i \leq m+1$ and $2 \leq j \leq n$, and so $A = \begin{bmatrix} a_{1,1} & 0 \\ 0 & A_1 \end{bmatrix}$ has the desired form. For the induction hypothesis, suppose that for some $K \in \mathbb{N}$, every matrix $B$ can be put in the desired form provided $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) \leq K$, and suppose that for our $A$ we have $\sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1$. Now among the entries of our matrix, choose a nonzero element of minimal norm and use elementary row and column operations of type 1 (swap) to put this entry in position (1,1). (If no such entry exists, then $A = 0$ and there is nothing to show.) Now by the Division Algorithm in $R$, there exist $q_i,t_j,u_i,v_j$ such that $r_{1,i} = q_ia_{1,1} + u_i$, $c_{j,1} = t_ja_{1,1} + v_j$, $0 \leq N(u_i) < N(a_{1,1})$, and $0 \leq N(v_j) < N(a_{1,1})$. Using elementary row and column operations of type 2 (add a multiple of one row/column to a different row/column) we can replace $r_{1,i}$ with $u_i$ and likewise replace $c_{j,1}$ by $v_j$. Note now that $\sum_{i=2}^{m+1} N(v_j) + \sum_{i=2}^n N(u_i) < \sum_{i=2}^{m+1} N(a_{1,1}) + \sum_{i=2}^n N(a_{1,1})$ $\leq \sum_{i=2}^{m+1} N(c_{i,1}) + \sum_{i=2}^n N(r_{1,i}) = K+1$. By the induction hypothesis, there is a sequence of elementary row and column operations which puts the new $A$ in the desired form, and so (performing these one after the other) we can put the original matrix $A$ in the desired form.

Now $A$ can be put in the form $\begin{bmatrix} a_1 & 0 \\ 0 & A_1 \end{bmatrix}$ by elementary row and column operations. Note that any row or column operation we perform on $A_1$, when performed analogously on $A$, does not change the entry $a_1$ or introduce new nonzero elements to row and column 1. Since (as we assume by the induction hypothesis) the matrix $A_1$ can be diagonalized, then $A$ can also be diagonalized by elementary row and column operations.

We have thus shown by induction that every matrix $A$ over a Euclidean domain can be diagonalized. It remains to be seen that these diagonal entries can be ordered by divisibility. We can assume that our matrix $D$ is square and has all nonzero entries on the main diagonal. We proceed by induction on the dimension of $D$. For the base case, where $D$ has dimension $1 \times 1$, there is nothing to show. Suppose now that every square diagonal matrix $D$ of dimension $n$ can have its diagonal entries divisibility-ordered by elementary row and column operations and let $D = \begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix}$ be a square diagonal matrix of dimension $n+1$. We claim that $d_1$ can be replaced by the greatest common divisor of all the $d_i$, and that each remaining $d_i$ can be replaced by a linear combination of the $d_i$s, via elementary row and column operations. We will show this for one $d_i$. Note that if $D$ is diagonal, then row and column operations which only operate on two rows and columns (say $a$ and $b$) do not affect the rest of the matrix. For this reason we can focus on a $2 \times 2$ matrix, say $\begin{bmatrix} d_1 & 0 \\ 0 & d_i \end{bmatrix}$. Since $R$ is a Euclidean domain, using the extended Euclidean Algorithm we can find $x$ and $y$ such that $\mathsf{gcd}(d_1,d_i) = xd_1 + yd_i$. Using a column/row operation of type 2, we can obtain $\begin{bmatrix} d_1 & xd_1 + yd_i \\ 0 & d_i \end{bmatrix}$. Swapping rows (or columns), we have $\begin{bmatrix} \mathsf{gcd}(d_1,d_i) & d_1 \\ d_i & 0 \end{bmatrix}$. If $d_1 = a_1\mathsf{gcd}(d_1,d_i)$, then again we can obtain $\begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ d_i & a_1d_i \end{bmatrix}$, and so $\begin{bmatrix} \mathsf{gcd}(d_1,d_i) & 0 \\ 0 & a_1d_i \end{bmatrix}$. Repeating this procedure for each diagonal entry (except the first), and since greatest common divisor is associative, we have a diagonal matrix $\begin{bmatrix} d_1 & 0 \\ 0 & D_1 \end{bmatrix}$ where $d_1$ divides each diagonal entry of $D_1$. By induction, $D$ is row/column equivalent to a diagonal matrices whose diagonal entries are ordered by divisibility.

Finally, suppose we have a finitely generated $R$-module $M$, with (say) a generating set of cardinality $n$ and corresponding surjective homomorphism $\varphi : R^n \rightarrow M$. By the preceding result, there exists a basis $B = \{e_1, \ldots, e_n\}$ for $R^n$ and a generating set $E = \{e_1,\ldots,e_m\}$ for $\mathsf{ker}\ \varphi$ such that the corresponding relations matrix is of the form $\begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}$, $D$ is square of dimension $k \leq n$ and has no zero diagonal entries, and the diagonal entries of $D$ are ordered by divisibility. In particular, we have $\mathsf{ker}\ \varphi = Rd_1 + \cdots Rd_k = (d_1) \oplus \cdots \oplus (d_k) \oplus 0^{n-k}$. Then by this previous exercise, $M \cong R/\mathsf{ker}\ \varphi \cong R/(d_1) \oplus \cdots \oplus R/(d_k) \oplus R^{n-k}$. Note that if any $d_i$ are units, then the corresponding quotient $R/(d_i)$ is trivial.

By the uniqueness portion of the Fundamental Theorem of Finitely Generated Modules over a PID, the (nonunit) $d_i$ are precisely the invariant factors of $M$.

### Characterize the ideals and congruences on the semigroup of natural numbers under max

Characterize the ideals and congruences on the semigroup $\mathbb{N}$ of natural numbers under the $\mathsf{max}$ operator. (I.e., $a\ \mathsf{max}\ b = a$ if $a \geq b$, $b$ otherwise.)

First we will make some definitions.

Definition: A subset $I \subseteq \mathbb{N}$ is called an interval if, whenever $a \leq c \leq b$ and $a,b \in I$, $c \in I$.

Lemma 1: Every nonempty interval in $\mathbb{N}$ has the form $[a,b] = \{c \ |\ a \leq c \leq b\}$ for some $a,b$ or $[a,\infty) = \{c \ |\ a \leq c\}$. Proof: Every nonempty interval on $\mathbb{N}$ has a least element by the well-ordering property of natural numbers. If a nonempty interval $I$ has a greatest element $b$, then $c \in I$ for all $a \leq c \leq b$, and so we have $I = [a,b]$. If $I$ does not have a greatest element, then for every $c \geq a$, there exists $b \in I$ with $a \leq c \leq b$, and thus $c \in I$. So we have $I = [a,\infty)$. $\square$

Lemma 2: If $I$ and $J$ are disjoint intervals and there exist $a \in I$ and $b \in J$ such that $a \leq b$, then for all $x \in I$ and $y \in J$ we have $x \leq y$. Proof: Suppose to the contrary that there exist $x \in I$ and $y \in J$ with $y \leq x$. There are six possible orderings for $\{a,b,x,y\}$ which preserve $a \leq b$ and $y \leq x$. Specifically, these are $a \leq b \leq y \leq x$, $a \leq y \leq b \leq x$, $a \leq y \leq x \leq b$, $y \leq a \leq b \leq x$, $y \leq a \leq x \leq b$, and $y \leq x \leq a \leq b$. In each case, $I \cap J$ is not empty. $\square$

Next we consider the ideals on $\mathbb{N}$. To that end, let $I \subseteq \mathbb{N}$ be a subset.

Suppose that $I$ is an ideal under the $\mathsf{max}$ operator. If $I$ is nonempty (as we insist our ideals to be), then it has a least element $a$ by the well-ordering property of the natural numbers. If $b \geq a$, then $\mathsf{max}(a,b) = b \in I$, and if $b < a$, then $b \notin I$ since $a$ is minimal. Thus $I = [a,\infty)$.

Conversely, suppose $I = [a,\infty)$ for some $a \in \mathbb{N}$. If $t \in I$ and $s \in \mathbb{N}$, then we have $t \geq a$. So $\mathsf{max}(s,t) \geq a$, and thus $\mathsf{max}(s,t) \in I$. So $I$ is an ideal.

Hence the ideals of $(\mathbb{N}, \mathsf{max})$ are precisely the intervals $[a,\infty)$ where $a \in \mathbb{N}$.

Now we will consider the congruences on $\mathbb{N}$. To that end, let $\sigma \subseteq \mathbb{N} \times \mathbb{N}$ be an equivalence relation.

Suppose $\sigma$ is a congruence, and let $A \subseteq \mathbb{N}$ be a $\sigma$-class. We claim that $A$ is an interval. To that end, let $a,b \in A$ and suppose $a \leq c \leq b$. Now $a \sigma b$ and $c \sigma c$, so that (since $\sigma$ is a congruence) $ac \sigma bc$, and thus $c \sigma b$. So $c \in A$. Thus $A$ is an interval (by our definition above). Thus if $\sigma$ is a congruence on $\mathbb{N}$ under $\mathsf{max}$, then the classes of $\sigma$ are pairwise disjoint intervals.

Conversely, suppose the classes of the equivalence relation $\sigma$ are pairwise disjoint intervals. We claim that $\sigma$ is a congruence. To that end, suppose $a \sigma b$ and $c \sigma d$, and suppose without loss of generality that $a \leq c$. By Lemma 2, we have $b \leq d$. So $ac = c \sigma d = bd$. Thus $\sigma$ is a congruence.

Hence the congruences on $(\mathbb{N}, \mathsf{max})$ are precisely the paritions of $\mathbb{N}$ which consist of intervals.

### Exhibit a subsemigroup of a cyclic semigroup which is not cyclic

Exhibit a subsemigroup of a cyclic semigroup which is not cyclic.

Consider the semigroup $\mathbb{N}$ of natural numbers under addition. Certainly $\mathbb{N}$ is cyclic with generator 1. Define $T \subseteq \mathbb{N}$ by $T = \{2a+3b\ |\ a,b \in \mathbb{N}\}$.

Certainly $T$ is nonempty, since $0 = 2\cdot 0 + 3 \cdot 0 \in T$. Moreover, if $2a_1 + 3b_1, 2a_2 + 3b_2 \in T$, then $(2a_1+3b_1) + (2a_2 + 3b_2) = 2(a_1+a_2) + 3(b_1+b_2) \in T$. So $T \subseteq \mathbb{N}$ is a subsemigroup of a cyclic semigroup.

Now suppose $T$ is cyclic, with generator $2a_0 + 3b_0$. Now $2 = 2 \cdot 1 + 3 \cdot 0 \in T$, so $2 = k(2a_0 + 3b_0)$ for some $k \in \mathbb{N}$. Certainly $k \neq 0$. If $b_0 \neq 0$, then we have $2 = k(2a_0+3b_0) \geq 3kb_0$ $\geq 3 > 2$, a contradiction. So $b_0 = 0$, and we have $2 = 2ka_0$. So $1 = ka_0$, and thus $a_0 = 1$. That is, $T$ is generated by $2 \cdot 1 + 3 \cdot 0 = 2$. But we also have $3 = 2 \cdot 0 + 3 \cdot 1 \in T$, so that $3 = 2k$ for some $k \in \mathbb{N}$, a contradiction.

So $T$ is not cyclic.

### Exhibit a semigroup which is not finitely generated and a semigroup which is finitely generated but not cyclic

Exhibit a semigroup which is not finitely generated and a semigroup which is finitely generated but not cyclic.

We begin with some lemmas of a more general nature.

Lemma 1: Let $I$ be a set and let $\{S_i\}_I$ be a family of semigroups indexed by $I$. Then the usual cartesian product of sets $\prod_I S_i$ is a semigroup under the induced operation $(s_i) \cdot (t_i) = (s_it_i)$. Moreover, if each $S_i$ is a monoid with identity $e_i$, then $\prod_I S_i$ is a monoid with identity $(e_i)$, and if each $S_i$ is commutative, then $\prod_I S_i$ is commutative. Proof: We need only show that this operator is associative. Indeed, $((s_i) \cdot (t_i)) \cdot (u_i) = (s_it_i) \cdot (u_i)$ $= ((s_it_i)u_i)$ $= (s_i(t_iu_i))$ $= (s_i) \cdot (t_iu_i)$ $= (s_i) \cdot ((t_i) \cdot (u_i))$ for all $(s_i). (t_i), (u_i) \in \prod_I S_i$ as desired. Now if $e_i$ is an identity in $S_i$ for each $i \in I$, then given $(s_i) \in \prod_I S_i$, we have $(e_i) \cdot (s_i) = (e_is_i) = (s_i)$ and likewise $(s_i) \cdot (e_i) = (s_i)$. Finally, if each $S_i$ is commutative, then $(s_i) \cdot (t_i) = (s_it_i)$ $= (t_is_i)$ $= (t_i) \cdot (s_i)$. $\square$

Lemma 2: Let $I$ be a set and let $\{S_i\}$ be a family of monoids (with identity $e_i \in S_i$) indexed by $I$. Then the set $\{(s_i) \in \prod_I S_i \ |\ s_i = e_i\ \mathrm{for\ all\ but\ finitely\ many}\ i \in I\}$ is a subsemigroup of $\prod_I S_i$, which we denote $\bigoplus_I S_i$. Proof: In view of Lemma 1, we need only show that this set is closed under multiplication. Indeed, if $(s_i), (t_i) \in \bigoplus_I S_i$, then there exist finite sets $A,B \subseteq I$ such that, if $i \notin A$, then $s_i = e_i$, and if $i \notin B$, then $t_i = e_i$. In particular, if $i \notin A \cup B$, then $s_it_i = e_i$. Now $A \cup B \subseteq I$ is finite, and thus $(s_i) \cdot (t_i) \in \bigoplus_I S_i$. So $\bigoplus_I S_i$ is a subsemigroup of $\prod_I S_i$. $\square$

Now consider $\mathbb{N}$ as a semigroup under addition and let $S = \bigoplus_\mathbb{N} \mathbb{N}$. We claim that $S$ is not finitely generated. To see this, suppose to the contrary that $S$ has a finite generating set $A = \{\alpha_1, \ldots, \alpha_k\}$, where $\alpha_j = (a_{j,i})$ and $a_{j,i} \in S_i$ for each $i \in \mathbb{N}$. Now for each $j$, the set of all indices $i$ such that $a_{j,i} \neq 0$ is finite- in particular, it has a largest element with respect to the usual order on $\mathbb{N}$. Let this number be $N_j$. Now let $N = \mathsf{max}_j N_j$. For any index $k > N$, we have $a_{j,i} = 0$.

Since (as we suppose) $S$ is generated by $A$, every element of $S$ can be written as a finite product (or sum, as it were, since $S$ is commutative) of elements from $A$. But in any such sum, the $k$th entry must be 0 for all $k > N$. But $S$ certainly has elements whose $k$th entry is not zero, and so we have a contradiction. So $S$ is not finitely generated.

Now consider $T = \mathbb{N} \times \mathbb{N}$, where again we consider $\mathbb{N}$ to be a semigroup under addition. Using additive notation, $T$ is evidently generated by $\{(0,1), (1,0)\}$ since $(a,b) = a(1,0) + b(0,1)$. Suppose now that $T$ is cyclic- say $T$ is generated by $(a_0,b_0)$. Now every element of $T$ has the form $k(a_0,b_0) = (ka_0,kb_0)$ for some $k$. For example, $(1,1) = (ka_0,kb_0)$, so $1 = ka_0$ and $1 = kb_0$. In $\mathbb{N}$, we then have $a_0 = b_0 = 1$. But then $(1,2) = k(1,1) = (k,k)$, so that $1 = k = 2$– a contradiction. Thus $\mathbb{N}$ is not finitely generated.

### Every infinite cyclic semigroup is isomorphic to the positive natural numbers under addition

Prove that every infinite cyclic semigroup is isomorphic to the semigroup $(\mathbb{N}^+, +)$ of positive natural numbers under addition.

First, let’s clarify some terminology. If $S$ is a semigroup and $s \in S$, then there is a semigroup homomorphism $\varphi : \mathbb{N}^+ \rightarrow S$ given by $k \mapsto s^k$. The image of $\varphi$ is called the cyclic subsemigroup of $S$ generated by $s$, and if $\varphi$ is surjective, then we say $S$ is cyclic with $s$ as a generator. If $S$ has an (unique) identity element $e$, then the homomorphism $\varphi$ extends to a mapping $\psi : \mathbb{N} \rightarrow S$ by $0 \mapsto e$ and this is also a semigroup homomorphism. The image of $\psi$ is called the cyclic submonoid of $S$ generated by $s$.

First, it is clear that $(\mathbb{N}^+, +)$ is an infinite cyclic semigroup.

Suppose now that $S$ is an infinite cyclic semigroup with $s$ a generator. Now $\varphi : \mathbb{N}^+ \rightarrow S$ given by $k \mapsto s^k$ is a surjective semigroup homomorphism. We only need to show that $\varphi$ is injective. To that end, suppose we have $\varphi(a) = \varphi(b)$ for some $a,b \in \mathbb{N}^+$, so that $s^a = s^b$. Suppose, without loss of generality, that $a < b$; say $b = a+k$, so that $s^{a+k} = s^{a}$. But now for all $t \geq 0$, by the division algorithm we have $t = qk + r$ for some $q$ and $0 \leq r < k$. Then $s^{a+t} = s^{a+qk+r} = s^{a+r}$. Indeed, for all positive natural numbers $\ell$, we have $\varphi(\ell) \in \{s^1, s^2, \ldots, s^a, s^{a+1}, \ldots, s^{a+k-1}\}$. In particular, $\mathsf{im}\ \varphi$, hence $S$, is finite- a contradiction. Thus $a = b$, and so $\varphi$ is injective. So $S \cong \mathbb{N}^+$.

### Properties of the rows of a relations matrix

Let $R$, $M$, $\varphi$, $x_j$, $y_i$, and $A$ be defined as in this previous exercise.

1. Show that interchanging the generators $y_a$ and $y_b$ has the effect of interchanging the $a$th and $b$th rows of the relations matrix $A$.
2. Show that, for any $r \in R$, replacing $y_a$ by $y_a + ry_b$ $a \neq b$) gives another generating set $S^\prime$ for $\mathsf{ker}\ \varphi$. Show further that the matrix with respect to this generating set is obtained from $A$ by adding $r$ times the $b$th row to the $a$ th row.

It is clear that interchanging $y_a$ and $y_b$ in $S$ interchanges the $a$th and $b$th rows of $A$, since the $i$th row of $A$ is merely the $B$-expansion of $y_i$.

Our proof in the previous exercise that adding a multiple of one element in a generating set to another element does not change the generated submodule holds here as well, so the altered set $S^\prime = \{y_1, \ldots, y_a + ry_b, \ldots, y_b, \ldots, y_m\}$ is indeed a generating set for $\mathsf{ker}\ \varphi$. Moreover, it is clear that the new $a$th row is just the old $a$th row plus $r$ times the old $b$th row.