# 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

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

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

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

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

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:

### 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

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

#### 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

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

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

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.

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

We therefore prove the semigroup homomorhpism by the following:

where because the coefficients must be nonnegative we see that