Context
I have a symmetric matrix (containing numbers, or sequences of characters) which is eventually sparse (meaning that it contains a lot of zeros). I want to store this matrix in a computer program without loosing too much space. The idea is to create a vector from the matrix (hence we do not duplicate the information induced by the symmetry). Also, using an associative array we can drop all non-interesting entries if the matrix is sparse.
Notations
We start with an \(n\times n\) matrix with rows and columns labelled \( 0,\ldots, n-1 \) and we want to induce a bijection \( \iota: \{0,\ldots,n-1\}^2 \longrightarrow \left\{ 0,\ldots, \frac{n(n+1)}{2}-1 \right\} \). We will enumerate the elements of the first row \( 0,\ldots, n-1 \), the ones of the second row \( n,\ldots, 2n-2 \), etc.
Correspondence
If the pair \( (i,j) \) designates an element of the matrix, its index \( \iota(i,j) \) in the vector is given by
\[
\iota(i,j)=\frac{i(2n-1-i)}{2}+j
\]
Conversely, if \( k\in \left\{ 0,\ldots, \frac{n(n+1)}{2}-1 \right\} \) is the index of an element of the vector, then the corresponding entry of the matrix is on the row
\[
\textrm{row}(k)=\textrm{floor} \frac{(2n+1)-\sqrt{(2n+1)^2-8k}}{2},
\]
and column
\[
\textrm{col}(k)=k-\frac{\textrm{row}(k)\cdot\big(2n-1-\textrm{row}(k)\big)}{2}
\]
Verifications
For a pair \( (i,j) \), we have to check that \( \textrm{row}\big( \iota(i,j) \big) = i \). Since the composition
\[
\textrm{row}\big( \iota(i,j) \big) = \textrm{floor}\frac{2n+1-\sqrt{(2n+1)^2-4i(2n-1-i)-8j}}{2}
\]
is increasing with respect to \( j \), we only have to check the equality in the extremal cases \( j = i \) and \( j = n-1 \). We find
\[
\textrm{row}\big( \iota(i,i) \big)=\textrm{floor} \frac{2n+1-\sqrt{ (2n-2i+1)^2}}{2} = i
\]
and
\[
\textrm{row}\big( \iota(i,n-1) \big)<\textrm{row}\big( \iota(i,n) \big)=\textrm{floor} \frac{2n+1-\sqrt{ (2n-2i-1)^2}}{2}=i+1,
\]
as required. It follows from these equalities that \( \textrm{col}\big( \iota(i,j) \big) = j \). The equality \( k = \iota\big( \textrm{row}(k), \textrm{col}(k) \big) \) is easy.
Laisser un commentaire