Linearly independent subgroups of permutation matrices Let $k$ be a field and $M$ the subgroup of $\operatorname{GL}(n,k)$ consisting of permutation matrices. We say a subgroup $G$ of $M$ linearly independent if $G$ is a linearly independent subset of $M_n(k)$. It is well-known that there is an isomorphism between $M$ and the full symmetric group $S_n$ with respect to the canonical basis of the affine $n$-dimensional space $k^n$, I identify them in this way. It is clear that any subgroup of a regular subgroup of $S_n$ is linearly independent. Is there a full description of all linearly independent subgroups of $S_n$?
 A: This just deals with the complex case: Here is an initial remark: Since we know that the character afforded by the natural permutation representation of $S_{n}$ is the sum of the trivial character an a degree $n-1$ irreducible, we know that the $n \times n$ permutation matrices span a space of dimension $1+(n-1)^{2}.$ Hence this is an upper bound for the order of a subgroup $H$ consisting of permutation matrices which are irreducible.  But this upper bound can never be attained if $n >2$. If it were, then the $n-1$-dimensional representation of $S_{n}$ would have to remain  irreducible on restriction to $H$, so that $|H|$ would have order divisible by $n-1$, so making $|H| = 1 +(n-1)^{2}$ impossible.
But now $|H| = (n-1)^{2}$ is also impossible for $n >2$, since if $|H| = (n-1)^{2} >1$, $H$ can have no complex irreducible character of degree $n-1$, as such a character would be non-trivial. Thus $H| < (n-1)^{2}$ when $n >2$.
Now it is easy to check via character theory that $|H| \leq 2 + (n-2)^{2}$ when $n >2$,  and this can only occur if the restriction of the degree $n-1$ irreducible character to $H$ decomposes as the sum of an irreducible of degree $n-2$ and an irreducible of degree $1$.
This upper bound can be attained for $n = 3$ with $H \cong A_{3}.$ But the bound can only be attained for $n \leq 4$ since equality forces both $(n-2) | |H|$ and $(n-2) | 2.$ However, even the case $n = 4$, it is not difficult to check that the upper bound of $6$ is not attained.
Thus we have $|H| \leq  1 +(n-2)^{2}$ if $n > 3.$ I am not sure if there is a systematic way to improve this bound for larger $n$.
