GATE CS 1994 Q1.11 — Arrays, Stacks and Queues

To find the index of the $(i, j)^{\text{th}}$ element of a lower triangular matrix in a compact 1D array representation, we can count the number of elements stored before it.

Assuming 1-based indexing for the matrix coordinates $(i, j)$ and 0-based indexing for the 1D array:

1. Elements in preceding rows:

   Since it is a lower triangular matrix, row $k$ contains exactly $k$ elements. Therefore, the total number of elements in all rows preceding row $i$ (from row $1$ to $i-1$) is:

   $$1 + 2 + 3 + \dots + (i-1) = \frac{i(i-1)}{2}$$
2. Elements in the current row $i$:

   In row $i$, the element is at column $j$. Since columns are 1-indexed, there are $j-1$ elements in row $i$ that lie before the $(i, j)^{\text{th}}$ element.

Adding these two values gives the total number of elements stored before the $(i, j)^{\text{th}}$ element:

In a 0-indexed 1D array, the index of an element is exactly equal to the number of elements preceding it. Thus, the index is:

Example Verification:

Consider a $3 \times 3$ lower triangular matrix stored in a 0-indexed array:

• Row 1: $A_{1,1}$ (Index 0)
• Row 2: $A_{2,1}$ (Index 1), $A_{2,2}$ (Index 2)
• Row 3: $A_{3,1}$ (Index 3), $A_{3,2}$ (Index 4), $A_{3,3}$ (Index 5)

For element $A_{3,2}$ (where $i=3, j=2$):

This matches the actual index 4 in our representation.