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?

Solutions Collecting From Web of "Span of Permutation Matrices"

As user1551 points out, your space is the span of all “magic matrices” — all $n\times n$ matrices for which every row and column sum is equal to the same constant (depending on the matrix). As an algebra this is isomorphic to $\mathbb{C} \oplus M_{n-1}(\mathbb{C})$.

You can think of this as the image in $\operatorname{End}_{\mathbb{C}}(\mathbb{C}^n)$ of the natural representation of $S_n$ on $n$ points — perhaps this is where your question comes from. The representation decomposes as the direct sum of the trivial rep and an $(n-1)$-dimensional irreducible.

The set of permutation matrices coming from the permutations $1$, $(1,r)$, $(1,r,s)$ for $1\neq r \neq s \neq 1$ form a basis of this space. To see that they are linearly independent, consider the first rows then the first columns of the corresponding matrices.

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}\}$.