$\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?

  • $\begingroup$ 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. $\endgroup$ – Omnomnomnom Mar 12 at 18:56
  • $\begingroup$ @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. $\endgroup$ – Luke Collins Mar 12 at 18:57
  • $\begingroup$ Your geometric characterization is correct. Not quite sure how to describe them "in the form of an equation", as you'd like to $\endgroup$ – Omnomnomnom Mar 12 at 18:59
  • $\begingroup$ Mostly because I would like to prove some properties about the adjacency matrices of graphs, and I need to work with permutation matrices. $\endgroup$ – Luke Collins Mar 12 at 19:03
  • 1
    $\begingroup$ Relevant: math.stackexchange.com/questions/322514/… $\endgroup$ – Dap Mar 12 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.