Official
N - Nonsymmetric Matrix Editorial
by
$B_{i, j} = A_{i, j} - A_{j, i}$ とおく。$i \neq j$ のとき $B_{i, j} \in \lbrace -2, -1, 1, 2 \rbrace$ である。$B_{1, 2} + B_{1, 3} + B_{1, 4} = 0$ であるため、対称性より $B_{1, 2} = 2, B_{1, 3} = -1, B_{1, 4} = -1$ としてよい。このとき $B_{1, 2} + B_{3, 2} + B_{4, 2} = 0$ から $B_{3, 2} = B_{4, 2} = -1$ であるため $B_{2, 4} = 1$ となる。
$B_{1, 4} + B_{2, 4} + B_{3, 4} = 0$ から $B_{3, 4} = 0$ となるが、これは矛盾。
N - Nonsymmetric Matrix Editorial
by 
cn449
\(N = 1\) のとき、答えは \(((0))\) です。
\(N = 2\) のとき、\(A_{1, 1} + A_{1, 2} = A_{1, 1} + A_{2, 1}\) から \(A_{1, 2} = A_{2, 1}\) なので条件を満たす行列は存在しません。
以下 \(N \geq 3\) とします。\(N\) の偶奇で場合分けを行います。
\(N\) が奇数のとき
以下のように行列を定めることで \(\max|A_{i,j}| = 1\) なる条件を満たす行列を得ることができます。
- \(i = j\) のとき \(A_{i, j} = 0\)
- \(i < j\) のとき
- \(i\) と \(j\) の偶奇が一致しているとき、\(A_{i, j} = 1\)
- \(i\) と \(j\) の偶奇が一致していないとき、\(A_{i, j} = -1\)
- \(i > j\) のとき
- \(i\) と \(j\) の偶奇が一致しているとき、\(A_{i, j} = -1\)
- \(i\) と \(j\) の偶奇が一致していないとき、\(A_{i, j} = 1\)
\(N\) が偶数のとき
\(N = 4\) のときは条件を満たす行列であって \(\max|A_{i,j}| = 1\) なるものは存在しません。これは全探索を行うか、以下のような証明によってわかります。
証明
条件を満たす行列であって $\max|A_{i,j}| = 1$ なるものが存在すると仮定する。$B_{i, j} = A_{i, j} - A_{j, i}$ とおく。$i \neq j$ のとき $B_{i, j} \in \lbrace -2, -1, 1, 2 \rbrace$ である。$B_{1, 2} + B_{1, 3} + B_{1, 4} = 0$ であるため、対称性より $B_{1, 2} = 2, B_{1, 3} = -1, B_{1, 4} = -1$ としてよい。このとき $B_{1, 2} + B_{3, 2} + B_{4, 2} = 0$ から $B_{3, 2} = B_{4, 2} = -1$ であるため $B_{2, 4} = 1$ となる。
$B_{1, 4} + B_{2, 4} + B_{3, 4} = 0$ から $B_{3, 4} = 0$ となるが、これは矛盾。
\(\max|A_{i, j}| = 2\) であって条件を満たす行列は存在し、例えば \(((0, 1, -1, 0), (2, -1, -1, 0), (0, 1, 1, -2), (-2, -1, 1, 2))\) がそのうちの一つです。
\(N \geq 6\) のときは以下のように行列を定めることで \(\max|A_{i,j}| = 1\) なる条件を満たす行列を得ることができます。
- \(A_{1, 1} = A_{2, N - 1} = A_{N, N} = 1\)
- \(A_{1, N - 1} = A_{1, N} = A_{2, N} = -1\)
- 上で値が決まっていない \((i, j)\) に対して
- \(i = j\) のとき \(A_{i, j} = -1\)
- \(i > j\) のとき
- \(i = j + 1\) かつ \(i\) が偶数のとき \(A_{i, j} = -1\)
- そうでないとき \(A_{i, j} = 0\)
- \(i < j\) のとき
- \(i + 1 = j\) または \(i + 2 = j\) のとき \(A_{i, j} = 1\)
- \(i + 3 = j\) かつ \(i\) が奇数のとき \(A_{i, j} = -1\)
- 上記に当てはまらず、\(i\) と \(j\) の偶奇が一致しているとき \(A_{i, j} = 1\)
- 上記に当てはまらず、\(i\) と \(j\) の偶奇が一致していないとき \(A_{i, j} = -1\)
posted:
last update: