TAOCP 2.2.6 Exercise 23
Let the matrix elements be stored in the order in which they are created.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 23. [**] [23] An extendible matrix is initially $1 \times 1$, then it grows from size $m \times n$ either to size $(m + 1) \times n$ or to size $m \times (n + 1)$ by adding either a new row or a new column. Show that such a matrix can be given a simple allocation function in which the elements A[I,J] occupy $mn$ consecutive locations, for $0 \le I < m$ and $0 \le J < n$; no elements change location when the matrix grows.
Verified: no
Solve time: 41s
Let the matrix elements be stored in the order in which they are created. Define
$$ \operatorname{LOC}(A[I,J])=B+I+J(J+1)/2, $$
where $B=\operatorname{LOC}(A[0,0])$.
This allocation corresponds to placing the elements on successive diagonals of the infinite array:
$$ A[0,0];\quad A[0,1],A[1,0];\quad A[0,2],A[1,1],A[2,0];\quad \ldots $$
When the matrix has size $m\times n$, every stored element satisfies $0\le I<m$ and $0\le J<n$. Since the matrix can grow only by adding a new bottom row or a new rightmost column, the set of occupied locations is always
$$ B,\ B+1,\ \ldots,\ B+mn-1. $$
Indeed, the rectangle $0\le I<m$, $0\le J<n$ contains exactly the first $mn$ positions of the above diagonal ordering. Adding row $m$ contributes the next $n$ locations, and adding column $n$ contributes the next $m$ locations. Hence the occupied locations remain consecutive, growing from $mn$ to $(m+1)n$ or to $m(n+1)$ locations, and every previously existing element keeps the same address because its value of $I+J(J+1)/2$ is unchanged.
Therefore an extendible matrix admits a simple allocation function in which the entries occupy exactly $mn$ consecutive memory locations at every stage, and no element changes location when the matrix grows. ∎