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

A tri-diagonal matrix has non-zero elements only on the main diagonal, the diagonal above it, and the diagonal below it. For an n×n matrix, the non-zero elements are at positions (i, j) where |i - j| ≤ 1.

When storing such a matrix in a one-dimensional array, we typically use row-major order and store only the non-zero elements. The index of the (i, j)th element in the 1D array depends on both the row number and the relative position of the element within that row.

In a tri-diagonal matrix, each row contains at most three non-zero elements (except the first and last rows, which contain two). Therefore, the index is determined by adding:

• the total number of elements stored before row i, and

• the position of the element within row i.

Using this mapping, the correct indexing formula for the (i, j)th element in the one-dimensional array is:

2i + j − 2

This formula correctly accounts for the cumulative number of stored elements and ensures proper mapping of the tri-diagonal structure into a linear array.

Explanation

Matrix form (non-zero entries only, since |i − j| ≤ 1):

• The formula applies only when |i − j| ≤ 1.

• Otherwise the element is 0 and is not stored.

Row 1: A11  A12   0    0
Row 2: A21  A22  A23   0
Row 3:  0   A32  A33  A34
Row 4:  0    0   A43  A44

Stored in the 1D array (row-wise)

[A11, A12, A21, A22, A23, A32, A33, A34, A43, A44]

Cross-check with worked examples

1. Example 1 — locate A23: with i = 2, j = 3, the formula gives 2(2) + 3 − 2 = 5.

2. Counting the stored sequence from 1, the 5th entry is A23 — the formula checks out.

3. Example 2 — locate A32: with i = 3, j = 2, the formula gives 2(3) + 2 − 2 = 6.

4. The 6th entry in the stored sequence is A32 — the formula checks out again.