anothermousey's blog

By anothermousey, history, 22 months ago, In English

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 and Litho on math stackexchange. You can find the solution and proof here. Thanks div4only for providing me with great support. I will state the construction here only.

Satisfied matrix construction

I do not know if this contributes much to competitive programming, but it is fun doing these types of math problems.

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
22 months ago, # |
Rev. 4   Vote: I like it +11 Vote: I do not like it

$$$A_{i, j} \neq 0 \rightarrow \forall 0 \leq k \leq n-1, A_{j, k} = 0$$$. However, there are only $$$n$$$ zeros and $$$n^2-n$$$ non-zeros. So for $$$n \geq 3$$$ there exists two distinct $$$j_1,\,j_2$$$ such that there are non-zeros on the $$$j_1$$$-th column and $$$j_2$$$-th column, respectively. So there have to contain $$$2$$$ zero rows of $$$A$$$, which is impossible.

Seems easy? Do I miss something? Is $$$A*A$$$ matrix multiplication or point-wise multiplication? You should make it clear.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I forgot to mention that the n*n terms in the final matrix should be modulo n. Sorry for missing information.

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Auto comment: topic has been updated by anothermousey (previous revision, new revision, compare).

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by anothermousey (previous revision, new revision, compare).