Why do the squared permanents sum to 1?

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.