Consider an n × n tri-diagonal sparse matrix A. Suppose we want to store the…

Concept

A tri-diagonal matrix is a sparse matrix in which non-zero entries lie only on the main diagonal and the two diagonals immediately adjacent to it (one above, one below). Thus A(i, j) is stored only when |i − j| ≤ 1; all other positions are zero and are not stored. To save space, only these stored entries are packed contiguously into a one-dimensional array in row-major order.

Application

Assume both the rows/columns and the array are indexed starting from 1, and that A(i, j) is a stored position (|i − j| ≤ 1). Count, in row-major order, how many stored entries precede A(i, j):

1. Row 1 stores only A(1,1) and A(1,2) → 2 entries. Each interior row r (2 ≤ r ≤ n−1) stores three entries: A(r, r−1), A(r, r), A(r, r+1). (The last row n stores only A(n, n−1) and A(n, n), but that boundary row never lies strictly before an interior query, so it does not affect the count below.)

2. Stored entries lying in the rows before row i = 2 + 3·(i − 2) = 3i − 4.

3. Within row i, the stored columns are i−1, i, i+1, so the position of column j inside its row is (j − i + 2).

4. Adding the within-row offset to the count of preceding entries: (3i − 4) + (j − i + 2) = 2i + j − 2.

Index of A(i, j) = 2i + j − 2.

Cross-check

Take A(2, 2), the second main-diagonal entry. The stored order is A(1,1), A(1,2), A(2,1), A(2,2), …, so A(2,2) sits at index 4. The formula gives 2·2 + 2 − 2 = 4. The two results agree, confirming the mapping.