I was wondering a problem: Is it possible to construct a $n \times n$ matrix (call it A) such that each number from $1$ to $n$ appears exactly $n$ times and the result of $A \times A$ (matrix multiplication) is a zero matrix (after modulo $n \times n$ terms in the matrix by $n$). I know it is obvious for odd $n$ but how about even $n$?↵
↵
Upd: After roughly 2 weeks the solution is done by [Phd Ben Grossmann](https://math.stackexchange.com/users/81360/ben-grossmann) and [Litho](https://math.stackexchange.com/users/197288/litho) on math stackexchange. You can find the solution and proof [here](https://math.stackexchange.com/questions/4616962/an-n-times-n-matrix-a-that-contains-each-of-1-2-cdots-n-exactly-n-time). Thanks [user:div4only,2023-1-24] for providing me with great support. I will state the construction here only. ↵
↵
<spoiler summary="Satisfied matrix construction">↵
For odd $n$, filling the $i^{th}$ row with number $i$ will give us the satisfied matrix. ↵
↵
For $n=2$, we can show that there is no satisfied matrix by simply bruteforce. ↵
↵
For $n=4 \times k$, the satisfied matrix is constructed by:↵
- filling rows $i = 1 \rightarrow k$ with $2 \times i - 1$.↵
- filling rows $i = k + 1 \rightarrow 3 \times k$ with $(4k, 4k-2, 4k-4, ..., 2, 2, 4, 6, ..., 4k)$.↵
- filling rows $i=3 \times k + 1 \rightarrow 4 \times k$ with $2 \times i - 4 \times k - 1$↵
↵
For $n=4 \times k + 2$, the satisfied matrix is constructed by:↵
- filling rows $i = 1$ and $i = 3 rightarrow 2 \times k + 2$ with (2, 4, ..., 4k, 4k+2, 4k+2, 1, 3, …, 2k−1, 2k+3, …, 4k+1).↵
- filling rows $i = 2$ and $i = 2 \times k + 3 rightarrow 4 \times k + 2$ with (2, 4, ..., 4k, 2k+1, 2k+1, 1, 3, …, 2k−1, 2k+3, …, 4k+1).↵
</spoiler>↵
↵
↵
↵
I do not know if this contributes much to competitive programming, but it is fun doing these types of math problems.
↵
Upd: After roughly 2 weeks the solution is done by [Phd Ben Grossmann](https://math.stackexchange.com/users/81360/ben-grossmann) and [Litho](https://math.stackexchange.com/users/197288/litho) on math stackexchange. You can find the solution and proof [here](https://math.stackexchange.com/questions/4616962/an-n-times-n-matrix-a-that-contains-each-of-1-2-cdots-n-exactly-n-time). Thanks [user:div4only,2023-1-24] for providing me with great support. I will state the construction here only. ↵
↵
<spoiler summary="Satisfied matrix construction">↵
For odd $n$, filling the $i^{th}$ row with number $i$ will give us the satisfied matrix. ↵
↵
For $n=2$, we can show that there is no satisfied matrix by simply bruteforce. ↵
↵
For $n=4 \times k$, the satisfied matrix is constructed by:↵
- filling rows $i = 1 \rightarrow k$ with $2 \times i - 1$.↵
- filling rows $i = k + 1 \rightarrow 3 \times k$ with $(4k, 4k-2, 4k-4, ..., 2, 2, 4, 6, ..., 4k)$.↵
- filling rows $i=3 \times k + 1 \rightarrow 4 \times k$ with $2 \times i - 4 \times k - 1$↵
↵
For $n=4 \times k + 2$, the satisfied matrix is constructed by:↵
- filling rows $i = 1$ and $i = 3 rightarrow 2 \times k + 2$ with (2, 4, ..., 4k, 4k+2, 4k+2, 1, 3, …, 2k−1, 2k+3, …, 4k+1).↵
- filling rows $i = 2$ and $i = 2 \times k + 3 rightarrow 4 \times k + 2$ with (2, 4, ..., 4k, 2k+1, 2k+1, 1, 3, …, 2k−1, 2k+3, …, 4k+1).↵
</spoiler>↵
↵
↵
↵
I do not know if this contributes much to competitive programming, but it is fun doing these types of math problems.
