# Computing k-rings of sets with Adjacency matrix powers

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.$