I was thinking about the following problem:
Let $n\in\mathbb N$ be odd. If I have a symmetric matrix in $M_n(\mathbb{N})$, i.e. a square symmetric matrix of size $n$, for which each column and each row consists of all numbers between $1$ and $n$, then the diagonal consists of all the numbers from $1$ to $n$.
I want to prove this using the pigeonhole principle. Thanks for helping me.
On
I am not sure that I understood correctly, but wouldn't $$ \left(\begin{array}{ccc} 1&2&3\\ 3&1&2\\ 2&3&1 \end{array}\right) $$ be a counterexample? All the rows and columns have all the numbers from $1$ to $3$, yet the diagonal has only $1$s.
Adding a proof for the non-existence of such a matrix, when the requirement of symmetry is added.
Each number must occur an odd number of times. But because of the symmetry, all the numbers appear off the diagonal an even number of times. Therefore they all appear in the diagonal an odd number of times, i.e. at least once. Because all there are $n$ numbers appearing on the diagonal, they must all appear there exactly once.
On
Note: This answer was for the original question, which inadvertently omitted the requirement that the matrix be symmetric.
It’s not true: consider, for instance, the matrix
$$\begin{bmatrix}1&2&3\\3&1&2\\2&3&1\end{bmatrix}\;.$$
You don’t even have to work that hard: with $n=2$ already you have
$$\begin{bmatrix}1&2\\2&1\end{bmatrix}\;.$$
You don't use the pigeonhole principle, but the double counting principle.
Note that since the matrix is symmetric, if an entry appears in the strictly upper right triangle, it must appear again in the strictly lower left triangle, hence appear an even number of times.
The only way for a number to appear an odd number of times, is for it to appear an odd number of times on the diagonal. Hence, each number must appear at least once on the diagonal.