# Is a monoid finitely generated by periodic matrices periodic?

This question is somewhat linked to this one -- in fact, I meant to ask the following:

Let $\mathcal{M}_n$ be the multiplicative monoid of $n \times n$ matrices on $\mathbb{N}$ (including $0$). Let $M_1, \ldots, M_k \in \mathcal{M}_n$ and suppose the monoid generated by each one of them is finite. Is the monoid generated by all of them periodic (i.e. such that any of its elements generates a finite monoid)?

I hope I got it right this time. Sorry for the noise.
Thanks!

-
Well, this is why I posted a new question: generating a finite monoid is different from being of finite order. For instance, $\left(\begin{array}{cc}1&0\\1&0\end{array}\right)$ or $\left(\begin{array}{cc}0&2\\0&0\end{array}\right)$ both generate finite monoids. – Michaël Cadilhac Jan 1 '11 at 17:02
Ah, right. My mistake. – Qiaochu Yuan Jan 1 '11 at 17:03

In fact, using the two examples in your comment provides a counterexample.

Let $A = \begin{bmatrix} 1 & 0\\1&0\end{bmatrix}$ and $B = \begin{bmatrix}0&2\\0&0 \end{bmatrix}$.

As you mention, $A^2 = \begin{bmatrix} 1 & 0 \\ 1 & 0\end{bmatrix}$ so $A$ generates a finite monoid. Likewise, $B^2$ is the $0$ matrix so this generates a finite monoid.

However, the monoid generated by $A$ and $B$ is not periodic: the element $BA = \begin{bmatrix} 2 & 0 \\ 0 & 0\end{bmatrix}$ doesn't generate a finite monoid since $(BA)^n = \begin{bmatrix} 2^n & 0\\ 0 & 0\end{bmatrix}$, which is distinct for each $n$.

-
Haha, yes, I thought about that a few minutes later, while in the car :) That's really silly of me! Thank you, Jason! – Michaël Cadilhac Jan 2 '11 at 6:26

More generally, for any $n\gt 1$, the matrices $$A=\left(\begin{array}{cccc} 1 & 0 & \cdots & 0\\ 1 & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 0 & \cdots & 0 \end{array}\right)\quad\text{and}\quad B=\left(\begin{array}{cccc} 1 & 1 & \cdots & 1\\ 0 & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & 0 \end{array}\right)$$ are each idempotent, so they each generate a finite monoid, but neither $$AB = \left(\begin{array}{cccc} 1 & 1 & \cdots & 1\\ 1 & 1 & \cdots & 1\\ \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & \cdots & 1 \end{array}\right)\quad\text{nor}\quad BA = \left(\begin{array}{cccc} n & 0 & \cdots & 0\\ 0 & 0 & \cdots & 0\\ \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & \cdots & 0 \end{array}\right)$$ are periodic.

-
Ah, right, thank you! – Michaël Cadilhac Jan 2 '11 at 6:26

Let $A$ be an element of $\mathcal{M}_n$ such that $A$ is periodic. Then $A^\mathrm{T}$ is also periodic. However, $AA^\mathrm{T}$ is periodic if and only if each nonzero entry of $A$ is $1$ and each row and column of $A$ has at most one nonzero entry.

Suppose $A=(a_{ij})$ and $a_{i_0j_0}\gt1$ for some $i_0$ and $j_0$. If $AA^\mathrm{T}=(b_{ij})$, then $b_{i_0i_0}\geq a_{i_0j_0}^2\gt1$. In particular this implies that the Euclidean norm of $AA^\mathrm{T}e_{i_0}$ is greater than $1$, where $e_{i_0}$ is the $i_0^\text{th}$ standard basis vector. Since $AA^\mathrm{T}$ is positive semidefinite, this implies that its spectral radius is greater than $1$, and therefore its powers have unbounded spectral radius.

Suppose that $a_{i_0j_0}\gt0$ and $a_{i_0j_1}\gt0$ for some $i_0$ and $j_0\neq j_1$. Then $b_{i_0i_0}\geq a_{i_0j_0}^2+a_{i_0j_1}^2\gt1$, which again implies that the powers of $AA^\mathrm{T}$ have unbounded spectral radius.

Suppose that $a_{i_0j_0}\gt0$ and $a_{i_1j_0}\gt0$ for some $i_0\neq i_1$ and $j_0$. Then $b_{i_0i_0}\geq a_{i_0j_0}^2\gt0$ and $b_{i_1i_0}\geq a_{i_1j_0}a_{i_0j_0}\gt0$. This implies that the Euclidean norm of $AA^\mathrm{T}e_{i_0}$ is at least $\sqrt{2}$. Thus, again, the powers of $AA^\mathrm{T}$ have unbounded spectral radius.

On the other hand, if each nonzero entry of $A$ is $1$ and each row and column of $A$ has at most one nonzero entry, then $AA^\mathrm{T}$ is idempotent.

-
That's really nice, thank you very much! – Michaël Cadilhac Jan 2 '11 at 6:27