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.

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}$.


share|improve this question
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)$. –  Arturo Magidin Dec 31 '10 at 22:35
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. –  Michaël Cadilhac Jan 1 '11 at 16:29
The new question: math.stackexchange.com/questions/16038/… –  Jonas Meyer Jan 1 '11 at 23:09
add comment

2 Answers

up vote 6 down vote accepted

(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.)

share|improve this answer
@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. –  Arturo Magidin Dec 31 '10 at 22:02
Ah, sorry, I misread the question. –  Qiaochu Yuan Dec 31 '10 at 22:14
@Qiaochu: It must contain $0$, otherwise there is no identity (hence no monoid)... –  Arturo Magidin Dec 31 '10 at 22:22
@Arturo: I think the only elements of finite order are permutations. Does that sound reasonable to you? –  Qiaochu Yuan Jan 1 '11 at 3:01
@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. –  Arturo Magidin Jan 1 '11 at 3:59
show 1 more comment

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.

share|improve this answer
Thanks for your answer Jonas! –  Michaël Cadilhac Jan 1 '11 at 16:31
add comment

Your Answer


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.