Converting a Triangular Matrix to an Array

I ran into an interesting problem recently. I had a matrix, that is a two-dimensional array, where all the data was in the upper right hand side or on the diagonal. Such matrixes are called upper triangular matrixes. I wanted to transfer the data in the matrix to an array. I needed a function which accepts the row and column value of some entry in the matrix and which returns the corresponding index into the array. For example, see the image below. It shows a 4 x 4 upper triangular matrix with values a, b, c, d in the first row; e, f, g in the second row; h, i in the third row; and j in the fourth row. My goal is to programmatically create an array with values a, b, c, d, e, f, g, h, i, j. The first step is to observe that if the size of the upper triangular matrix is n, then the size of the corresponding array is 1 + 2 + 3 + . . . + n = sum of first n integers = n * (n + 1) / 2. Next, after a bit of experimentation I determined one way to map a (r, c), (that is a row, column pair), to an index value is the equation:

 

i = (n * r) + c – ((r * (r+1)) / 2)   [note: earlier post had a typo here]

 

For example if r = 1 and c = 3 (the value g in the matrix), then i = (4 * 1) + 3 – ((1 * 1) + 1)) / 2) = 4 + 3 – 1 = 6. Some code could resemble this:

 

string[] array = new string[(n * (n+1)) / 2]; // allocate
for (int r = 0; r < matrix.GetLength(0); ++r) // each row
{
  for (int c = 0; c < matrix.GetLength(1); ++c)
  {
    int i = (n * r) + c – ((r * (r+1)) / 2); // corrected from earlier post
    array[i] = matrix[r,c];
  }
}

 

A really neat little problem.