language agnostic - How to store a symmetric matrix?

Question

Which is the best way to store a symmetric matrix in memory?

It would be good to save half of the space without compromising speed and complexity of the structure too much. This is a language-agnostic question but if you need to make some assumptions just assume it's a good old plain programming language like C or C++..

It seems a thing that has a sense just if there is a way to keep things simple or just when the matrix itself is really big, am I right?

Just for the sake of formality I mean that this assertion is always true for the data I want to store

matrix[x][y] == matrix[y][x]

Answer 1

Here is a good method to store a symmetric matrix, it requires only N(N+1)/2 memory:

int fromMatrixToVector(int i, int j, int N)
{
   if (i <= j)
      return i * N - (i - 1) * i / 2 + j - i;
   else
      return j * N - (j - 1) * j / 2 + i - j;
}

For some triangular matrix

0 1 2 3
  4 5 6
    7 8
      9

1D representation (stored in std::vector, for example) looks like as follows:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

And call fromMatrixToVector(1, 2, 4) returns 5, so the matrix data is vector[5] -> 5.

For more information see http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211/TIP-Half-Size-Triangular-Matrix.htm