# The relation between quasi-permutation matrix and permutation matrix?

We know that a quasi-permutation matrix is a square matrix over the complex numbers with non-negative integral trace.

Can anyone tell me why it is called "quasi-permutation matrix"? Is there any relation between quasi-permutation matrix and permutation matrix?

• A permutation matrix satisfies the definition of a quasi-permutation matrix, since the entries of a permutation are zeros and ones. Obviously the converse is not true, so the quasi-permutation matrices are a richer setting for finite groups to have matrix representations. Are you with me so far? – hardmath Mar 14 '16 at 12:02
• @ hardmath Your word is right. But I think there maybe something special between quasi-permutaion matrix and permutation matrix. Maybe it's just a name ,so-so. – Xiaosong Peng Mar 14 '16 at 14:23

## 1 Answer

Perhaps the best way to appreciate the choice of terminology is by looking back at the 1962 paper Linear groups analogous to permutation groups by W.J. Wong, where the concept is introduced:

If $G$ is a finite linear group of degree $n$, that is, a finite group of automorphisms of an $n$-dimensional complex vector space (or, equivalently, a finite group of non-singular matrices of order $n$ with complex coefficients), I shall say that $G$ is a quasi-permutation group if the trace of every element of $G$ is a non-negative rational integer. The reason for this terminology is that, if $G$ is a permutation group of degree $n$, its elements, considered as acting on the elements of a basis of an $n$-dimensional complex vector space $V$, induce automorphisms of $V$ forming a group isomorphic to $G$. The trace of the automorphism corresponding to an element $x$ of $G$ is equal to the number of letters left fixed by $x$, and so is a non-negative integer. Thus, a permutation group of degree $n$ has a representation as a quasi-permutation group of degree $n$.

Although stated slightly differently than I did in my Comment, it provides the same essential justification for the terminology, anticipating that this more general framework for finite group representations (linear = using matrices) may share some nice properties with permutation groups.

Wong next states two properties of a permutation group $G$ of degree $n$:

• The order $|G|$ is a divisor of $n!$

• If $p$ is a prime number exceeding $\sqrt{n}$, then the Sylow $p$-subgroup of $G$ is of elementary Abelian type.

The rest of the paper basically proves analogous statements about quasi-permutation groups:

Theorem $1.\;\;$ The order of a quasi-permutation group $G$ of degree $n$ is a divisor of $n!$

Theorem $2.\;\;$ The Sylow $p$-group of a quasi-permutation group of degree $n$ smaller than $p^2$ is of elementary Abelian type.

The closing paragraph of that paper summarizes the two results as showing that "any $p$-group which can be represented as a quasi-permutation group of degree $n$ can also be represented as a permutation group of degree n, provided that $p^2 \gt n$." The paragraph then notes that the condition $p^2 \gt n$ cannot be omitted by giving the example of the quaternion group of order $8$, which has a representation as a quasi-permutation group of degree $4$, but none as a permutation group of degree $4$.

One might read this example as suggesting that generalizing to quasi-permutation groups allows for representations of smaller degree than permutation groups do, while still providing concrete opportunities for investigation. Much of the subsequent research literature has compared the minimal degree $p(G)$ of a (faithful) representation of certain finite groups $G$ by permutation groups with the minimal degree $c(G)$ by quasi-permutation groups. The introductory fact that permutation groups are quasi-permutation groups implies $c(G) \le p(G)$.

Finally we note that quasi-permutation group has to be understood in a slightly more permissive (artful?) spirit than permutation group is. The product of two compatible sized permutation matrices is again a permutation matrix, but the product of two quasi-permutation matrices need not be a quasi-permutation matrix (though it will be a posteriori if both are elements of a quasi-permutation group). For example:

$$\begin{pmatrix} 0 & i \\ i & 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} i & 0 \\ 0 & i \end{pmatrix}$$

This last has trace $2i$, not an non-negative integer, so it is not a quasi-permutation matrix despite being the product of two quasi-permutation matrices.

• @ hardmath Thank you very much. I get some things about quasi-permutation matrix. – Xiaosong Peng Mar 28 '16 at 1:31
• the trace of a permutation matrix is equal to the number of vector elements whose position/order remains unchanged – phdmba7of12 Feb 20 at 12:23
• @phdmba7of12: Yes, this is mentioned in the paragraph I quote above, from the paper by W. J. Wong (1962) which introduced the notion of quasi-permutation groups. – hardmath Feb 21 at 1:46