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 Birkhoff–von Neumann theorem states that the convex hull of permutation matrices is the set of all doubly stochastic matrices. Hence the span of all permutation matrices is given by $S=\{X\in M_{n,n}(\mathbb{C}): \textrm{ all column sums and row sums of } X \textrm{ are equal}\}$.
