Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
+1 for the nice basis. – user1551 Oct 7 '11 at 19:12
Yes, thanks for the nice basis. – Barry Smith Oct 10 '11 at 1:14

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.