Proof that $A\in M_{n\times n}\mathbb{R}$ is a permutation matrix if and only if it is the product of elementary matrices of type $P_{ij}$.

Question

We define a permutation matrix $A\in M_{n\times n}\mathbb{R}$ as a matrix that has all its coefficients 0 except from a 1 in each row and each column. Then, proof that $A\in M_{n\times n}\mathbb{R}$ is a permutation matrix if and only if it is the product of elementary matrices of type $P_{ij}$.

Answer 1

I would answer this way. First, show that the set $S$ of permutation matrices is a subgroup of $GL_n$ (it is not hard to prove it). Then, for $M \in S$, let $\sigma$ be the unique permutation on $\{1,\ldots,n\}$ such that $M_{i,j} = \delta_{i,\sigma(j)}$ where $\delta$ stands for the Kronecker symbol. You can show $\sigma$ exists by constructing it : $\sigma(j)$ is the rank of the only line for which there is a $1$ at the $j$-th place. Now, show that $M \in S \mapsto \sigma \in\mathfrak{S}_n$ is a group homomorphism. It is surjective (as you can construct the desired matrix for a chosen $\sigma$ by the formula above) and for cardinality reasons, it will be an isomorphism. Thus, the results is the same as saying that $\mathfrak{S}_n$ is generated by transpositions, which is true.