TAOCP 2.2.6 Exercise 21
Since $n$ is variable, the allocation function must encode the size of the matrix together with the indices.
Section 2.2.6: Arrays and Orthogonal Lists
Exercise 21. [**] [20] Suggest a storage allocation function for $n \times n$ matrices where $n$ is variable. The elements A[I,J] for $1 \le I,J \le n$ should occupy $n^2$ consecutive locations, regardless of the value of $n$.
Verified: no
Solve time: 27s
Since $n$ is variable, the allocation function must encode the size of the matrix together with the indices. A convenient method is to reserve a consecutive block of $n^2$ locations for each value of $n$, and then use ordinary row-major addressing within that block. Let
$$ B(n)=\sum_{m=1}^{n-1}m^2 =\frac{(n-1)n(2n-1)}{6} $$
be the total number of locations occupied by all smaller matrices. Then define
$$ \operatorname{LOC}(A[I,J]) = a_0+B(n)+(I-1)n+(J-1), \qquad 1\le I,J\le n. $$
For fixed $n$, the quantity $(I-1)n+(J-1)$ runs through the integers $0,1,\ldots,n^2-1$ in lexicographic order of $(I,J)$, so the elements of an $n\times n$ matrix occupy exactly $n^2$ consecutive locations. Different values of $n$ occupy disjoint consecutive blocks, because $B(n+1)=B(n)+n^2$. Hence the requirement is satisfied.
$$ \boxed{ \operatorname{LOC}(A[I,J]) = a_0+\frac{(n-1)n(2n-1)}{6} +(I-1)n+(J-1) } $$