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

Question

Algorithm Requirements

The input is an arbitrary square matrix M size N×N , which simply fits into the memory.

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

Obvious solutions

• Make sure the transpose is equal to the matrix itself ( M ^T =M ) . It is easy to program in many environments, but (usually) consumes twice as much memory and requires N² worst case comparisons. Therefore, it is O ( N² ) and has a high peak memory.

• Check if the lower triangular part matches the upper triangular part . Of course, the algorithm returns the first inequality found. This would make the worst case (in the worst case, the matrix is ​​really symmetrical) requires N²/2 - N comparisons, since the diagonal does not need to be checked. Therefore, although it is better than option 1, it is still O ( N² ).

Question

Although it’s hard to understand how this will be possible (the elements of N² should all be matched in some way), is there an algorithm that performs this check better than O ( N² )?

Or, if there is evidence of the absence of such an algorithm: how to implement it most efficiently for a multi-core processor (Intel or AMD), taking into account such things as cache-friendliness, optimal branch prediction, other specific to the compiler, etc.?

This question is mainly related to academic interest, although I suggest that practical use may consist in determining which solver to use if the matrix describes a linear system AX=b ...

Answer 1

For a dense matrix, the answer is a definite no, since any non-invasive (off-diagonal) elements may differ from their transposed copies.

For standard sparse matrix representations, the same reasoning indicates that you usually cannot do better than the size of the input.

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

Answer 2

Since you will need to learn all the elements except the diagonal, IMO complexity cannot be better than O (n ^ 2).

Answer 3

I think you can take a probabilistic approach here.

I think this is not a coincidence / coincidence that x randomly selected elements of the lower coordinate will correspond to their upper triangular counting part. The probability is very high that the matrix is ​​really symmetrical.

So, instead of going through all the elements ½n² - n , you can check the random coordinates p and say if the matrix is ​​symmetric with confidence:

 p / (½n² - n) 

you can decide the threshold above which you think the matrix should be a symmetric matrix.