Linearization of a (sparse) symmetric matrix

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.

Publié

dans

par

Étiquettes :