# Time complexity of comparing two $N \times N$ Matrices?

So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of operations is less than $O(N^{2})$ or is the matrix comparison lower bound also $\Omega(N^2)$?

• What kind of comparison are you looking at? – Raphael Feb 22 '16 at 13:43

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)$.
Theoretically, it is possible if you bound the input space and the type of the matrix. For example, suppose that we know that the matrices are both scalar matrices, such that they are identity matrices times two different scalar. In that case, it is necessary to only compare two elements; a diagonal element with a diagonal element from the other matrix. In this case, the algorithmic complexity would be $O(1)$. This is kind of a cop-out, however, as we are now computing on a specific subset of matrices.