A $n \times n$ matrix $M$ is a symmetric matrix,where $n$ is odd($i.e.n=2k+1,k\in \mathbb{Z}^{+}\cup{\{0\}}$). Every row of $M$ is a permutation of $\{1,2,\cdots,n\}$. Show that the diagonal elements of $M$ is also a permutation of $\{1,2,\cdots,n\}.$
$e.g.$ when $n=3, $ all possible matrices satisfying $M$'s requirements as following:
$$\begin{pmatrix} {\color{red} 3} & 2 & 1\\ 2& {\color{red}1}& 3\\ 1 & 3& {\color{red}2} \end{pmatrix},\begin{pmatrix} {\color{red}3} & 1 & 2\\ 1& {\color{red}2}& 3\\ 2 & 3& {\color{red}1} \end{pmatrix},\begin{pmatrix} \color{red}2 & 1 & 3\\ 1& \color{red}3& 2\\ 3 & 2& \color{red}1 \end{pmatrix},\begin{pmatrix} \color{red}2 & 3 & 1\\ 3& \color{red}1& 2\\ 1 & 2& \color{red}3 \end{pmatrix},\begin{pmatrix} {\color{red}1} & 2 & 3\\ 2& {\color{red}3}& 1\\ 3 & 1& {\color{red}2} \end{pmatrix},\begin{pmatrix} {\color{red}1} & 3 & 2\\ 3& {\color{red}2}& 1\\ 2 & 1& {\color{red}3} \end{pmatrix}.$$
Obviously,the diagonal elements of each one is a permutation of $\{1,2,3\}.$
For $n=2k+1,k\geq 2 ,k\in \mathbb{N}.$ I consider the characteristic polynomial of $M$: $$f_{\mathbf{M}}(\lambda)=(\lambda-\frac{n(n+1)}{2})(\lambda^{2}+a_{1}\lambda+b_{1})\cdots(\lambda^{2}+a_{k}\lambda+b_{k}).$$ If we can prove $a_{1}=a_{2}=\cdots=a_{k}=0,$then $\mathbb{trace}(M)=\frac{n(n+1)}{2}.$ Additionally,if we can prove the product of diagonal elements $\prod_{i=1}^{n}a_{11} a_{22}\cdots a_{nn}=n!,$then the question will be sloved. But both of them are not easy to be proved.If you have some good ideas, please give me some hints !
A simple parity argument will do. By assumption, every element of $S=\{1,2,\ldots,n\}$ must occur an odd number of times (or more precisely, $n$ times). Yet, if some element of $S$ does not appear on the diagonal, it must appear in $M$ an even number of times, because the matrix is symmetric and off-diagonal elements occur in pairs.