Arrays: Address Calculation and Special Matrices

An array stores elements of one type in consecutive memory locations, so the address of any element can be computed from its indices with a little arithmetic. That computation gives $O(1)$ access by index, the property that makes arrays the foundation of heaps, hash tables, matrices and dynamic programming tables.

This note centres on address calculations: given the base address, element size, index bounds and storage order, find the address of an element. A second topic is how to store special matrices (triangular, symmetric, tridiagonal, sparse) compactly and where a given element lands. This note derives the general formulas and checks each one by enumeration. How C arrays relate to pointers is in Arrays and Their Relation to Pointers.

Conventions: $B$ is the base address (address of the first element), $w$ the size of one element in bytes (addressing is by bytes unless addresses are counted in words). Index ranges are written $l..u$, so a dimension has $u - l + 1$ elements. C arrays always start at index 0; other lower bounds come from languages such as Pascal and Fortran, and from 1-based presentations.

For A[l..u]:

In C ($l = 0$) this is B + i * sizeof A[0], exactly what &A[i] computes.

For A[l1..u1][l2..u2] with $n_1 = u_1 - l_1 + 1$ rows and $n_2 = u_2 - l_2 + 1$ columns:

In words: count how many complete rows (or columns) come before the element, multiply by the row (or column) length, and add the position inside the current row (or column).

For A[l1..u1][l2..u2][l3..u3] in row-major order, with $n_k = u_k - l_k + 1$:

The pattern generalises: in row-major order the last index varies fastest; in column-major order the first index varies fastest. The first dimension's size $n_1$ never appears in the row-major formula, which is why a C function parameter can omit only the first dimension (int a[][4]).

Square $n \times n$ matrices with many guaranteed zeros (or repeated entries) can be stored in a one-dimensional array holding only the significant entries. In this section indices are 1-based, $1 \le i, j \le n$, and the formulas give the 0-based offset $k$ into the 1D array; the address is $B + k\,w$.

Number of stored entries: $1 + 2 + \cdots + n = n(n+1)/2$.

Note the symmetry: upper triangular column-major has the same shape of formula as lower triangular row-major with $i$ and $j$ exchanged.

Store only the lower triangle ($n(n+1)/2$ entries) and access $A[i][j]$ with $j > i$ as $A[j][i]$.

A tridiagonal matrix has non-zero entries only where $|i - j| \le 1$: the main diagonal and the diagonals directly above and below. It has $3n - 2$ such entries. Stored row by row (row 1 has 2 entries, rows 2 to $n-1$ have 3, row $n$ has 2):

A band matrix of positive order $n\ge1$ and integer half-width $0\le b\le n-1$, with nonzeros allowed only where $|i-j|\le b$, has $n(2b+1)-b(b+1)$ allowed positions. Tridiagonal is $b=1$ for $n\ge2$. If a redundant larger width is supplied, use $b_{\mathrm{eff}}=\min(b,n-1)$ in the formula.

When only a few entries are non-zero but with no fixed pattern, store a list of triplets (row, column, value), usually sorted by row and then column, or use linked lists per row. For $t$ non-zero entries the triplet form uses $3t$ values instead of $n^2$; it saves space when $3t < n^2$ (counting each stored value as one unit).

The C row-major offsets below are for C11 with gcc on x86-64 Linux (LP64, 4-byte int).

Example 1 (2D with non-zero lower bounds). A[-3..4][5..10] of 4-byte integers, $B = 1000$. Then $n_1 = 8$, $n_2 = 6$.

The C check models the array as int M[8][6] with A[i][j] at M[i+3][j-5]; the byte offset of M[4][2] is 104, and sizeof M is 192.

Example 2 (3D). A[1..3][1..4][1..5] of 2-byte elements, row-major, $B = 2000$: $\text{addr}(A[2][3][4]) = 2000 + (((2-1) \cdot 4 + (3-1)) \cdot 5 + (4-1)) \cdot 2 = 2000 + 33 \cdot 2 = 2066$. In C, &T[1][2][3] in int T[3][4][5] is 33 elements from the start.

Example 3 (lower triangular, $n = 6$). Element $A[5][3]$: row-major offset $5 \cdot 4/2 + 2 = 12$; column-major offset $2 \cdot 6 - 1 + 2 = 13$. The packed array has $6 \cdot 7/2 = 21$ entries; a strictly lower triangular matrix (zero diagonal too) would need $15$.

Example 4 (tridiagonal). For any $n$, $A[1][1]$ is at offset 0, $A[2][1]$ at $2 \cdot 2 + 1 - 3 = 2$, and $A[i][i]$ at $3i - 3$.