title: Is there an algorithm better than O(N²) to determine if matrix is symmetric?
body: <h2>Algorithm requirements</h2>
  
  <p>Input is an arbitrary square matrix <code>M</code> of size <code>N×N</code>, which <em>just</em> fits in memory. </p>
  
  <p>The algorithm's output must be <code>true</code> if <code>M[i,j] = M[j,i]</code> for all <code>j≠i</code>, <code>false</code> otherwise.</p>
  
  <h2>Obvious solutions</h2>
  
  <ol>
  <li><p><strong>Check if the transpose equals the matrix itself (<code>M</code><sup>T</sup><code>=M</code>)</strong>. Easiest to program in many environments, but (usually) consumes twice the memory and requires <code>N²</code> comparisons worst case. Therefore, this is O(<code>N²</code>) and has high peak memory.</p></li>
  <li><p><strong>Check if the lower triangular part equals the upper triangular part</strong>. 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 <code>N²/2 - N</code> comparisons, since the diagonal does not need to be checked. So although it is better than option 1, this is still O(<code>N²</code>).</p></li>
  </ol>
  
  <h2>Question</h2>
  
  <p>Although it's hard to see how it would be possible (the <code>N²</code> elements will all have to be compared somehow), is there an algorithm doing this check that is better than O(<code>N²</code>)?</p>
  
  <p>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.?</p>
  
  <p>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 <code>AX=b</code>...</p>