Span of permutation matrices

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.