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 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!

share|improve this question
    
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

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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.

share|improve this answer
    
That's really nice, thank you very much! –  Michaël Cadilhac Jan 2 '11 at 6:27

Your Answer

 
discard

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.