Suppose that $M$ is a $2021\times 2021$ symmetric matrix such that the entries of each row is set by rearranging $\{1,2,\cdots,2021\}$. Then what is the trace of $M$?
We know that ${\rm tr}(M)$ is the sum of all eigenvalues of $M$. I can see that $\frac{2021\cdot 2022}{2}$ is an eigenvalue of $M$ since $$M(1,1,\cdots,1)^{\rm T}=(1+\cdots+2021)\cdot(1,1,\cdots,1)^{\rm T} .$$ But after that I’m stuck. Any help is appreciated.
Fix $a\in\{1,...,2021\}$.
By hypothesis, $a$ occurs exactly once in each row, so the total number of occurrences of $a$ is $2021$.
Since the matrix is symmetric, the number of off-diagonal occurrences of $a$ must be even, hence $a$ must occur an odd number of times on the diagonal, and in particular, at least once.
By the pigeonhole principle, each $a\in\{1,...,2021\}$ must occur exactly once on the diagonal, hence the trace is $$ 1+\cdots+2021 = \frac{2021{\,\cdot\,}2022}{2} $$