公式

N - Nonsymmetric Matrix 解説 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\)

投稿日時:
最終更新: