# Minimal generating sets of monoids acting on finite vector spaces.

Let $V$ be a finite dimensional vector space over $\mathbb{Z}_2$ with a linear map $f_i : V \to V$ for each $i$ in some finite index set $I$.

Then one can always find some subset $G \subseteq V$ of minimal cardinality such that the set of all elements:

$f_{i_1} \circ \dots \circ f_{i_n}(g)$ where $g \in G$, $i_j \in I$ and $n \geq 0$

spans the vector space $V$. Likewise in the dual situation $(V^*,(f_i^*)_{i \in I})$ there is some respective minimal generating set $G' \subseteq V^*$.

Here are my questions:

1. How does the cardinality of $G'$ compare to that of $G$?

2. What if each $f_i$ is assumed to be idempotent?

Any help much appreciated.

## 1 Answer

Things can differ as much as you like even if all maps are idempotents. Let F be any field. Let M be the monoid of all constant maps on {1,...n} (acting on the left) together with the identity. In otherwords, M has n left zeroes and an identity. Let V be the regular left FM-module. It is a cyclic module generated by the identity of M.

Consider the dual module V*. It can be identified with the mappings $M\to F$ with right FM-module structure given by (fm)(x)=f(mx). In particular, if m is not the identity map, then fm is a constant map. Thus V*/constants is an n-dimensional module annihilated by all non-zero elements of M and hence cannot be generated by fewer than n elements (that is, a basis). Thus V* cannot be generated by fewer than n elements.

• Thanks. Let me make the question more specific. For any n \geq 0, consider the finite monoid M with generators m_ij, for i \in n, j = 1,2, and relations (i) m_ij . m_ik = m_ik and (ii) m_ij . m_rs = m_rs . m_ij whenever i \neq r. Each generator is idempotent and commutes with all but one other, where it acts as a right zero. The free Z_2 M-module on k vectors has |G| = k, in the sense of the question. However its dual appears to have |G'| \geq 2^n * k. Are there any known conditions on such modules that force e.g. |G'| \leq |G| or similar? I'm sorry if this is too specific. – Rob Myers Feb 4 '13 at 15:00
• Notice V**=V so you can't have inequalities in general without equality. Most likely the dual of a free module will require many generators if the semigroup is very far from being isomorphic to its reversal or if it does not have a semisimple algebra. I think an argument like mine above will show that the dual of your free modules requires many generators. To many left or right zeroes means the dual is very different than the predual. – Benjamin Steinberg Feb 4 '13 at 16:42