# 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?

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.

• Yes, thanks for the nice basis. Commented Oct 10, 2011 at 1:14
• Why the basis is linearly independent? I don't see it by considering the first row and first column. Commented Jun 22, 2018 at 15:31
• When you speak of $M_{n-1}(\mathbb{C})$ are you speaking of the list of all matrices under the Lie bracket? Thank you. Commented Mar 24, 2021 at 13:47

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

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.