for my C++ course at may university, we were asked to write a small jet analysis for some LHC data. While writing mine, I was confronted with this: How do you store a symmetrical $N \times N$ matrix efficiently in C++?

If you just store it as a normal matrix, the needed space will go with $N\^2$. Also, every update has to be done twice. Not very nice (and that does not even take any problem with multidimensional arrays in C++ in to account)

Now, what do we really need for this matrix?

Which does not look like its much but for simplicity sake I am only using an $N=4$-matrix. For my analysis, $N$ was around $10000$. So how much elements do we really need?

The first row has $1$ element, the second $2$ and so on up to the last row which has $N$ elements. Therefore we have a total of $\sum_{i=1}\^N i = \frac{N\^2 + N}{2}$ elements. Great! We basically need only half the elements and therefore only half the RAM!

But how do we store it? We need a way to transform this multidimensional array into a single dimensional array and then use a simple function which transforms the 2D coordinates i,j to an index p of our single dimensional array. Lets take a look at the matrix again:

Now, then we write this rows just after each other like this:

and use a reference function like this: (we will require $i \geq j$ for this but if $j > i$, you can just switch both as the matrix is symmetrical)

Yeah! We now can allocate an single dimension array and use it as an symmetrical matrix without worrying about multiple elements!