In a compact one dimensional array representation for lower triangular matrix…

Concept

A compact array stores only the non-zero entries of a triangular matrix, in row order. So the array index of any entry equals a running count: the number of entries already stored from all earlier rows, plus how far into the current row that entry sits. For a lower triangular matrix (1-indexed rows/columns), row i holds i non-zero entries — one for each column j = 1, 2, …, i — so the count of entries contributed by rows 1 through i − 1 follows the arithmetic-series identity 1 + 2 + … + (i − 1) = i(i − 1)/2.

Application

1. Count the entries occupying array slots before row i begins: rows 1, 2, …, i − 1 contribute 1, 2, …, i − 1 entries respectively, so the total is the sum of the first (i − 1) positive integers, i(i − 1)/2, by the arithmetic-series formula n(n + 1)/2 with n = i − 1.

2. Locate (i, j) within row i itself: row i's non-zero entries run through columns j = 1, 2, …, i in order, so (i, j) is the j-th entry placed in that row.

3. Convert the in-row position to a zero-based offset: the j-th entry within the row sits at offset j − 1 from the row's first stored entry (the row's first entry, j = 1, lands at offset 0).

4. Add the two counts to get the overall zero-based array index: index(i, j) = i(i − 1)/2 + (j − 1) — exactly the option j − 1 + i(i − 1)/2.

Cross-check

• Smallest case: (i, j) = (1, 1) is the very first stored entry, so it must map to index 0. The formula gives 1(0)/2 + (1 − 1) = 0 — correct.

• Later case: (i, j) = (3, 2). Rows 1 and 2 together store 1 + 2 = 3 entries (indices 0, 1, 2), so row 3 starts at index 3; its second entry (j = 2) is at index 3 + 1 = 4. The formula gives 3(2)/2 + (2 − 1) = 3 + 1 = 4 — matching the direct count and confirming the derivation.