TIP: Half Size Triangular Matrix


Application Security Testing: An Integral Part of DevOps

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;
      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; 
       keyafter = row * N - (row - 1) * row / 2; 
   } while (index >= keyafter); 
   col = N - keyafter + index; 
void Trag_reverse_noeq(int index, int N, int& row, int& col)
    row = 0;
    int keyafter;
        keyafter = row * (N-1) - (row - 1) * row / 2;
    } while (index >= keyafter);
    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

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

About the Author

Ben Axelrod



  • matrix pattern

    Posted by payal on 10/27/2014 02:23am

    003 046 365

  • _____

    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.

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • As all sorts of data becomes available for storage, analysis and retrieval - so called 'Big Data' - there are potentially huge benefits, but equally huge challenges...
  • The agile organization needs knowledge to act on, quickly and effectively. Though many organizations are clamouring for "Big Data", not nearly as many know what to do with it...
  • Cloud-based integration solutions can be confusing. Adding to the confusion are the multiple ways IT departments can deliver such integration...

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date
We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.