Computing k-rings of sets with Adjacency matrix powers

Home    Publications    Blog    About Me   

02 May 2017

Statement

Consider an adjacency matrix \(A\) of a graph with nodes \(V = \{i\}_{i=1}^n\) and edges \(E \subset V \times V\) that takes on entries

\[A_{ij} = \left\{ \begin{array}{l l} 1 & \{i,j\} \in E\\ 0 & \text{o.w} \end{array} \right.\]

where \(\forall i \in V, \{i,i\} \in E\). If we let sets be represented by vectors \(v \in {(\mathbb{R}^+)}^n\) by the map \(\pi: {(\mathbb{R}^+)}^n \rightarrow 2^V\) defined by

\[\pi(v) = \{ i: v_i > 0\}\]

we have the interesting property that the $k$-ring neighborhood of a set $\sigma$, represented by some vector \(v^\sigma\), is given by

\[\pi\left(A^kv^\sigma\right)\]

I thought this was a more commonly known fact, but apparently not :(.

$k$-rings

Before we begin let us make clear the definition of the $k$-ring around a set. Given a set $\sigma$ the $0$-ring is defined as $\sigma$ itself. Notationally we’ll denote the ring operator as \(\mathcal{R}^k: 2^V \rightarrow 2^V\) and so the \(0\) ring is written as

\(\mathcal{R}^0(\sigma) = \sigma.\) The $k$-ring is then defined recursively by

\[\mathcal{R}^k(\sigma) = \mathcal{R}(\sigma)\]

where $\mathcal{R} = \mathcal{R}^1$ is the set morphism

\[\mathcal{R}(\sigma) = \{j: \forall {i,j} \in E, \forall i \in V\}.\]

For completeness we’ll say that the mapping $\sigma \rightarrow v^\sigma$ is trivially computed by \(v^\sigma = v(\sigma) = \sum_{i \in \sigma} e_i\) where $e_i$ are basis vectors, but in general $v^\sigma = \sum_{i \in \sigma} c_i e_i$ for $c_i \in \mathbb{R}^+$. This choice of $v^\sigma$ is here to make the computation of a $k$-ring a bit more explicit:

\[\mathcal{R}^k(\sigma) = \pi(A^k(v(\sigma))).\]

Proof

Because the definition of a $k$-ring was already recursive, all that needs to be done is to prove that for an arbitrary set $\sigma$, that $\pi(Av^\sigma) = \mathcal{R}(\sigma)$. All we need to assume is that we have some realization

\(v(\sigma) = \bar v^{\sigma} = \sum_{i \in \sigma} c_i e_i \in \pi^{-1}(\sigma)\).

and prove that \(\mathcal{R}(\sigma) = \pi(A \bar v^{\sigma})\).

The recursiveness and this realization come into play in the sense that if the above is true then

\[\mathcal{R}^{k+1}(\sigma) = \mathcal{R}(\mathcal{R}^{k}(\sigma)) = \pi(Av(\mathcal{R}^{k}(\sigma))) = \pi(A^{k+1}v(\sigma))) = \pi(A^{k+1}\bar v^\sigma).\]

Quickly, take note that the definition of the 1-ring for a set can be computed by a (countable) union. That is,

\[\mathcal{R}(\sigma) = \bigcup_{i \in \sigma} \mathcal{R}(\{i\}).\]

Simple proof

\(\pi(A \bar v^{\sigma}) = \pi\left(\sum_i \sum_j A_{i,j} c_i e_i\right) = \bigcup_i \pi\left(\left[\sum_j A_{i,j} c_i \right]e_i\right).\)

By the definition of $A$ and $\bar v^{\sigma}$ as well as recalling that they take on positive coefficients we see that

\[\sum_j A_{i,j} c_i > 0 \iff \left( i \in \sigma \text{ and } \exists j\in V, \{i,j\} \in E\right)\] \[\iff \exists i \in V\text{ s.t } j \in \mathcal{R}(\{i\}).\]

Therefore, this is equivalent to $j \in \mathcal{R}(\sigma)$.

More interesting proof

This is nicely compartmentalized into two components: the identification of how $A$ behaves with an arbitrary singleton ${i}$ and how the summation of their vector realizations behaves.

For a single element ${i}$ we have

\[A\bar v^{\{i\}} = Ac_ie_i = c_i A e_i = c_i \sum_{\{i,j\} \in E} e_j = \sum_{\{i,j\} \in E} c_i e_j\]

because $v^{{i}} = c_i$ must be positive we see that

\[\pi(A\bar v^{\{i\}})= \{j: c_i > 0\} = \{j: \forall {i,j} \in E\} = \mathcal{R}(\{i\}) .\]

Now that we have proven that for a single element this procedure produces a 1-ring neighborhood, we generalize this to the computation of neighborhoods of sets.

It is therefore sufficient to show that $\pi$ is a semigroup homomorphism from vectors under addition and sets under union.

\[\sigma \cup \omega = \pi(\bar v^\sigma) + \pi(\bar v^{\omega})= \pi(\bar v^{\sigma} + \bar v^{\omega}).\]

Before we go through the trivial proof let us present the conclusion of this proof assuming this morphism works:

\[\pi( A\bar v^{\sigma}) = \pi\left( \sum_i c_i A e_i\right) = \bigcup_{i\in V} \pi\left( c_i A e_i\right) = \bigcup_{i \in \sigma} \pi\left( A e_i\right)\] \[= \bigcup_{i \in \sigma} \mathcal{R}(\{i\}) = \mathcal{R}(\sigma)\]

We therefore prove the semigroup homomorhpism by the following:

\[\pi(\bar v^{\sigma} + \bar v^{\omega}) = \{i: c_i^\sigma + c_i^\omega > 0\}\]

where because the coefficients must be nonnegative we see that

\[c_i^\sigma + c_i^\omega > 0 \iff \left(c_i^\sigma > 0 \text{ or } c_i^\omega > 0 \right)\] \[\iff\left( i \in \omega \text{ or } i \in \sigma \right) \iff i \in \omega \cup \sigma.\]
comments powered by Disqus