IMC 2001 · Day 1 · P1

Since there are exactly $n$ rows and $n$ columns, the choice is of the form $$\{ (j, \sigma(j)) : j = 1, \dots, n \}$$ where $\sigma \in S_n$ is a permutation. Thus the corresponding sum is equal to $$\sum_{j=1}^{n} n(j-1) + \sigma(j) = \sum_{j=1}^{n} nj - \sum_{j=1}^{n} n + \sum_{j=1}^{n} \sigma(j) = n \sum_{j=1}^{n} j - \sum_{j=1}^{n} n + \sum_{j=1}^{n} j = (n+1) \frac{n(n+1)}{2} - n^2 = \frac{n(n^2+1)}{2},$$ which shows that the sum is independent of $\sigma$.