Span of permutation matrices The set $P$ of $n \times n$ permutation matrices spans a subspace of dimension $(n-1)^2+1$ within, say, the $n \times n$ complex matrices.  Is there another description of this space?  In particular, I am interested in a description of a subset of the permutation matrices which will form a basis.
For $n=1$ and $2$, this is completely trivial -- the set of all permutation matrices is linearly independent.  For $n=3$, the dimension of their span is $5$, and any five of the six permutation matrices are linearly independent, as can be seen from the following dependence relation:
$$ \sum_{M \in P} \det (M) \ M = 0 $$
So even in the case $n=4$, is there a natural description of a $10$ matrix basis?

The set of permutation matrices indexed by the permutations having an increasing subsequence of length $n-1$ is a basis. This set is the same as the set of consecutive cycles, that is, permutations of $n$ that consecutively cycle a set of consecutive numbers. For example, $3 \mapsto 4 \mapsto 5 \mapsto 3$ is a consecutive cycle (as is its inverse) but $3 \mapsto 5 \mapsto 6 \mapsto 3$ is not.
This result is proved, and vastly generalized, in  https://arxiv.org/abs/2109.00107.
