2
$\begingroup$

This may be a simple question, but I can't make it out right now.

Let $M$ be a monoid, and $g_1, \ldots, g_n \in M$ be elements of finite order in $M$. Is $\langle g_1, \ldots, g_n \rangle$ periodic (i.e, have all its elements of finite order)?

The monoid I'm interested in is the multiplicative monoid of $n \times n$ matrices over $\mathbb{N}$.

Thanks.

  • 0
    It's true for the $2\times 2$ matrices over $\mathbb{N}$ for silly reasons: the only elements of finite order are $\left(\begin{array}{cc}1& 0 \\ 0 &1\end{array}\right)$ and $\left(\begin{array}{cc}0 & 1\\1 & 0\end{array}\right)$.2010-12-31
  • 0
    Damn, you're right! That makes me realize that ... this is not the question I wanted to ask! Wow, never post late on the 31st of December. I'll launch a new question with the correct wording.2011-01-01
  • 0
    The new question: http://math.stackexchange.com/questions/16038/is-a-monoid-finitely-generated-by-periodic-matrices-periodic2011-01-01

2 Answers 2

6

(Edit because I misread the question somewhat.)

To show that this is false for an arbitrary monoid it suffices to exhibit a monoid generated by elements of finite order which has elements of infinite order. Take, for example, $M = \langle a, b | a^2 = b^2 = 1 \rangle$. In this monoid $ab$ has infinite order. One can see this geometrically by constructing the following linear representation: let $a$ and $b$ act by reflection across two lines through the origin at an angle $\theta$ with respect to each other which is not a rational multiple of $\pi$. (For this reason $M$ is known as the infinite dihedral group.)

Probably the most important example of this phenomenon "in nature" is the modular group, which has group presentation $\langle a, b | a^2 = b^3 = 1 \rangle$ and hence is generated by an element of order $2$ and an element of order $3$.

I am not sure about your particular $M$. Does $\mathbb{N}$ contain $0$ for you? (If not I am having trouble finding any nontrivial elements of finite order.)

  • 2
    @Qiaochu: I don't think the OP is wondering if the monoid of all $n\times n$ matrices over $\mathbb{N}$ has elements of infinite order, but whether a submonoid generated by element of finite order may contain any. So I'm not sure your first paragraph is appropriate. Of course, the result is false in general, with your first $M$ being the infinite dihedral group.2010-12-31
  • 0
    Ah, sorry, I misread the question.2010-12-31
  • 1
    @Qiaochu: It must contain $0$, otherwise there is no identity (hence no monoid)...2010-12-31
  • 1
    @Arturo: I think the only elements of finite order are permutations. Does that sound reasonable to you?2011-01-01
  • 1
    @Qiaochu: It is the case in $n=2$, and it seemed that way for $n=3$ as well (though I didn't check it thoroughly). It would not surprise me.2011-01-01
  • 0
    Right, $0 \in \mathbb{N}$ for me. Thank you for your answers, guys.2011-01-01
4

For the case you're interested in it is true, because the set of finite order $n$-by-$n$ matrices over $\mathbb{N}$ is precisely the set of permutation matrices. In fact, every invertible element of $M_n(\mathbb{N})$ is a permutation matrix. (Here $\mathbb{N}$ contains $0$, and invertible means invertible in the monoid $M_n(\mathbb{N})$ with multiplication.)

Suppose that $B=(b_{ij})\in M_n(\mathbb{N})$ is not a permutation matrix. Then either one of the entries of $B$ is greater than $1$, one of the rows or columns of $B$ has more than one nonzero entry, or one of the rows or columns of $B$ is zero. Let $A=(a_{ij})\in M_n(\mathbb{N})$ be invertible.

Suppose first that $B$ has an entry greater than $1$, i.e., $b_{i_0j_0}\gt1$ for some $i_0$ and $j_0$. Since $A$ is invertible, its $i_0^\text{th}$ column is not zero, so there is an $i_1$ such that $a_{i_1i_0}\gt0$. Then if $AB=(c_{ij})$, we have $c_{i_1j_0}\geq a_{i_1i_0}b_{i_0j_0}\gt1$, so that $AB\neq I$. Hence, $B$ is not invertible in this case.

Now suppose that $B$ has a row with more than one nonzero entry, i.e., $b_{i_0j_0}\gt0$ and $b_{i_0j_1}\gt0$ for some $i_0$ and $j_0\neq j_1$. Again, there is an $i_1$ such that $a_{i_1i_0}\gt0$, and we have $c_{i_1j_0}\geq a_{i_1i_0}b_{i_0j_0}\gt0$ and $c_{i_1j_1}\geq a_{i_1i_0}b_{i_0j_1}\gt0$, so again $AB\neq I$. A similar argument applies if $B$ has a column with more than one nonzero entry, either by multiplying in the other order, or by considering the transpose. Thus in either case $B$ is not invertible.

This leaves only the case that $B$ has a zero row or column, in which case it is even a zero divisor. Thus in any case, $B$ is not invertible.