If $A$ is a permutation matrix, then why is $A^{T}A=I$? If $A$ is a permutation matrix, then why is $A^{T}A=I$?
I tried this on a couple of examples to convince myself, but I am not able to come up with a rigorous justification of this fact. 
The way I see it is as follows. If $A$ is a permutation matrix then so it $A^{T}.$ Now applying $A^{T}$ on the left will permute the rows, whereas applying $A^{T}$ on the right would have permuted the columns of $A.$ In this case, we are concerned with a permutation of the columns. So image we have a matrix $B$ and we try to compute $A^{T}AB,$ then first we will permute the columns of $B$ according to the permutation represented by $A$ and then we would permute the columns again according to the permutation $A^{T}.$ What I don't see clearly is why must $A^{T}$ somehow undo the column permutations of $A?$
Any insights would be much appreciated. 
 A: Well, if $A\in \mathcal{M}_{n}(\mathbf{R})$ then we know that the columns of such a permutation matrix form an orthnormal basis for $\mathbf{R}^n$. So, $A$ is orthogonal and $A^TA=I_n$ by a standard fact about orthogonal matrices. To see why this is the case, observe that $A^TA$ corresponds to dotting each column of $A$ with another column of $A$. By orthonormality, $A^TA$ returns the identity matrix.
For example, take 
$$ A=\begin{bmatrix}
1&0&0\\
0&0&1\\
0&1&0
\end{bmatrix}.$$
$$ A^TA=
\begin{bmatrix}
1&0&0\\
0&0&1\\
0&1&0
\end{bmatrix}\begin{bmatrix}
1&0&0\\
0&0&1\\
0&1&0
\end{bmatrix}=I_3.$$
A: Permutation matrices are orthogonal matrices, so $P^T = P^{-1}$ and the effect of a permutation $P$ is reversed by $P^T$.
A: $\newcommand{\ip}[2]{\langle #1,#2\rangle}$
Since $Ax$ is just a permutation of the entries of $x$ it's clear that$$\ip{Ax}{Ay}=\ip xy.$$
By definition of $A^T$ this says $$\ip{A^TAx}{y}=\ip xy$$for all $x,y$;  hence $A^TAx=x$.
A: Here is an argument which relies only on the definition of permutation matrices and matrix multiplication. If we denote the $(i,j)$th element of $A$ by $a_{ij},$ then the $(i,j)$th of $A^T A$ is given by
$$
\sum_{j=1}^n a_{ki} \, a_{kj}.
$$
For a permutation matrix and any $j$ there is a single $i$ such that the $(i,j)$th entry is non-zero (in fact, equal to $1$). From this you see that 
$$
\sum_{j=1}^n a_{ki} \, a_{kj} = 0
$$
if $i\neq j,$
and 
$$
\sum_{j=1}^n a_{ki} \, a_{kj} = 1
$$
if $i= j.$
