Computing k-rings of sets with Adjacency matrix powers

Home    Publications    Blog    About Me   

02 May 2017

Statement

Consider an adjacency matrix of a graph with nodes and edges that takes on entries

where . If we let sets be represented by vectors by the map defined by

we have the interesting property that the $k$-ring neighborhood of a set $\sigma$, represented by some vector , 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 and so the ring is written as

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

.

and prove that .

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

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

comments powered by Disqus