\(n=20\), 完全ランダムで実験をすると、例えば以下のようになります。

11221202210202021111
02010120101010102020
10101012010101010101
01010101201010101010
20101010120101010101
12010101012010101010
01201010101201010101
02010101010120101010
01201010101012010101
20120101010101201010
12012010101010120101
10101201010101012010
21010120101010101201
20101012010101010120
12010101201010101012
20101010120101010101
01010101012010101010
10101010101201010101
12010101010120101010
01201010101012010101

ある程度 \(i, j\) が大きくなると、左上から右下にかけて同じ値が出るようになっていることがわかります。

実際に、必ず \(a_{4, 4} = a_{5, 5}\) が成立することが場合分け or 全探索で示せます。よって、最初の4行 / 4列のみを愚直に計算することでこの問題は \(O(N)\) で解くことが出来ます。