$\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?
I found a sufficiently nice characterisation of permutation matrices:
Proof: That permutation matrices are non-negative and orthogonal is clear.
Conversely, let $\mathbf P$ be a non-negative matrix with $\mathbf P^{\mathsf T}\mathbf P=\mathbf I$. Each row and column of $\mathbf P$ must contain at least one non-zero entry, otherwise $\mathbf P^{\mathsf T}\mathbf P \neq \mathbf I$ since the product will have a column of zeros.
Now suppose two entries of $\mathbf P$ in the $i$th row are non-zero, say $p_{ij}$ and $p_{ij'}$ where $j\neq j'$. But then the entry in the $jj'$th position in $\mathbf P^{\mathsf T}\mathbf P$ will not be zero, a contradiction. A similar argument yields the corresponding fact for columns.
Finally, suppose one of the non-zero entries of $\mathbf P$ is not equal to $1$, say in the $ij$th position. Then the entry in the $jj$th position of $\mathbf P^{\mathsf T}\mathbf P$ is $\sum_{k=1}^n p_{kj}^2 = p_{ij}^2 \neq 1$, a contradiction.