<p><strong>Background</strong></p>

<p>I was looking for a formulation of 'free sets' and 'independent sets' from linear algebra that would extend to groups. This question was considered <a href="http://www-circa.mcs.st-and.ac.uk/Theses/jdmphd.pdf%E2%80%8E" rel="nofollow">here</a> but I couldn't find a satisfactory definition in the literature so I'd like to suggest the following simple approach. Let $G$ be a finite group, and for each $x \in G$ let $o(x)$ denote its order, i.e. the smallest positive integer $p$ such that $x^p = 1_G$.</p>

<p><strong>Core definitions</strong></p>

<p>Let $X = \{x_1,\ldots,x_k\}$ be a $k$-subset of $G$ and let $A_k = \{a_1,\ldots,a_k\}$ be the $k$-letter alphabet. Let $\Sigma_k$ denote the free monoid generated by $A_k$, and let $\Pi_k = \prod_{i \in [k]} \mathbb{Z}_{o(x_i)}$ viewed as an abelian group. Consider the homomorphism $\phi_k : \Sigma_k \rightarrow G$ that maps each $a_i$ to $x_i$, and consider the homomorphism $\psi_k : \Sigma_k \rightarrow \Pi_k$ defined by $(\psi_k(w))_i = |w|_{a_i}$. We can then give the following definitions:</p>

<p>(1) $X$ is a 'generating set' of $G$ if $\phi_k$ is surjective;</p>

<p>(2) $X$ is a 'free set' of $G$ if there exists an homomorphism $\eta_k : Im(\phi_k) \rightarrow \Pi_k$ such that $\psi_k = \eta_k \circ \phi_k$.</p>

<p>We observe that some properties from linear algebra carry over to this setting. For instance, any superset of a generating set is also generating, and any subset of a free set is also free. We may then define a 'free generating set' of $G$ the obvious way. Note that such a set may not exist, but when $G$ does admit a fgs we may define $rank(G)$ as the cardinality of this set.</p>

<p><strong>Basic remarks</strong> </p>

<p>Similar to linear algebra, it turns out that two fgs always have the same cardinality. Here is a proof sketch for a special case. Suppose for contradiction that $G$ had two fgs $X,Y$ with $k = |X| &lt; |Y| = l$, and suppose <em>for simplicity</em> that each element of $X \cup Y$ has the same order $p$. Consider the surjective mapping $\phi_k : \Sigma_k \rightarrow G$ obtained from $X$, and the surjective mapping $\phi_l : \Sigma_l \rightarrow G$ obtained from $Y$. As $Y$ is free, we obtain an homomorphism $\eta_l$ by (2).</p>

<p>Given an element $x_i \in X$, there is a word $w_i \in \Sigma_l$ such that $\phi_l(w_i) = y_i$. Define the $k \times l$-matrix $M$ by $M_{i,j} = \eta_l(x_i)[j] = |w_i|_{a_j} \mod p$. For every $z \in G$, we can then write $\eta_l(z)$ as a combination of the column vectors of $M$. It follows that the image of the $\eta_l$ must be included in the subspace spanned by $M$ and thus has size at most $p^k$; therefore $\eta_l$ cannot be surjective contradicting the assumption that $Y$ is free.</p>

<p>Some examples follow. For a finite abelian group $G$, we know that it is isomorphic to a product $\mathbb{Z}_{n_1} \times \ldots \times \mathbb{Z}_{n_k}$ and then $rank(G) = k$. For the permutation group $S_n$, it can be seen that $rank(S_n) = n-1$ as the transpositions form a free generating set; indeed, for a permutation $\pi \in S_n$ we can define a tuple $\eta(\pi) = (s_1,\ldots,s_{n-1}) \in \mathbb{Z}_2^{n-1}$, where $s_i = 0$ if $\pi(i) &lt; \pi(i+1)$ and $s_i = 1$ otherwise. More generally, if $G \subseteq S_n$ is a permutation group, I conjecture that a free generating set can be obtained by the Schreier-Sims algorithm.</p>

<p><strong>Questions</strong></p>

<ol>
<li><p>is it possible to adapt the above proof to handle distinct orders? if so, what part of linear algebra carries over to this setting?</p></li>
<li><p>if we can compute the rank for permutation groups as suggested above, are there other, presumably infinite, groups for which this is doable efficiently?</p></li>
<li><p>are there any algorithmic applications of this notion to problems involving graphs or permutations?</p></li>
</ol>

CC BY-SA 3.0
2014-04-04T14:53:52.233Z
Your questions are full of potentially interesting content: but they would be easier to read if you added structure: divided them into sections (e.g. `## Motivation`, `## Question`), used numbered lists, etc. Check out the formatting hints accessible by clicking on the yellow-orange `?` icon at the upper-right of your input form for questions.
Niel de Beaudrap
CC BY-SA 3.0
2014-04-04T16:33:08.570Z
@NieldeBeaudrap: thanks for the advice. I have noticed an error in my question, it doesn't seem correct that two fgs have the same size, although I don't have a counterexample yet... I will update the question once I've sorted out these issues.
NisaiVloot
CC BY-SA 3.0
2014-04-05T02:09:30.903Z
Can you summarize what is the difference of your proposed definition from matroids?
Tegiri Nenashi
CC BY-SA 3.0
2014-04-05T02:13:41.480Z
Well, matroids are an *abstract* generalization while I propose a *concrete* generalization. They're probably not comparable though: assuming that my definition of independence makes sense, I don't think that it satisfies the exchange property of matroids.
NisaiVloot
<algebra><gr.group-theory>
Extending the notion of independence
NisaiVloot
# Extending the notion of independence

