# Characterisation of Permutation Matrices

$$\newcommand\mat{\mathbf}$$A permutation matrix is a matrix whose columns are a permutation of the columns of the identity matrix $$\mat I$$. In other words, a permutation matrix is a matrix $$\mat P$$ with precisely one $$1$$ per row/column and zeros everywhere else.

A few easy observations about permutation matrices are:

• $$\mat P^{-1} = \mat P^\mathsf{T}$$ (orthogonality)
• $$\mat P\mat 1 = \mat P^\mathsf{T}\mat1= \mat 1$$ (doubly stochastic), where $$\mat 1 = (1,\dots,1)$$ is the all-ones vector
• Eigenvalues are $$e^{2i\pi k/n}$$ for $$k=1,\dots,n$$, where $$n$$ is the least positive integer such that $$\mat P^n = \mat I$$.

But I don't think these three properties suffice to characterise permutation matrices, and the latter two aren't too nice to work with anyway. Is there a nice set of equations one can work with which completely capture the behaviour of permutation matrices?

• Along the lines of Birkhoff's theorem, you could say that the permutation matrices are the extreme points of the set of doubly-stochastic matrices. – Omnomnomnom Mar 12 at 18:56
• @Omnomnomnom Yes I've read about that theorem in pursuit of a characterisation, but how can I encapsulate what it says in the form of an equation? In a geometric sense, I believe one can see the set of doubly stochastic matrices as the convex hull of the polytope made up of the set of permutation matrices. – Luke Collins Mar 12 at 18:57
• Your geometric characterization is correct. Not quite sure how to describe them "in the form of an equation", as you'd like to – Omnomnomnom Mar 12 at 18:59
• Mostly because I would like to prove some properties about the adjacency matrices of graphs, and I need to work with permutation matrices. – Luke Collins Mar 12 at 19:03
• – Dap Mar 12 at 20:19