Time complexity of comparing two $N \times N$ Matrices?
A very simple adversary argument shows that when comparing two vectors of length $M$ (in your case, $M = N^2$), you must query (in the worst case) all positions of both vectors to know whether they are equal. That takes time $\Omega(M)$.