Why do the squared permanents sum to 1? Consider an  $n^2$ by $n^2$ real orthogonal matrix $M$.  Let $M'$ be the $n^2$  by $n$ matrix created by selecting the first $n$ columns of $M$.
Now consider all $n$ by $n$ matrices $A_i$ created by selecting exactly $n$ not  necessarily distinct rows from $M'$ with replacement.  There are ${n^2+n-1 \choose n}$ such  matricex $A_i$.
Let $s_1,\dots,s_k$ be the number of times each row is selected and let $\tau = \prod_i s_i!$.
As an example, if $n=2$ and $A_i$ is formed by choosing row $1$ twice from $M'$ then $A_i$ will be a $2$ by $2$ matrix with two identical rows.  We have $s_1 = 2$ and $\tau = 2$.
Let $\operatorname{perm}$ be the function that computes the permanent of a matrix.
Why is the following true?
$$\sum \frac{\operatorname{perm}(A_i)^2}{\tau} = 1?$$ 
 A: Suppose we were to pick $n$ rows with replacement, but now with order mattering.  In other words, we choose an ordered $n$-tuple of rows $(r_1, r_2, \dots, r_n)$ (since we have $n^2$ choices for each row, there's $n^{2n}$ total ways of picking the rows).  Then for a given $s_1, s_2, \dots, s_k$, the number of ways of picking the rows so that row $i$ is chosen exactly $s_i$ times is then $\frac{n!}{\tau}$.  So in this new framework, we can express the result we're trying to show as 
$$\sum_{r_1, \dots, r_n} \textrm{perm}(A)^2 = n!.$$
We can write the permanent as a sum over permutations, i.e.
$$\textrm{perm}(A)=\sum_{\sigma} \prod_{i=1}^n A_{i, \sigma(i)} = \sum_{\sigma} \prod_{i=1}^n M_{r_i, \sigma(i)}$$
When we square $\textrm{perm}(A)$, we can view it as a sum over two permutations, so that the left hand side of the first displayed equation can be written as 
$$\sum_{r_1, \dots, r_n} \sum_{\sigma} \sum_{\tau} \prod_{i=1}^n M_{r_i, \sigma(i)} M_{r_i, \tau(i)} = \sum_{\sigma} \sum_{\tau} \sum_{r_1, \dots, r_n} \prod_{i=1}^n M_{r_i, \sigma(i)} M_{r_i, \tau(i)}$$
The inner sum and product factorize!  We have 
$$\sum_{r_1, \dots, r_n} \prod_{i=1}^n M_{r_i, \sigma(i)} M_{r_i, \tau(i)} = \prod_{i=1}^n \left(\sum_{j=1}^{n^2} M_{j, \sigma(i)} M_{j, \tau(i)}\right)$$
Now the inner sum is just the inner product between columns $\sigma(i)$ and $\tau(i)$ in $M$.  In particular, if $\sigma(i) \neq \tau(i)$, that inner sum (and therefore the product) is $0$.    
If on the other hand, $\sigma=\tau$, then the inner sum is $1$ for every $i$, and the product is equal to $1$.  So each permutation contributes exactly $1$, and the whole sum is $n!$, which is what we're looking for.  