(Asked by: username_0 on 2014-04-04)

**Background**

I was looking for a formulation of 'free sets' and 'independent sets' from linear algebra that would extend to groups. This question was considered [here](http://www-circa.mcs.st-and.ac.uk/Theses/jdmphd.pdf%E2%80%8E) but I couldn't find a satisfactory definition in the literature so I'd like to suggest the following simple approach. Let $G$ be a finite group, and for each $x \in G$ let $o(x)$ denote its order, i.e. the smallest positive integer $p$ such that $x^p = 1\_G$.

**Core definitions**

Let $X = \{x\_1,\ldots,x\_k\}$ be a $k$-subset of $G$ and let $A\_k = \{a\_1,\ldots,a\_k\}$ be the $k$-letter alphabet. Let $\Sigma\_k$ denote the free monoid generated by $A\_k$, and let $\Pi\_k = \prod\_{i \in [k]} \mathbb{Z}\_{o(x\_i)}$ viewed as an abelian group. Consider the homomorphism $\phi\_k : \Sigma\_k \rightarrow G$ that maps each $a\_i$ to $x\_i$, and consider the homomorphism $\psi\_k : \Sigma\_k \rightarrow \Pi\_k$ defined by $(\psi\_k(w))\_i = |w|\_{a\_i}$. We can then give the following definitions:

(1) $X$ is a 'generating set' of $G$ if $\phi\_k$ is surjective;

(2) $X$ is a 'free set' of $G$ if there exists an homomorphism $\eta\_k : Im(\phi\_k) \rightarrow \Pi\_k$ such that $\psi\_k = \eta\_k \circ \phi\_k$.

We observe that some properties from linear algebra carry over to this setting. For instance, any superset of a generating set is also generating, and any subset of a free set is also free. We may then define a 'free generating set' of $G$ the obvious way. Note that such a set may not exist, but when $G$ does admit a fgs we may define $rank(G)$ as the cardinality of this set.

**Basic remarks**

Similar to linear algebra, it turns out that two fgs always have the same cardinality. Here is a proof sketch for a special case. Suppose for contradiction that $G$ had two fgs $X,Y$ with $k = |X| < |Y| = l$, and suppose *for simplicity* that each element of $X \cup Y$ has the same order $p$. Consider the surjective mapping $\phi\_k : \Sigma\_k \rightarrow G$ obtained from $X$, and the surjective mapping $\phi\_l : \Sigma\_l \rightarrow G$ obtained from $Y$. As $Y$ is free, we obtain an homomorphism $\eta\_l$ by (2).

Given an element $x\_i \in X$, there is a word $w\_i \in \Sigma\_l$ such that $\phi\_l(w\_i) = y\_i$. Define the $k \times l$-matrix $M$ by $M\_{i,j} = \eta\_l(x\_i)[j] = |w\_i|\_{a\_j} \mod p$. For every $z \in G$, we can then write $\eta\_l(z)$ as a combination of the column vectors of $M$. It follows that the image of the $\eta\_l$ must be included in the subspace spanned by $M$ and thus has size at most $p^k$; therefore $\eta\_l$ cannot be surjective contradicting the assumption that $Y$ is free.

Some examples follow. For a finite abelian group $G$, we know that it is isomorphic to a product $\mathbb{Z}\_{n\_1} \times \ldots \times \mathbb{Z}\_{n\_k}$ and then $rank(G) = k$. For the permutation group $S\_n$, it can be seen that $rank(S\_n) = n-1$ as the transpositions form a free generating set; indeed, for a permutation $\pi \in S\_n$ we can define a tuple $\eta(\pi) = (s\_1,\ldots,s\_{n-1}) \in \mathbb{Z}\_2^{n-1}$, where $s\_i = 0$ if $\pi(i) < \pi(i+1)$ and $s\_i = 1$ otherwise. More generally, if $G \subseteq S\_n$ is a permutation group, I conjecture that a free generating set can be obtained by the Schreier-Sims algorithm.

**Questions**

1. is it possible to adapt the above proof to handle distinct orders? if so, what part of linear algebra carries over to this setting?
2. if we can compute the rank for permutation groups as suggested above, are there other, presumably infinite, groups for which this is doable efficiently?
3. are there any algorithmic applications of this notion to problems involving graphs or permutations?

**Tags:** algebra, gr.group-theory

> **Comments:**
> **username_1**: Your questions are full of potentially interesting content: but they would be easier to read if you added structure: divided them into sections (e.g. `## Motivation`, `## Question`), used numbered lists, etc. Check out the formatting hints accessible by clicking on the yellow-orange `?` icon at the upper-right of your input form for questions.  
> **username_0**: @NieldeBeaudrap: thanks for the advice. I have noticed an error in my question, it doesn't seem correct that two fgs have the same size, although I don't have a counterexample yet... I will update the question once I've sorted out these issues.  
> **username_2**: Can you summarize what is the difference of your proposed definition from matroids?  
> **username_0**: Well, matroids are an *abstract* generalization while I propose a *concrete* generalization. They're probably not comparable though: assuming that my definition of independence makes sense, I don't think that it satisfies the exchange property of matroids.  

---

## 0 answers

