Adjacency #
Introduction #
In this section we review the adjacency matrix of a graph and consider some of its basic properties. We ask how a similar structure might be devised to represent the cardinal structure of a quiver. Motivated by this question, we'll use the word ring to define routes and plans, which model subjective states of knowledge about potential paths in a quiver. Multisets allow us to obtain an isomorphism between plans and plan matrices. We then construct a particular plan matrix that plays the role of an adjacency matrix: the adjacency plan matrix (which has a corresponding adjacency plan).
Note: this section is largely incomplete and should be ignored for now.
Adjacency matrices of graphs #
The adjacency matrix \( \matrix{A} \) of a finite directed graph \( \graph{G} \) with vertices \( \sym{V} = \list{\vert{v_1},\vert{v_2},\elSy,\vert{v_{\sym{n}}}} = \vertexList(\graph{G}) \) is an \( \sym{n}\times \sym{n} \) matrix with entries:
\[ \matrixPart{\matrix{A}}{\sym{i}}{\sym{j}}\defEqualSymbol \begin{cases} 1 &\text{if } \elemOf{\de{\vert{v_{\sym{i}}}}{\vert{v_{\sym{j}}}}}{\graph{G}}\\ 0 &\text{otherwise} \end{cases} \]For a finite directed multigraph, the entries can be arbitrary non-negative integers that simply count the number of edges \( \de{\vert{v_{\sym{i}}}}{\vert{v_{\sym{j}}}} \).
Examples #
Here we illustrate some example graphs and their corresponding adjacency matrices:
Properties #
Matrix powers and walks #
Quivers #
How do we model the cardinal structure that a quiver imposes on a digraph? A famous quip in computer science goes that "all problems can be solved by an additional level of indirection". Our additional level of indirection is via the cardinals: we now consider a mapping from cardinals to adjacency matrices:
\[ \matrix{A}\defEqualSymbol \assocArray{\mto{\card{c}_1}{\matrix{A}_1},\mto{\card{c}_2}{\matrix{A}_2},\elSy,\mto{\card{c}_{\sym{k}}}{\matrix{A}_{\sym{k}}}} \]Each \( \matrix{A}_{\sym{i}} \) gives the ordinary digraph adjacency matrix for the subgraph of the quiver \( \quiver{Q} \) consisting only of edges labeled with the cardinal \( \card{c}_{\sym{i}} \).
Here we show these mappings for some simple quivers:
Back to single matrices #
An idea that might have occurred to the reader is to combine the per-cardinal adjacency matrices into a single adjacency matrix:
But if this idea is to work, what are these matrices? More specifically, what is the meaning of sums of the form \( \grFo{\card{g}} + \reFo{\card{r}} \) that can appear in their entries? These are simply elements of the word ring that we introduced in a previous section.
Adjacency ring #
The approach we used above was to represent the cardinal structure of a quiver by storing a separate adjacency matrix for each cardinal, gathering these into a mapping \( \assocArray{\mto{\card{c}_1}{\matrix{A}_1},\mto{\card{c}_2}{\matrix{A}_2},\elSy,\mto{\card{c}_{\sym{k}}}{\matrix{A}_{\sym{k}}}} \). This allowed us to distinguish adjacency on a per-cardinal basis.
But there is more algebraic way to do this, which is by treating the cardinals as being the indeterminates of a polynomial, although the misleading term variable is sometimes used.
We can then represent a mapping \( \assocArray{\mto{\card{c}_1}{\matrix{A}_1},\mto{\card{c}_2}{\matrix{A}_2},\elSy,\mto{\card{c}_{\sym{k}}}{\matrix{A}_{\sym{k}}}} \) as a polynomial \( \polynomial{a} = \poly{\card{c_1} \, \matrix{A}_1 + \card{c_2} \, \matrix{A}_2 + \elSy + \card{c_{\sym{k}}} \, \matrix{A}_{\sym{k}}} \), where the \( \card{c_{\sym{i}}} \) are variables and the adjacency matrices \( \matrix{A}_{\sym{i}} \) are coefficients.
Formally, \( \polynomial{a} \) is an element of a (multivariate) polynomial ring \( \polynomialRing{\ring{R}}{\variable{\card{c}_1},\variable{\card{c}_2},\elSy,\variable{\card{c}_{\sym{n}}}} \), where the coefficient ring is \( \ring{R} = \matrixRing{\ring{\mathbb{Z}}}{\sym{n}} \), the matrix ring of \( \sym{n}\times \sym{n} \) matrices with integer entries.
The adjacency polynomial \( \polynomial{a} \) represents the quiver in a particular sense that we will now explore.
Routes, multiroutes, and plans #
Motivation #
We will now construct a family of structures that represents subjective states of knowledge of an agent about how they might navigate a quiver \( \quiver{Q} \).
The subjective states will describe how an agent believes it can move between ordered pairs of vertices \( \vertOf{\vert{v_{\sym{i}}},\vert{v_{\sym{j}}}}{\quiver{Q}} \), which we'll call endpoints. We'll organize the various forms of knowledge as follows:
-
a route \( \routeSymbol{R} \) for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \) is an imagined path from origin vertex \( \vert{v} \) to destination vertex \( \vert{w} \) (this need not correspond to an actual path)
-
a multiroute \( \multirouteSymbol{R} \) for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \) is a multiset of routes that all share the same endpoints \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \)
-
a plan \( \planSymbol{P} \) is a multiset of routes, not necessarily for the same endpoints
A plan and a multiroute are said to be empty if they are empty as multisets.
Being a multiset of routes, a multiroute is necessarily also a plan. Conversely, a plan might contain routes with differing endpoints, and hence is not in general a multiroute. We can however refer to the multiroute for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \) within a plan, which is the multiset of all those routes with those particular endpoints.
A route is fictitious if it does not describe a path in the quiver. Likewise, a multiroute or plan is fictitious if it contains a single fictitious route.
A plan does not have to be consistent: a plan might contain a route for \( \fromTo{\vert{u}\fromToSymbol \vert{v}} \) and a route for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \), but no route for \( \fromTo{\vert{u}\fromToSymbol \vert{w}} \). This doesn't match our intuition about navigation, which is that if we know how to get from \( \vert{u} \) to \( \vert{v} \) and from \( \vert{v} \) to \( \vert{w} \) then we implicitly know how to get from \( \vert{u} \) to \( \vert{w} \). We will create an exact definition of consistency later.
The route word for a route for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \) is a path word that describes the imagined path from vertex \( \vert{v} \) to vertex \( \vert{w} \) as a sequence of cardinals.
The multiroute word for a multiroute for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \) is a path multiword that describes the multiset of imagined paths from vertex \( \vert{v} \) to vertex \( \vert{w} \) in terms of their cardinals.
Interpretation #
As we said, plans are constructs that describe what an agent believes about how it is possible to navigate a quiver. These beliefs do not have to true, or even consistent, but we will of course define the logic of how to build true and consistent beliefs.
Notation #
In Path groupoids we introduced the notation \( \paren{\pathWord{\vert{u}}{\wordSymbol{W}}{\vert{v}}} \) to refer to a path in a quiver. (Multi)routes are distinct from paths, since while paths must exist in the quiver, (multi)routes can be fictitious. Therefore we introduce distinct notation \( \route{\vert{u}}{\wordSymbol{W}}{\vert{v}} \) for a route for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \) with path word \( \wordSymbol{W} \) and \( \multiroute{\vert{u}}{\multiwordSymbol{W}}{\vert{v}} \) to represent a multiroute for \( \fromTo{\vert{v}\fromToSymbol \vert{w}} \) with path multiword \( \elemOf{\multiwordSymbol{W}}{\wordRingSymbol } \).
Recall that a multiword \( \multiwordSymbol{W} \) is a formal sum of words \( \elemOf{\wordSymbol{W_{\sym{i}}}}{\wordGroupSymbol } \) with coefficients \( \elemOf{\sym{n_{\sym{i}}}}{\ring{\mathbb{Z}}} \):
\[ \multiwordSymbol{W} = \sym{n_1} \, \wordSymbol{W_1} + \sym{n_2} \, \wordSymbol{W_2} + \elSy \]The multiroute with multiword \( \multiroute{\vert{u}}{\multiwordSymbol{W}}{\vert{v}} \) with path multiword \( \multiwordSymbol{W} \) is by definition the formal sum of routes with corresponding path words from \( \multiwordSymbol{W} \):
\[ \multiroute{\vert{u}}{\multiwordSymbol{W}}{\vert{v}}\identicallyEqualSymbol \sym{n_1} \, \route{\vert{u}}{\wordSymbol{W_1}}{\vert{v}} + \sym{n_2} \, \route{\vert{u}}{\wordSymbol{W_2}}{\vert{v}} + \elSy \]Recall that when all \( n_{\sym{i}} \ge 0 \), we can interpret a multiword as a multiset, where \( \sym{n_{\sym{i}}} \) are the multiplicities for each distinct word (if some \( \sym{n_{\sym{i}}}<0 \), we have instead a signed multiset). Then the above formal sum is equivalent to building a multiroute as a multiset of routes, one for each word in the multiword:
\[ \multiroute{\vert{u}}{\multiwordSymbol{W}}{\vert{v}}\identicallyEqualSymbol \multisetConstructor{\route{\vert{u}}{\wordSymbol{W}}{\vert{v}}}{\elemOf{\wordSymbol{W}}{\multiwordSymbol{W}}} \]Representation #
We've introduced the high-level concepts of routes, multiroutes, and plans. We'll now show how a plan can be represented by a matrix of a particular type.
Consider an \( \sym{n}\times \sym{n} \) matrix \( \matrix{M} \), where \( \sym{n} = \vertexCountOf{\quiver{Q}} \) is the number of vertices, and whose entries are multiwords, namely elements of the word ring \( \wordRingSymbol \).
A matrix \( \matrix{M} \) represents a plan \( \planSymbol{P} \) as follows:
\[ \planSymbol{P} = \indexSum{\multiroute{\vert{v_{\sym{i}}}}{\matrixPart{\matrix{M}}{\sym{i}}{\sym{j}}}{\vert{v_{\sym{j}}}}}{\sym{i},\sym{j}}{} \]The \( \TuFo{\sym{i}, \sym{j}} \) entry of \( \matrix{M} \), written \( \matrixPart{\matrix{M}}{\sym{i}}{\sym{j}} \), gives the multiroute word for \( \fromTo{\vert{v_{\sym{i}}}\fromToSymbol \vert{v_{\sym{j}}}} \).
Let's rephrase this in terms of individual routes, using the multiset interpretation of the word ring \( \wordRingSymbol \). Since each entry \( \matrixPart{\matrix{M}}{\sym{i}}{\sym{j}} \) is an element of the \( \wordRingSymbol \), we can interpret the entry as a multiset of path words. These path words will be the route words for individual routes for \( \fromTo{\vert{v_{\sym{i}}}\fromToSymbol \vert{v_{\sym{j}}}} \).
\[ \planSymbol{P} = \multisetConstructor{\route{\vert{v_{\sym{i}}}}{\wordSymbol{W}}{\vert{v_{\sym{j}}}}}{\begin{nsarray}{c} 1 \le \sym{i},\sym{j} \le \sym{n}\\ \elemOf{\wordSymbol{W}}{\matrixPart{\matrix{M}}{\sym{i}}{\sym{j}}} \end{nsarray} } \]We can see now more clearly the utility of the word ring: multiwords in the word ring represent multisets of path words. Fixing an origin and destination \( \fromTo{\vert{v_{\sym{i}}}\fromToSymbol \vert{v_{\sym{j}}}} \), each path word describes a route, and hence a multiset of path words describes a multiroute. Organizing these multiwords into a matrix, we can represent an entire plan. Next, we'll consider the significance of the ring addition and multiplication of such plan matrices.
Ring structure of plans #
Matrix ring #
The set of \( \sym{n}\times \sym{n} \) matrices (whose entries are taken from a ring \( \ring{R} \)) forms a ring in its own right, called a matrix ring and written \( \matrixRing{\ring{R}}{\sym{n}} \), with addition and multiplication given by normal algorithms for matrices:
\[ \begin{aligned} \matrixPart{\paren{\matrix{X}\matrixPlusSymbol \matrix{Y}}}{\sym{i}}{\sym{j}}&\defEqualSymbol \matrixPart{\matrix{X}}{\sym{i}}{\sym{j}} + \matrixPart{\matrix{Y}}{\sym{i}}{\sym{j}}\\ \matrixPart{\paren{\matrix{X}\matrixDotSymbol \matrix{Y}}}{\sym{i}}{\sym{j}}&\defEqualSymbol \indexSum{\matrixPart{\matrix{X}}{\sym{i}}{\sym{k}} \, \matrixPart{\matrix{Y}}{\sym{k}}{\sym{j}}}{\sym{k} \le \sym{n}}{}\end{aligned} \](The addition and multiplication of matrix entries on the rhs of these definitions takes place in the ring \( \ring{R} \) of matrix entries.)
Plan ring #
The matrices we used to represent plans for a quiver \( \quiver{Q} \) form a matrix ring, which we will call the plan matrix ring, written \( \planRing{\quiver{Q}} \):
\[ \planRing{\quiver{Q}}\defEqualSymbol \matrixRing{\wordRing{\quiver{Q}}}{\vertexCountOf{\quiver{Q}}} \]This is the \( \sym{n}\times \sym{n} \) matrix ring (where \( \sym{n} = \vertexCountOf{\quiver{Q}} \) is the number of vertices), whose entries are elements of the word ring \( \wordRingSymbol \) over the cardinals of the quiver. We'll call a matrix from the plan ring a plan matrix.
Sums of matrices #
The sum \( \matrix{X} + \matrix{Y} \) of two plan matrices \( \elemOf{\matrix{X},\matrix{Y}}{\planRing{\quiver{Q}}} \) is given by merging \( \matrix{X} \) and \( \matrix{Y} \) seen as multisets of routes.
Products of matrices #
What about multiplication \( \matrix{X}\matrixDotSymbol \matrix{Y} \) of two plan matrices \( \matrix{X},\matrix{Y} \)? By the ordinary definition of matrix multiplication in a matrix ring, we have:
\[ \matrixPart{\paren{\matrix{X}\matrixDotSymbol \matrix{Y}}}{\sym{i}}{\sym{j}} = \indexSum{\matrixPart{\matrix{X}}{\sym{i}}{\sym{k}} \, \matrixPart{\matrix{Y}}{\sym{k}}{\sym{j}}}{\sym{k} \le \sym{n}}{} \]For fixed \( \sym{i},\sym{j},\sym{k} \), the product \( \matrixPart{\matrix{X}}{\sym{i}}{\sym{k}} \, \matrixPart{\matrix{Y}}{\sym{k}}{\sym{j}} \) is the product of two multiwords. Under the multiset interpretation, this product is the multiset formed from all possible concatenations of a word from \( \matrixPart{\matrix{X}}{\sym{i}}{\sym{k}} \) and a word from \( \matrixPart{\matrix{Y}}{\sym{k}}{\sym{j}} \) respectively. Each such pair of words represents a route from \( \matrix{X} \) for \( \fromTo{\vert{v_{\sym{i}}}\fromToSymbol \vert{v_{\sym{k}}}} \) and a route from \( \matrix{Y} \) for \( \fromTo{\vert{v_{\sym{k}}}\fromToSymbol \vert{v_{\sym{j}}}} \). Therefore each concatenated word in the result can be interpreted as the path word for a route for \( \fromTo{\vert{v_{\sym{i}}}\fromToSymbol \vert{v_{\sym{j}}}} \). The entire result is the multiset of such composite path words: a multiword.
For a fixed \( \sym{i} \) and \( \sym{j} \), the sum \( \indexSum{\matrixPart{\matrix{X}}{\sym{i}}{\sym{k}} \, \matrixPart{\matrix{Y}}{\sym{k}}{\sym{j}}}{\sym{k} \le \sym{n}}{} \) over all \( \sym{k} \) is therefore a multiset that consists of the path words of composite routes that start at \( \vert{v_{\sym{i}}} \) and end at \( \vert{v_{\sym{j}}} \), having passed through any \( \vert{v_{\sym{k}}} \): the first part of each composite route comes from \( \matrix{X} \), the second from \( \matrix{Y} \).
Therefore, the product \( \matrix{X}\matrixDotSymbol \matrix{Y} \) represents the plan that consists of the all composite routes formed from any route in \( \matrix{X} \) followed by any route in \( \matrix{Y} \), where-ever these can be composed. The matrix product is therefore the natural way to combine two plans in an ordered way to form another plan.
Plan matrices vs plans #
Plan matrices are distinct from plans themselves, although we have shown how they are related under the multiset interpretation of rings. Specifically, a plan matrix represents a (possibly signed) multiset of routes. Is there a natural equivalence between plans and plan matrices?
The answer is yes, but in a similar sense to how matrices correspond to linear operators for a finite-dimensional vector space. Once we have chosen an ordered basis for a vector space, we can represent a linear operator as a matrix. Similarly, once we choose a labeling of vertices of a quiver, we can use plan matrices to represent plans, since the entries of the plan matrix are relative to a particular ordering of vertices. In the setting of a (countably) infinite quiver, nothing much changes, though our matrices become infinite. Questions of "convergence" are appropriate to worry about: we might require than any particular sum that occurs in the definition of plan matrix multiplication involves only a finite number of non-zero terms, but we will see how this can be achieved later.
Abstract operations on plans #
We have already see how to define plan matrix multiplication and addition, and have attached multiset interpretations to these. It is worth now defining the same operations abstractly on plans themselves, since they are arguably simpler when we do not insist on representing plans as plan matrices:
The sum of two plans \( \planSymbol{X} + \planSymbol{Y} \) is the union of the \( \planSymbol{X} \) and \( \planSymbol{Y} \) as multisets of routes:
\[ \planSymbol{X} + \planSymbol{Y}\defEqualSymbol \planSymbol{X}\setUnionSymbol \planSymbol{Y} \]The product of two plans \( \planSymbol{X} \, \planSymbol{Y} \) is the multiset of compositions of routes from \( \planSymbol{X} \) and routes from \( \planSymbol{Y} \):
\[ \planSymbol{X} \, \planSymbol{Y}\defEqualSymbol \multisetConstructor{\pathCompose{\routeSymbol{X}}{\routeSymbol{Y}}}{\elemOf{\routeSymbol{X}}{\planSymbol{X}},\elemOf{\routeSymbol{Y}}{\planSymbol{Y}}} \]Implicitly, if two routes cannot be composed, in other words if \( \pathCompose{\routeSymbol{X}}{\routeSymbol{Y}} = \nullPath \), that term is ignored in the construction.
In fact, plans form a ring, the plan ring, just like plan matrices do. These rings are isomorphic, as one might imagine.
Consistency #
We mentioned earlier that plans need not be consistent, although we didn't define precisely what consistency is. Roughly speaking, a plan is consistent if it is closed under composition with itself, meaning that any two routes in the plan that can be composed to form another route will form a composite route that is already in the plan. We naturally expect this of intelligent agents, since if such an agent knows how to get from A to B and from B to C, it necessarily must know how to get from A to C -- if it does not already have a route from A to C, it can simply compose a route from A to B with a route from B to C.
What is the mathematical condition that corresponds to this notion of consistency? Quite simply, if a plan \( \planSymbol{P} \) is consistent, then \( \planSymbol{P} \, \planSymbol{P} = \planSymbol{P} \) -- or in ring-theory terminology, \( \planSymbol{P} \) is idempotent. We will show how to construct such consistent plans shortly.
Cardinal and adjacency plans #
We are now ready to engage with the original goal, which was to represent the cardinal structure of a quiver with a suitable generalization of an adjacency matrix.
Now that we have plan matrices, we can form the adjacency plan matrix \( \matrix{P} \) for a quiver. Here we show one example:
Notice the presence of inverted cardinals below the diagonal. Why is this necessary? The reason is that we can form paths out of cardinals or their inverses. In other words, we can traverse an edge \( \tde{1}{2}{\reFo{\card{r}}} \) in the forward direction, yielding the path \( \pathWord{1}{\word{\reFo{\card{r}}}}{2} \), or we can traverse it in the backward direction, yielding the path \( \pathWord{2}{\word{\reFo{\ncard{r}}}}{1} \). If we wish for all paths of length \( \sym{n} \) to be present in the iterated adjacency plan matrix \( \power{\matrix{P}}{\sym{n}} \), we must encode a given edge in the adjacency plan matrix in both the forward and backward orientations, corresponding to a normal and inverted cardinal present in entries mirrored around the diagonal.
Powers of the adjacency plan #
Eigenvectors of adjacency #
Plan Laplacian #