Permutation matrix; an alternative view

Posted: February 17, 2024 in Basic Algebra, Matrices
Tags: permutation matrix

As always, in this post, we denote by $\text{GL}(n,k)$ the group of $n \times n$ invertible matrices with entries from a field $k.$ Also, $A^T$ is the transpose of a matrix $A.$

Here we defined a permutation matrix as an $n \times n$ matrix $A$ such that $Ae_i=e_{\sigma(i)}$ for some $\sigma \in S_n$ and all positive integers $i \le n,$ where $\{e_1, \cdots , e_n\}$ is the standard basis of the $\mathbb{R}$ -vector space $\mathbb{R}^n$ and $S_n$ is the group of permutations of the set $\{1, 2, \cdots , n\}.$ In other words, an $n \times n$ permutation matrix is a matrix whose columns are exactly $e_1, \cdots , e_n$ in any order. Equivalently, a permutation matrix is a matrix $A$ with this property that every row or column of $A$ has exactly one nonzero entry and that nonzero entry is $1.$ For example, for $n=2,$ we have exactly two permutation matrices: $\begin{pmatrix}1 & 0 \\ 0 & 1\end{pmatrix}, \begin{pmatrix}0 & 1 \\ 1 & 0\end{pmatrix}.$

In this post, we give another way to view a permutation matrix. The following problem was recently posted on the Art of Problem Solving website; here you can see the problem and my solution (post #7). I’m going to rephrase the statement of the problem and also make my solution a little bit more clear.

Problem. Show that $A \in \text{GL}(n,\mathbb{R})$ is a permutation if and only if all the entries of $A$ and $A^{-1}$ are in $\{0,1\}.$

Solution. One side is clear: if $A$ is a permutation matrix, then $A$ is invertible and all the entries of $A$ and $A^{-1}$ are in the set $\{0,1\}.$
Suppose now that $A \in \text{GL}(n,\mathbb{R})$ and all the entries of $A, A^{-1}$ are in $\{0,1\}.$ Let $I$ be the $n \times n$ identity matrix, and let $a_{ij}, b_{ij}, c_{ij}$ be, respectively, the $(i,j)$ -entry of $A,A^{-1},I.$ Choose any positive integer $i \le n.$ Since $AA^{-1}=I$ and $c_{ii}=1,$ there exists a positive integer $m \le n$ such that $a_{im}=b_{mi}=1.$ If $a_{ij}=1$ for some $j \ne m,$ then, since $A^{-1}A=I,$ we’ll get

$0=c_{mj}=b_{mi}a_{ij}+ \cdots =1 + \cdots \ne 0,$

which is a contradiction. So $a_{ij}=0$ for all $j \ne m.$ We have shown that in every row of $A,$ all the entries except for one, which is $1,$ are zero. Now, we also have that all the entries of $A^T$ and $(A^T)^{-1}$ are in $\{0,1\}$ because $(A^T)^{-1}=(A^{-1})^T.$ Therefore repeating the above argument this time for $A^T$ shows that in every column of $A,$ all the entries except for one, which is $1,$ are zero, and hence $A$ is a permutation. $\ \Box$