# TIP: Half Size Triangular Matrix

Often, when dealing with graphs or other data types, you need to store a large distance matrix. By its nature, this matrix is symmetric, which means that cells in the upper right are the same as the cells in the lower left. For example, cell (1,2) is equal to cell (2,1). For large matrices, this redundancy can waste a lot of space—especially when double precision is required.

The technique described here allows you to use a 1D array to store only half of the matrix. A simple function outputs the 1D index when given the row, column, and size of the 2D matrix.

This function came about when I noticed that the first key number on each row was noticed to be row*N-TriangleNumber. Where row is the row number (starting with 0), N is the size of the matrix (elements per side), and TriangleNumber is an integer sequence defined by N(N+1)/2. See: http:www.research.att.com/%7Enjas/sequences/A000217 for more info on that.

For example, when N=4, the key numbers are 0, 4, 7, and 9. Create this matrix like so:

  0 1 2 3
0 0 1 2 3
1   4 5 6
2     7 8
3       9


From this equation, row*N-N(N+1)/2, it is easy to get the rest of the indices.

Here is the Trag_eq() function that gives you the index into the 1D array. Note that the size of the 1D array is (N*N-N)/2+N.

int Trag_eq(int row, int col, int N)
{
if (row <= col)
return row*N - (row-1)*((row-1) + 1)/2 + col - row;
else if (col<row)
return col*N - (col-1)*((col-1) + 1)/2 + row - col;
}


Then, to set or read cells, it is simply array[Trag_eq(r,c,N)].

There is a slightly less useful variant to this, but it can save you more space in some situations. When you are not dealing with diagonal entries, (row = column), you can use this function instead:

int Trag_noeq(int row, int col, int N)
{
//assert(row != col);    //You can add this in if you like
if (row<col)
return row*(N-1) - (row-1)*((row-1) + 1)/2 + col - row - 1;
else if (col<row)
return col*(N-1) - (col-1)*((col-1) + 1)/2 + row - col - 1;
else
return -1;
}


The usage is the same, except the size of the 1D array is now (N*N-N)/2—a savings of N. And now, you have to be more careful about indexing so you don't access element -1 of the 1D array.

You can also do the *reverse* of the previously mentioned formulas. Where the index into the 1D triangular matrix is given, and the row and column of the corresponding 2D square matrix is output. It turns out that this is a bit more difficult. The reason is that the key numbers for a certain sized matrix are a function of the row. So you have to iterate until you find the right row for the specified index.

Here are the reverse functions. Similar to above there are two functions, one for with and one for without diagonal entries. The order of this operation is O(N). Where N is the length of one side of the 2D square matrix. But since the loop breaks after it finds the right row, the average case is O(N/2).

void Trag_reverse_eq(int index, int N, int& row, int& col)
{
row = 0;
int keyafter;
do
{
row++;
keyafter = row * N - (row - 1) * row / 2;
} while (index >= keyafter);
row--;
col = N - keyafter + index;
}

void Trag_reverse_noeq(int index, int N, int& row, int& col)
{
row = 0;
int keyafter;
do
{
row++;
keyafter = row * (N-1) - (row - 1) * row / 2;
} while (index >= keyafter);
row--;
col = N - keyafter + index;
}


Here is an example of how to use these functions. If you have a triangular matrix like this:

0 1 2 3
4 5 6
7 8
9


Which is stored in a 1D array like this:

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


This is how to call the function to get the row and column of cell number 5:

int row;
int col;
Trag_reverse_eq(5, 4, row, col);
// row is now 1
// col is now 2


#### Ben Axelrod

http://www.benaxelrod.com/

• #### _____

Posted by Kyle Gorman on 12/23/2013 08:31am

Cool! I just implemented this as a Python class using numpy: https://gist.github.com/kylebgorman/8064310 One note: given n, the length of a vector representing a matrix triangle (and assuming n is a triangular number), the dimension (height and also width) of the square matrix in which the triangle is situated is given by (\sqrt(8n + 1) - 1) / 2. Haven't worked it out yet, but I think that might give you a closed-form (as opposed to iterative) solution to the Trag_reverse_* functions.

• You must have javascript enabled in order to post comments.

## Top White Papers and Webcasts

• The rapid evolution of enterprise storage technologies, combined with external forces, like the explosion of big data, can cause Linux® and server administrators to play catch-up when it comes to storage. Running a bunch of monolithic storage devices and proprietary, disconnected technologies forces administrators to spend valuable time creating and managing complex solutions. To reduce complexity and enable rapid deployment of new technologies and applications, server administrators need a single open …

• The impact of a data loss event can be significant. Real-time data is essential to remaining competitive. Many companies can no longer afford to rely on a truck arriving each day to take backup tapes offsite. For most companies, a cloud backup and recovery solution will eliminate, or significantly reduce, IT resources related to the mundane task of backup and allow your resources to be redeployed to more strategic projects. The cloud - can now be comfortable for you – with 100% recovery from anywhere all …

## Most Popular Programming Stories

• There have been no articles posted today.