Is there an algorithm better than O(N²) to determine if matrix is symmetric?

Question

Algorithm requirements

Input is an arbitrary square matrix M of size N×N, which just fits in memory.

The algorithm's output must be true if M[i,j] = M[j,i] for all j≠i, false otherwise.

Obvious solutions

1. Check if the transpose equals the matrix itself (M^T=M). Easiest to program in many environments, but (usually) consumes twice the memory and requires N² comparisons worst case. Therefore, this is O(N²) and has high peak memory.

2. Check if the lower triangular part equals the upper triangular part. Of course, the algorithm returns on the first inequality found. This would make the worst case (worst case being, the matrix is indeed symmetric) require N²/2 - N comparisons, since the diagonal does not need to be checked. So although it is better than option 1, this is still O(N²).

Question

Although it's hard to see how it would be possible (the N² elements will all have to be compared somehow), is there an algorithm doing this check that is better than O(N²)?

Or, provided there is a proof of non-existence of such an algorithm: how to implement this most efficiently for a multi-core CPU (Intel or AMD) taking into account things like cache-friendliness, optimal branch prediction, other compiler-specific specializations, etc.?

This question stems mostly from academic interest, although I imagine a practical use could be to determine what solver to use if the matrix describes a linear system AX=b...

Answer 1

Since you will have to examine all the elements except the diagonal, the complexity IMO can't be better than O (n^2).

Answer 2

For a dense matrix, the answer is a definite "no", because any uninspected (non-diagonal) elements could be different from their transposed counterparts.

For standard representations of a sparse matrix, the same reasoning indicates that you can't generally do better than the input size.

However, the same reasoning doesn't apply to arbitrary matrix representations. For example, you could store sparse representations of the symmetric and antisymmetric components of your matrix, which can easily be checked for symmetry in O(1) time by checking if antisymmetric element has any components at all...