\( \gdef\badDispatch#1{\textbf{\textcolor{e1432d}{#1}}} \gdef\noKatexForm#1{\badDispatch{#1}} \gdef\largeDot{\raisebox{0.06em}{\tiny∙}} \gdef\rarrbar{ {\raisebox{-0.05em}{→}\mkern{-0.13em}{\large\shortmid}}} \gdef\larrbar{ { {\large\shortmid}\mkern{-0.13em}{\raisebox{-0.05em}{←}}}} \gdef\suptrans{^\mathsf{T}} \gdef\supdagger{^\dagger} \gdef\rawsymbol#1{\operatorname{#1}} \gdef\colorsymbol#1#2{\textcolor{#1}{\rawsymbol{#2}}} \gdef\lsymbol#1{\colorsymbol{262626}{#1}} \gdef\msymbol#1{\colorsymbol{b50800}{#1}} \gdef\osymbol#1{\colorsymbol{00427f}{#1}} \gdef\lstring#1{\textcolor{666666}{\textrm{\textquotedblleft{#1}\textquotedblright}}} \gdef\boldForm#1{\textbf{#1}} \gdef\lrform#1{ {\textcolor{e1432d}{#1}}} \gdef\lgform#1{ {\textcolor{4ea82a}{#1}}} \gdef\lbform#1{ {\textcolor{3e81c3}{#1}}} \gdef\rform#1{ {\textcolor{e1432d}{#1}}} \gdef\gform#1{ {\textcolor{4ea82a}{#1}}} \gdef\bform#1{ {\textcolor{3e81c3}{#1}}} \gdef\rgform#1{ {\textcolor{dc841a}{#1}}} \gdef\gbform#1{ {\textcolor{47a5a7}{#1}}} \gdef\rbform#1{ {\textcolor{c74883}{#1}}} \gdef\waform#1{ {\textcolor{6b6b6b}{#1}}} \gdef\wbform#1{ {\textcolor{929292}{#1}}} \gdef\wcform#1{ {\textcolor{c5c5c5}{#1}}} \gdef\barToken{\mathbf{|}} \gdef\filledRectangleToken{▮} \gdef\emptyRectangleToken{▯} \gdef\filledSquareToken{■} \gdef\emptySquareToken{□} \gdef\filledToken{∙} \gdef\emptyToken{∘} \gdef\cardinalRewrite#1#2{\rewrite{#1}{#2}} \gdef\primed#1{ {#1}^{\prime}} \gdef\tinybullet{ {\tiny●}} \gdef\forwardFactor{\uparrow} \gdef\backwardFactor{\downarrow} \gdef\neutralFactor{\mid} \gdef\arrowhead{⏵} \gdef\deSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{→}}}\,}} \gdef\ueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny──}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\ldeSymbol{ { { {\raisebox{1.1pt}{\tinybullet}\mkern{-1pt}{\longrightarrow}}}\,}} \gdef\lueSymbol{ {\raisebox{1pt}{\tinybullet\raisebox{-0.03em}{\mkern{-0.3pt}{\tiny────}\mkern{-0.3pt}}\tinybullet}\,}} \gdef\de#1#2{ { {#1} \deSymbol {#2}}} \gdef\ue#1#2{ { {#1} \ueSymbol {#2}}} \gdef\tde#1#2#3{ { {#1} \overset{#3}{\deSymbol} {#2}}} \gdef\tue#1#2#3{ { {#1} \overset{#3}{\ueSymbol} {#2}}} \gdef\ltde#1#2#3{ { {#1} \overset{#3}{\ldeSymbol} {#2}}} \gdef\ltue#1#2#3{ { {#1} \overset{#3}{\lueSymbol} {#2}}} \gdef\mapsfrom{\htmlClass{hreflect}{\mapsto}} \gdef\longmapsfrom{\htmlClass{hreflect}{\longmapsto}} \gdef\diffd{𝕕} \gdef\partialdof#1{\partial {#1}} \gdef\emptySet{\empty} \gdef\unknown{\wbform{\text{?}}} \gdef\notApplicable{\wbform{\text{---}}} \gdef\textAnd{\text{\,and\,}} \gdef\identicallyEqualSymbol{\equiv} \gdef\congruentSymbol{\equiv} \gdef\isomorphicSymbol{\cong} \gdef\homotopicSymbol{\simeq} \gdef\approxEqualSymbol{\approx} \gdef\bijectiveSymbol{\cong} \gdef\defeq{\;≝\;} \gdef\defEqualSymbol{\;≝\;} \gdef\tailEqualSymbol{\underdot{=}} \gdef\headEqualSymbol{\dot{=}} \gdef\ruledelayed{:\to} \gdef\mathdollar{\text{\textdollar}} \gdef\hyphen{\text{-}} \gdef\endash{\text{--}} \gdef\emdash{\text{---}} \gdef\updownarrows{\uparrow\!\downarrow} \gdef\vthinspace{\mkern{1pt}} \gdef\dlq{\text{\textquotedblleft}} \gdef\drq{\text{\textquotedblright}} \gdef\dprime{ {\prime\prime}} \gdef\inverse#1{ { {#1}^{-1}}} \gdef\inverseSymbol{\inverse{□}} \gdef\groupDirectProduct#1{#1} \gdef\groupDirectProductSymbol{\times} \gdef\groupInverse{\inverse} \gdef\groupPower#1#2{ {#1}^{#2}} \gdef\groupCommutator#1#2{\left[{#1},{#2}\right]} \gdef\groupoidInverse{\inverse} \gdef\latticeBFS#1{\textrm{bfs}({#1})} \gdef\pathHomomorphism#1{#1} \gdef\groupoidFunction#1{#1} \gdef\groupoidHomomorphism#1{#1} \gdef\affineModifier#1{\overrightharpoon{#1}} \gdef\supercirc#1{#1^{\circ}} \gdef\supercircb#1{#1\!\degree} \gdef\toroidalModifier#1{\supercirc{#1}} \gdef\modulo#1{\supercirc{#1}} \gdef\dividesSymbol{\,|\,} \gdef\groupFunction#1{#1} \gdef\groupHomomorphism#1{#1} \gdef\automorphisms{\operatorname{Aut}} \gdef\endomorphisms{\operatorname{End}} \gdef\transportMap#1{\transportMapSymbol_{#1}} \gdef\transportMapSymbol{\tau} \gdef\action#1{#1} \gdef\selfAction#1{\hat{#1}} \gdef\actionGroupoid#1{\utilde{#1}} \gdef\cardinalGroup#1{G^*({#1})} \gdef\signed#1{ {#1}^*} \gdef\transportAtlas#1{T_{#1}} \gdef\inverted#1{\underline{#1}} \gdef\mirror#1{\overline{#1}} \gdef\pathComposeSymbol{ {\,∷\,}} \gdef\pathCompose#1#2{ {#1}\pathComposeSymbol{#2}} \gdef\translateSymbol{\uparrow} \gdef\backwardTranslateSymbol{\downarrow} \gdef\pathTranslate#1#2{ {#1}\,\translateSymbol\,{#2}} \gdef\pathLeftTranslate#1{ {#1}{\,\translateSymbol}} \gdef\pathBackwardTranslate#1#2{ {#1}{\,\backwardTranslateSymbol\,}{#2}} \gdef\pathLeftBackwardTranslate#1{ {#1}{\,\backwardTranslateSymbol}} \gdef\compactCovariantDifference#1#2{\Delta_{#1}\,{#2}} \gdef\covariantDifference{ {#1}\,\Delta\,{#2}} \gdef\forwardDifference{\Delta^{+}} \gdef\backwardDifference{\Delta^{-}} \gdef\centralDifference{\Delta} \gdef\pathForwardDifference#1{\forwardDifference_{#1}} \gdef\pathBackwardDifference#1{\backwardDifference_{#1}} \gdef\pathCentralDifference#1{\centralDifference_{#1}} \gdef\pathHead#1{\pathHeadVector{#1}} \gdef\pathTail#1{\pathTailVector{#1}} \gdef\pathHeadVector#1{ {#1}^{\bullet}} \gdef\pathTailVector#1{ {#1}_{\bullet}} \gdef\pathReverse#1{ {#1}^{\dagger}} \gdef\pathIntegral#1#2{ {#1} \int {#2}} \gdef\pathIntegralSymbol{ {\int}} \gdef\pathDot#1#2{ {#1} \cdot {#2}} \gdef\pathDotSymbol{ {\cdot}} \gdef\compactBasis#1{\mathscr{B}} \gdef\length{\operatorname{len}} \gdef\signedLength{\operatorname{len^*}} \gdef\andFn{\operatorname{and}} \gdef\orFn{\operatorname{or}} \gdef\notFn{\operatorname{not}} \gdef\vertexList{\operatorname{vertices}} \gdef\vertexList{\operatorname{vertices}} \gdef\edgeList{\operatorname{edges}} \gdef\pathList{\operatorname{paths}} \gdef\cardinalList{\operatorname{cards}} \gdef\signedCardinalList{\operatorname{cards^*}} \gdef\wordOf{\operatorname{word}} \gdef\headVertex{\operatorname{head}} \gdef\tailVertex{\operatorname{tail}} \gdef\basis{\operatorname{basis}} \gdef\split{\operatorname{split}} \gdef\lcm{\operatorname{lcm}} \gdef\minimalContractionSets{\operatorname{MCSets}} \gdef\minimalContractions{\operatorname{MC}} \gdef\grade{\operatorname{grade}} \gdef\support{\operatorname{support}} \gdef\coefficient{\operatorname{coeff}} \gdef\domain{\operatorname{domain}} \gdef\codomain{\operatorname{codomain}} \gdef\modFunction{\operatorname{mod}} \gdef\isPrime#1{#1\textrm{ prime}} \gdef\blank{\_} \gdef\emptyWord{} \gdef\multiwordSymbol#1{\mathbf{#1}} \gdef\wordSymbol#1{\mathtt{#1}} \gdef\word#1{#1} \gdef\pathMap#1{#1} \gdef\function#1{#1} \gdef\imageModifier#1{ {#1}^{\rightarrow}} \gdef\preimageModifier#1{ {#1}^{\leftarrow}} \gdef\multiImageModifier#1{ {#1}^{\Rightarrow}} \gdef\multiPreimageModifier#1{ {#1}^{\Leftarrow}} \gdef\functionComposition#1{#1} \gdef\functionCompositionSymbol{∘} \gdef\route#1#2#3{[{#1}\!:\!{#2}\!:\!{#3}]} \gdef\multiroute#1#2#3{[{#1}\!:\!{#2}\!:\!{#3}]} \gdef\pathWord#1#2#3{ {#1}\!:\!{#2}\!:\!{#3}} \gdef\nullPath{\bot} \gdef\nullElement{\bot} \gdef\path#1{#1} \gdef\vert#1{#1} \gdef\underdot#1{\underset{\raisebox{0.3em}{.}}{#1}} \gdef\tvert#1{\underdot{#1}} \gdef\hvert#1{\dot{#1}} \gdef\edge#1{#1} \gdef\card#1{\mathtt{#1}} \gdef\path#1{#1} \gdef\quiver#1{#1} \gdef\bindingRuleSymbol{\to} \gdef\compactBindingRuleSymbol{:} \gdef\cayleyQuiverSymbol#1{\selfAction{#1}} \gdef\bindCayleyQuiver#1#2{\selfAction{#1}[#2]} \gdef\bindActionQuiver#1#2{#1[#2]} \gdef\bindSize#1#2{#1(#2)} \gdef\bindCardSize#1#2{#1[#2]} \gdef\bindCards#1#2{#1[#2]} \gdef\subSize#1#2{#1_{#2}} \gdef\gridQuiver#1{\textrm{Grid}^{#1}} \gdef\treeQuiver#1{\textrm{Tree}^{#1}} \gdef\bouquetQuiver#1{\textrm{Bq}^{#1}} \gdef\lineQuiver{\textrm{L}} \gdef\cycleQuiver{\textrm{C}} \gdef\squareQuiver{\textrm{Sq}} \gdef\cubicQuiver{\textrm{Cbc}} \gdef\triangularQuiver{\textrm{Tri}} \gdef\hexagonalQuiver{\textrm{Hex}} \gdef\rhombilleQuiver{\textrm{Rmb}} \gdef\limit#1#2{\lim_{#2}\,#1} \gdef\realVectorSpace#1{\mathbb{R}^{#1}} \gdef\realVectorSpace#1{\mathbb{C}^{#1}} \gdef\matrixRing#1#2{M_{#2}(#1)} \gdef\groupoid#1{#1} \gdef\group#1{#1} \gdef\field#1{#1} \gdef\ring#1{#1} \gdef\indeterminate#1{#1} \gdef\semiring#1{#1} \gdef\sym#1{#1} \gdef\matrix#1{#1} \gdef\polynomial#1{#1} \gdef\polynomialRing#1#2{#1[{#2}]} \gdef\routeSymbol#1{#1} \gdef\multirouteSymbol#1{\mathbf{#1}} \gdef\planSymbol#1{\mathbf{#1}} \gdef\ringElement#1{#1} \gdef\matrixPart#1#2#3{#1\llbracket{#2,#3}\rrbracket} \gdef\matrixRowPart#1{#1} \gdef\matrixColumnPart#1{#1} \gdef\subMatrixPart#1#2#3{#1_{#2,#3}} \gdef\matrixDotSymbol{\cdot} \gdef\matrixPlusSymbol{+} \gdef\wordGroup#1{\wordGroupSymbol_{#1}} \gdef\wordGroupSymbol{\Omega} \gdef\wordRing#1{\wordRingSymbol_{#1}} \gdef\wordRingSymbol{\Omega\!\degree} \gdef\linearCombinationCoefficient#1{ {\textcolor{888888}{#1}}} \gdef\plan#1{#1} \gdef\planRing#1{\planRingSymbol_{#1}} \gdef\planRingSymbol{\Phi} \gdef\basisPath#1#2{\mathbf{#1}_{#2}} \gdef\basisPathWeight#1#2{ {#1}_{#2}} \gdef\unitSymbol{\mathbf{e}} \gdef\unitVertexField{\unitSymbol_1} \gdef\forwardSymbol{f} \gdef\backwardSymbol{b} \gdef\symmetricSymbol{s} \gdef\antisymmetricSymbol{a} \gdef\wordVector#1#2{\unitSymbol_{#1}^{#2}} \gdef\gradOf#1{\grad\,{#1}} \gdef\grad{\nabla} \gdef\divOf#1{\div\,{#1}} \gdef\div{\dot{\nabla}} \gdef\laplacianOf#1{\laplacian\,{#1}} \gdef\laplacian{\ddot{\nabla}} \gdef\suchThat#1#2{ {#1}|{#2}} \gdef\chart#1{\chartSymbol_{#1}} \gdef\chartSymbol{C} \gdef\graphRegionIntersectionSymbol{\cap} \gdef\graphRegionUnionSymbol{\cup} \gdef\pathIso{\simeq} \gdef\factorial#1{#1!} \gdef\power#1#2{ {#1}^{#2}} \gdef\repeatedPower#1#2{ {#1}^{#2}} \gdef\contractionLattice#1{\operatorname{Con}(#1)} \gdef\contractedRelation#1{\sim_{#1}} \gdef\isContracted#1#2{ {#1} \sim {#2}} \gdef\isContractedIn#1#2#3{ {#1} \sim_{#3} {#2}} \gdef\isNotContracted#1#2{ {#1} \not \sim {#2}} \gdef\isNotContractedIn#1#2#3{ {#1} \not \sim_{#3} {#2}} \gdef\contractionSum#1{#1} \gdef\contractionSumSymbol{\sqcup} \gdef\contractionProduct#1{#1} \gdef\contractionProductSymbol{ {\cdot}} \gdef\graph#1{#1} \gdef\graphHomomorphism#1{#1} \gdef\coversSymbol{\sqsupseteq} \gdef\coveredBySymbol{\sqsubseteq} \gdef\strictlyCoversSymbol{\sqsupset} \gdef\strictlyCoveredBySymbol{\sqsubset} \gdef\covering#1#2#3{ {#2} \sqsupseteq_{#1} {#3}} \gdef\powerSet#1{\powerSetSymbol({#1})} \gdef\powerSetSymbol{\mathscr{P}} \gdef\existsForm#1#2{\exists\,{#1}\,:\,{#2}} \gdef\forAllForm#1#2{\forall\,{#1}\,:\,{#2}} \gdef\notted#1{\notSymbol {#1}} \gdef\andSymbol{\land} \gdef\orSymbol{\lor} \gdef\notSymbol{\lnot} \gdef\latticeElement#1{#1} \gdef\latticeMeetSymbol{\wedge} \gdef\latticeJoinSymbol{\vee} \gdef\latticeTop{\top} \gdef\latticeBottom{\bot} \gdef\latticeGreaterSymbol{>} \gdef\latticeGreaterEqualSymbol{\ge} \gdef\latticeLessSymbol{<} \gdef\latticeLessEqualSymbol{\le} \gdef\grpname#1{\operatorname{\mathsf{#1}}} \gdef\mkg#1#2#3{\grpname{#1}({#2},{#3})} \gdef\mka#1#2#3{\mathfrak{#1}({#2},{#3})} \gdef\generalLinearAlgebra#1#2{\mka{gl}{#1}{#2}} \gdef\generalLinearGroup#1#2{\mkg{GL}{#1}{#2}} \gdef\specialLinearAlgebra#1#2{\mka{sl}{#1}{#2}} \gdef\specialLinearGroup#1#2{\mkg{SL}{#1}{#2}} \gdef\projectiveGeneralLinearAlgebra#1#2{\mka{pgl}{#1}{#2}} \gdef\projectiveGeneralLinearGroup#1#2{\mkg{PGL}{#1}{#2}} \gdef\projectiveSpecialLinearAlgebra#1#2{\mka{psl}{#1}{#2}} \gdef\projectiveSpecialLinearGroup#1#2{\mkg{PSL}{#1}{#2}} \gdef\orthogonalAlgebra#1#2{\mka{o}{#1}{#2}} \gdef\orthogonalGroup#1#2{\mkg{O}{#1}{#2}} \gdef\specialOrthogonalAlgebra#1#2{\mka{so}{#1}{#2}} \gdef\specialOrthogonalGroup#1#2{\mkg{SO}{#1}{#2}} \gdef\unitaryAlgebra#1{\mka{u}{#1}{#2}} \gdef\unitaryGroup#1{\mkg{U}{#1}{#2}} \gdef\specialUnitaryAlgebra#1#2{\mka{su}{#1}{#2}} \gdef\specialUnitaryGroup#1#2{\mkg{su}{#1}{#2}} \gdef\spinAlgebra#1#2{\mka{spin}{#1}{#2}} \gdef\spinGroup#1#2{\mkg{Spin}{#1}{#2}} \gdef\pinAlgebra#1#2{\mka{pin}{#1}{#2}} \gdef\pinGroup#1#2{\mkg{Pin}{#1}{#2}} \gdef\symmetricGroup#1{\grpname{Sym}({#1})} \gdef\presentation#1{#1} \gdef\groupPresentation#1#2{\left\langle\,{#1}\,\,\middle|\mathstrut\,\,{#2}\,\right\rangle} \gdef\groupRelationIso{=} \gdef\groupGenerator#1{#1} \gdef\groupRelator#1{#1} \gdef\groupElement#1{#1} \gdef\groupoidElement#1{#1} \gdef\iconstruct#1#2{ {#1}\,\,\middle|{\large\mathstrut}\,\,{#2}} \gdef\setConstructor#1#2{\left\{\,\iconstruct{#1}{#2}\,\right\}} \gdef\multisetConstructor#1#2{\left\{\mkern{-2.3pt}\left|\,\,\iconstruct{#1}{#2}\,\right|\mkern{-2.3pt}\right\}} \gdef\multisets#1{\mathscr{M}({#1})} \gdef\signedMultisets#1{\mathscr{M^*}({#1})} \gdef\setSymbol#1{#1} \gdef\multisetSymbol#1{#1} \gdef\setElementSymbol#1{#1} \gdef\multisetElementSymbol#1{#1} \gdef\multisetMultiplicitySymbol{\raisebox{.1em}{\small\#}\mkern{.1em}} \gdef\boundMultiplicityFunction#1{\operatorname{ {#1}^{\sharp}}} \gdef\constructor#1#2{\left.{#1}\,\,\middle|\mathstrut\,\,{#2}\right.} \gdef\elemOf#1#2{ { {#1} \in {#2} }} \gdef\notElemOf#1#2{ { {#1} \notin {#2} }} \gdef\edgeOf#1#2{ { {#1} {\in}_E {#2} }} \gdef\vertOf#1#2{ { {#1} {\in}_V {#2} }} \gdef\pathOf#1#2{ { {#1} {\in}_P {#2} }} \gdef\pathType#1{\operatorName{path}{#1}} \gdef\vertexType#1{\operatorName{vertex}{#1}} \gdef\edgeType#1{\operatorName{edge}{#1}} \gdef\multisetType#1{\operatorName{mset}{#1}} \gdef\signedMultisetType#1{\operatorName{mset^*}{#1}} \gdef\fromTo#1{#1} \gdef\fromToSymbol{\mapsto} \gdef\vertexCountOf#1{|{#1}|} \gdef\vertices#1{ V_{#1} } \gdef\edges#1{ E_{#1} } \gdef\vertexField#1{#1} \gdef\edgeField#1{#1} \gdef\pathVector#1{\mathbf{#1}} \gdef\pathVectorSpace#1{\mathscr{#1}} \gdef\baseField#1{#1} \gdef\finiteField#1{\mathbb{F}_{#1}} \gdef\functionSpace#1#2{#2^{#1}} \gdef\pathGroupoid#1{ { \Gamma_{#1} }} \gdef\forwardPathQuiver#1#2{ {\overrightharpoon{#1}_{#2}}} \gdef\backwardPathQuiver#1#2{ {\overrightharpoon{#1}^{#2}}} \gdef\pathQuiver#1{ {\overrightharpoon{#1}}} \gdef\mto#1#2{ {#1}\mapsto{#2}} \gdef\mtoSymbol{\mapsto} \gdef\groupWordRewriting#1{\langle{#1}\rangle} \gdef\rewrite#1#2{ {#1}\mapsto{#2}} \gdef\rewritingRule#1#2{ {#1}\mapsto{#2}} \gdef\rewritingSystem#1{\mathcal{#1}} \gdef\multiwayBFS#1{\textrm{bfs}({#1})} \gdef\rewritingStateBinding#1#2{ {\left.{#1}\!\mid\!{#2}\right.}} \gdef\rewritingRuleBinding#1#2{#1{\left[\,{#2}\,\right]}} \gdef\namedSystem#1{\mathsf{#1}} \gdef\genericRewritingSystem{\namedSystem{System}} \gdef\stringRewritingSystem{\namedSystem{Str}} \gdef\turingMachineRewritingSystem{\namedSystem{TM}} \gdef\cellularAutomatonRewritingSystem{\namedSystem{CA}} \gdef\graphRewritingSystem{\namedSystem{Gr}} \gdef\hypergraphRewritingSystem{\namedSystem{HGr}} \gdef\petriNetRewritingSystem{\namedSystem{Petri}} \gdef\ncard#1{\card{\inverted{#1}}} \gdef\mcard#1{\card{\mirror{#1}}} \gdef\nmcard#1{\card{\inverted{\mirror{#1}}}} \gdef\assocArray#1{\left\langle {#1} \right\rangle} \gdef\set#1{\{ {#1} \}} \gdef\list#1{\{ {#1} \}} \gdef\multiset#1{\lBrace {#1} \rBrace} \gdef\permutationCycle#1{#1} \gdef\permutationCycleSymbol{\to} \gdef\permutationSet#1{#1} \gdef\permutationSetSymbol{;} \gdef\transposition#1#2{ {#1} \leftrightarrow {#2}} \gdef\tuple#1{( {#1} )} \gdef\concat#1{ {#1} } \gdef\paren#1{\left( {#1} \right)} \gdef\ceiling#1{\lceil{#1}\rceil} \gdef\floor#1{\lfloor{#1}\rfloor} \gdef\translationVector#1{\left[{#1}\right]_{\textrm{T}}} \gdef\quotient#1#2{ {#1} / {#2}} \gdef\compactQuotient#1#2#3{ {#1}\;{\upharpoonright_{#2}}\;{#3}} \gdef\multilineQuotient#1#2{\frac{#1}{#2}} \gdef\idElem#1{e_{#1}} \gdef\minus#1{-{#1}} \gdef\elem{\ \in\ } \gdef\vsp{\mkern{0.4pt}} \gdef\iGmult{\vsp} \gdef\gmult{\vsp\ast\vsp} \gdef\Gmult{\vsp\ast\vsp} \gdef\gdot{\vsp\cdot\vsp} \gdef\gDot{\vsp{\,\largeDot\,}\vsp} \gdef\ellipsis{\dots} \gdef\verticalEllipsis{\vdots} \gdef\appliedRelation#1{#1} \gdef\setUnionSymbol{\cup} \gdef\setIntersectionSymbol{\cap} \gdef\setRelativeComplementSymbol{\backslash} \gdef\multisetUnionSymbol{\cup} \gdef\multisetIntersectionSymbol{\cap} \gdef\multisetRelativeComplementSymbol{\backslash} \gdef\multisetSumSymbol{+} \gdef\cartesianProductSymbol{\times} \gdef\functionSignature#1#2#3{ { {#1} : {#2} \to {#3}}} \gdef\poly#1{#1} \gdef\quiverProdPoly#1{#1} \gdef\quiverProdPower#1#2{#1^{#2}} \gdef\quiverProdTimes#1{#1} \gdef\parenLabeled#1#2{#1\ ({#2})} \gdef\parenRepeated#1#2{\parenLabeled{#1}{ {#2}\text{ times}}} \gdef\underLabeled#1#2{\underbrace{#1}_{#2}} \gdef\underRepeated#1#2{\underbrace{#1}_{#2\text{ times}}} \gdef\overLabeled#1#2{\overbrace{#1}^{#2}} \gdef\overRepeated#1#2{\overbrace{#1}^{#2\text{ times}}} \gdef\modLabeled#1#2{ {#1 }\textrm{ mod }{#2}} \gdef\freeGroup#1{F_{#1}} \gdef\cyclicGroup#1{\mathbb{Z}_{#1}} \gdef\componentSuperQuiverOfSymbol{\succ} \gdef\setCardinality#1{|{#1}|} \gdef\dependentQuiverProductSymbol{\,\times\,} \gdef\independentQuiverProductSymbol{\,⨝\,} \gdef\graphUnionSymbol{\sqcup} \gdef\graphProductSymbol{\times} \gdef\inlineProdSymbol{\mid} \gdef\serialCardSymbol{ {:}} \gdef\parallelCardSymbol{ {\mid}} \gdef\cardinalSequenceSymbol{ {:}} \gdef\cardinalProductSymbol{\inlineProdSymbol} \gdef\vertexProductSymbol{\!\inlineProdSymbol\!} \gdef\edgeProductSymbol{\inlineProdSymbol} \gdef\indexSum#1#2#3{ {\sum_{#2}^{#3} #1}} \gdef\indexProd#1#2#3{ {\prod_{#2}^{#3} #1}} \gdef\indexMax#1#2#3{ {\max_{#2}^{#3} #1}} \gdef\indexMin#1#2#3{ {\min_{#2}^{#3} #1}} \gdef\oneTo#1{1..{#1}} \gdef\zeroTo#1{0..{#1}} \gdef\qstring#1{\mathtt{"}{#1}\mathtt{"}} \gdef\qchar#1{\mathtt{'}{#1}\mathtt{'}} \gdef\lstr#1{\mathtt{#1}} \gdef\lchar#1{\mathtt{#1}} \gdef\string#1{ {#1}} \gdef\character#1{ {#1}} \gdef\homomorphismMapping#1{\assocArray{#1}} \gdef\translationPresentation#1{\textrm{Z}_{#1}} \gdef\starTranslationPresentation#1{\textrm{Z}^*_{#1}} \gdef\translationPathValuation#1{\mathcal{\overrightharpoon Z}_{#1}} \gdef\starTranslationPathValuation#1{\overrightharpoon{\mathcal{Z}^*_{#1}}} \gdef\translationWordHomomorphism#1{\mathcal{Z}_{#1}} \gdef\starTranslationWordHomomorphism#1{\mathcal{Z}^*_{#1}} \gdef\translationCardinalValuation#1{\textrm{T}_{#1}} \gdef\starTranslationCardinalValuation#1{\textrm{T}^*_{#1}} \)
Routes, plans, and adjacency

Routes, plans, and 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 the duality between multisets and certain rings, define the word ring of the word group, and use the word ring to define routes and plans, which model subjective states of knowledge about potential paths in a quiver. We obtain a duality between plans and plan matrices. We then construct a particular plan matrix that plays the role of an adjacency matrix: the adjacency plan matrix.

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},\ellipsis ,\vert{v_{\sym{n}}}} = \vertexList(\graph{G})\) is an \(\sym{n}\times \sym{n}\) matrix with entries:

\[ \matrixPart{\matrix{A}}{\matrixRowPart{\sym{i}}}{\matrixColumnPart{\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},\ellipsis ,\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 occured 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 \(\gform{\card{g}} + \rform{\card{r}}\) that can appear in their entries? To give formal meaning to this idea, we will first have to consider the word ring, which allows us to form such sums.

Word ring

The word ring, written \(\wordRingSymbol\), is the so-called group ring of the word group \(\wordGroupSymbol\): the ring of formal \(\ring{\mathbb{Z}}\)-linear combinations of elements of the group \(\wordGroupSymbol\). We will explain this idea with examples.

Example: one cardinal

For the word group \(\bindCards{\wordGroupSymbol }{\rform{\card{r}}}\), we can only form words from the single cardinal \(\rform{\card{r}}\). All of these words \(\elemOf{\groupElement{w}}{\bindCards{\wordGroupSymbol }{\rform{\card{r}}}}\) can be described by simply counting how many times the cardinal \(\rform{\card{r}}\) is repeated in \(\groupElement{w}\) (negative counts indicate that we are repeating \(\rform{\negated{\card{r}}}\) instead):

\[ \groupElement{w} = \overRepeated{\concat{\rform{\card{r}} \rform{\card{r}} \ellipsis \rform{\card{r}}}}{\sym{p}} = \groupPower{\rform{\card{r}}}{\sym{p}} \]

Therefore we can write the set of elements compactly as :

\[ \bindCards{\wordGroupSymbol }{\rform{\card{r}}} = \setConstructor{\groupPower{\rform{\card{r}}}{\sym{p}}}{\elemOf{\sym{p}}{\group{\mathbb{Z}}}} \]

Word concatenation simply adds these exponents:

\[ \groupPower{\rform{\card{r}}}{\sym{p}}\gdot \groupPower{\rform{\card{r}}}{\sym{q}} = \overRepeated{\concat{\rform{\card{r}} \ellipsis \rform{\card{r}}}}{\sym{p}}\gdot \overRepeated{\concat{\rform{\card{r}} \ellipsis \rform{\card{r}}}}{\sym{q}} = \overRepeated{\concat{\concat{\rform{\card{r}} \ellipsis \rform{\card{r}}}\,\concat{\rform{\card{r}} \ellipsis \rform{\card{r}}}}}{\sym{p} + \sym{q}} = \groupPower{\rform{\card{r}}}{\sym{p} + \sym{q}} \]

Therefore \(\bindCards{\wordGroupSymbol }{\rform{\card{r}}}\) is isomorphic to the group \(\group{\mathbb{Z}}\), the integers under addition.

The word ring \(\bindCards{\wordRingSymbol }{\rform{\card{r}}}\) consists of integer-weighted sums of elements of \(\bindCards{\wordRingSymbol }{\rform{\card{r}}}\). It is the simplest answer to the question: "how do we define addition and subtraction of group elements?". Once we allow these new operations, we can add a given group element \(\groupElement{w}\) to itself any number of times. We can keep track of the number of times we have added (or subtracted) a group element from the zero element with an integer coefficient:

\[ \overRepeated{\groupElement{w} + \groupElement{w} + \ellipsis + \groupElement{w}}{\sym{n}} = \linearCombinationCoefficient{n} \, \groupElement{w} \]

Similarly, we can add two differing group elements to each other; since they are different, these two terms of a sum remain separate:

\[ \overRepeated{\groupElement{w} + \ellipsis + \groupElement{w}}{\sym{m}} + \overRepeated{\groupElement{v} + \ellipsis + \groupElement{v}}{\sym{n}} = \linearCombinationCoefficient{m} \, \groupElement{w} + \linearCombinationCoefficient{n} \, \groupElement{v} \]

Therefore, a general element of \(\bindCards{\wordRingSymbol }{\rform{\card{r}}}\) can be written as an integral linear combination of words. We'll write the coefficients with the same symbol as the ring element to make keeping track of these easier, but we'll gray the coefficient symbol to distinguish it:

\[ \groupElement{w} = \indexSum{\linearCombinationCoefficient{w_p} \, \groupPower{\rform{\card{r}}}{\sym{p}}}{\elemOf{\sym{p}}{\group{\mathbb{Z}}}}{} \]

Sum

To add two elements \(\groupElement{w},\groupElement{v}\) of the word ring, we take formally add the two sums. Since addition is commutative, we can re-arrange the terms to group like powers of \(\rform{\card{r}}\), and we obtain a sum whose coefficients are the sums of the coefficients of \(\groupElement{w}\textAnd \groupElement{v}\):

\[ \groupElement{w} + \groupElement{v} = \indexSum{\paren{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} + \linearCombinationCoefficient{v_{\gbform{\sym{p}}}}} \, \groupPower{\rform{\card{r}}}{\gbform{\sym{p}}}}{\elemOf{\gbform{\sym{p}}}{\group{\mathbb{Z}}}}{} \]

Product

To multiply two elements \(\groupElement{w},\groupElement{v}\) of the word ring, we multiply them as sums in the normal way:

\[ \begin{aligned} \groupElement{w}\gDot \groupElement{v}\, &= \, \paren{\indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \groupPower{\rform{\card{r}}}{\gbform{\sym{p}}}}{\gbform{\sym{p}}}{}}\gDot \paren{\indexSum{\linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \groupPower{\rform{\card{r}}}{\rbform{\sym{q}}}}{\rbform{\sym{q}}}{}}\\ \, &= \, \indexSum{\paren{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \groupPower{\rform{\card{r}}}{\gbform{\sym{p}}}}\gDot \paren{\linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \groupPower{\rform{\card{r}}}{\rbform{\sym{q}}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{}\\ \, &= \, \indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \paren{\groupPower{\rform{\card{r}}}{\gbform{\sym{p}}}\gdot \groupPower{\rform{\card{r}}}{\rbform{\sym{q}}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{}\\ \, &= \, \indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \groupPower{\rform{\card{r}}}{\gbform{\sym{p}} + \rbform{\sym{q}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{}\\ \end{aligned} \]

If we "gather like powers of \(\rform{\card{r}}\)" we obtain:

\[ \begin{aligned} \groupElement{w}\gDot \groupElement{v}\, &= \, \indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \groupPower{\rform{\card{r}}}{\gbform{\sym{p}} + \rbform{\sym{q}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{}\\ \, &= \, \indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rbform{\sym{q}}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{\gbform{\sym{p}} + \rbform{\sym{q}} = \rgform{\sym{n}}}} \, \groupPower{\rform{\card{r}}}{\rgform{\sym{n}}}}{\rgform{\sym{n}}}{}\\ \, &= \, \indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rgform{\sym{n}} - \gbform{\sym{p}}}}}{\gbform{\sym{p}}}{}} \, \groupPower{\rform{\card{r}}}{\rgform{\sym{n}}}}{\rgform{\sym{n}}}{}\\ \end{aligned} \]

Sums (or integrals) of this form are generally known as convolutions.

An alternate way of presenting this result is to write \(\groupElement{w}\gDot \groupElement{v}\) "coefficientwise", that is, to define the coefficient of \(\groupPower{\rform{\card{r}}}{\rgform{\sym{n}}}\) in the product \(\groupElement{w}\gDot \groupElement{v}\) in terms of \(\groupElement{w}\textAnd \groupElement{v}\):b

\[ \coefficient(\groupElement{w}\gDot \groupElement{v},\groupPower{\rform{\card{r}}}{\rgform{\sym{n}}}) = \indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rgform{\sym{n}} - \gbform{\sym{p}}}}}{\gbform{\sym{p}}}{} \]

Example: two cardinals

Like before, we'll start with the word group \(\wordGroupSymbol [\rform{\card{r}},\bform{\card{b}}]\), whose elements look like this:

\[ \bindCards{\wordGroupSymbol }{\rform{\card{r}},\bform{\card{b}}} = \list{\word{1},\word{\rform{\card{r}}},\word{\rform{\ncard{r}}},\word{\bform{\card{b}}},\word{\bform{\ncard{b}}},\word{\rform{\card{r}}}{\rform{\card{r}}},\word{\rform{\ncard{r}}}{\rform{\ncard{r}}},\word{\rform{\card{r}}}{\bform{\card{b}}},\word{\rform{\card{r}}}{\bform{\ncard{b}}},\word{\rform{\ncard{r}}}{\bform{\card{b}}},\word{\rform{\ncard{r}}}{\bform{\ncard{b}}},\word{\bform{\card{b}}}{\rform{\card{r}}},\word{\bform{\card{b}}}{\rform{\ncard{r}}},\word{\bform{\ncard{b}}}{\rform{\card{r}}},\word{\bform{\ncard{b}}}{\rform{\ncard{r}}},\word{\bform{\card{b}}}{\bform{\card{b}}},\word{\bform{\ncard{b}}}{\bform{\ncard{b}}},\word{\rform{\card{r}}}{\rform{\card{r}}}{\rform{\card{r}}},\word{\rform{\card{r}}}{\rform{\card{r}}}{\bform{\card{b}}},\ellipsis } \]

Therefore, the word ring \(\wordRingSymbol [\rform{\card{r}},\bform{\card{b}}]\) consists of any \(\mathbb{Z}\)-linear combination of elements from \(\wordGroupSymbol [\rform{\card{r}},\bform{\card{b}}]\). An element of \(\elemOf{\groupElement{w}}{\wordRing{\quiver{2}}}\) can be written as:

\[ \groupElement{w} = \indexSum{\linearCombinationCoefficient{w_i} \, \wordSymbol{e}_{\sym{i}}}{\sym{i}}{} \]

Here, \(\wordSymbol{e} = \list{\word{1},\word{\rform{\card{r}}},\word{\rform{\ncard{r}}},\word{\bform{\card{b}}},\word{\bform{\ncard{b}}},\word{\rform{\card{r}}}{\rform{\card{r}}},\word{\rform{\ncard{r}}}{\rform{\ncard{r}}},\word{\rform{\card{r}}}{\bform{\card{b}}},\ellipsis }\) is a sequence that enumerates the elements of \(\wordRingSymbol [\rform{\card{r}},\bform{\card{b}}]\) in some order. This serves as an (infinite) basis for the word ring, and effectively allows us to model elements of the ring as infinite-dimensional integer-valued "vectors" with respect to this basis.

Sum

The sum is defined by adding the coefficients elementwise, as before:

\[ \groupElement{w} + \groupElement{v} = \indexSum{\paren{\linearCombinationCoefficient{w_{\gbform{\sym{i}}}} + \linearCombinationCoefficient{v_{\gbform{\sym{i}}}}} \, \wordSymbol{e}_{\gbform{\sym{i}}}}{\gbform{\sym{i}}}{} \]

Product

The product in the group ring is defined by expanding the product-of-sums into a sum-of-products. Each individual product is then an ordinary group multiplication, which we know how to do. We "gather the like terms" here: the coefficient of each word in the product \(\groupElement{w}\gDot \groupElement{v}\) is, by definition, the sum of the ways it can be formed as products of terms in the sums for \(\groupElement{w}\textAnd \groupElement{v}\):

\[ \begin{aligned} \groupElement{w}\gDot \groupElement{v}\, &= \, \paren{\indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \wordSymbol{e}_{\gbform{\sym{p}}}}{\gbform{\sym{p}}}{}}\gDot \paren{\indexSum{\linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \wordSymbol{e}_{\rbform{\sym{q}}}}{\rbform{\sym{q}}}{}}\\ \, &= \, \indexSum{\paren{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \wordSymbol{e}_{\gbform{\sym{p}}}}\gDot \paren{\linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \wordSymbol{e}_{\rbform{\sym{q}}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{}\\ \, &= \, \indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \paren{\groupElement{\wordSymbol{e}_{\gbform{\sym{p}}}}\gdot \groupElement{\wordSymbol{e}_{\rbform{\sym{q}}}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{}\\ \end{aligned} \]

Again, we can gather like terms, in other words, those group elements \(\wordSymbol{e}_{\rgform{\sym{k}}}\) for which \(\groupElement{\wordSymbol{e}_{\gbform{\sym{p}}}}\gdot \groupElement{\wordSymbol{e}_{\rbform{\sym{q}}}} = \wordSymbol{e}_{\rgform{\sym{k}}}\):

\[ \begin{aligned} \groupElement{w}\gDot \groupElement{v}\, &= \, \indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rbform{\sym{q}}}} \, \paren{\groupElement{\wordSymbol{e}_{\gbform{\sym{p}}}}\gdot \groupElement{\wordSymbol{e}_{\rbform{\sym{q}}}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{}\\ \, &= \, \indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_{\gbform{\sym{p}}}} \, \linearCombinationCoefficient{v_{\rbform{\sym{q}}}}}{\substack{\gbform{\sym{p}},\;\rbform{\sym{q}}}}{\groupElement{\wordSymbol{e}_{\gbform{\sym{p}}}}\gdot \groupElement{\wordSymbol{e}_{\rbform{\sym{q}}}} = \wordSymbol{e}_{\rgform{\sym{k}}}}} \, \wordSymbol{e}_{\rgform{\sym{n}}}}{\rgform{\sym{n}}}{}\\ \end{aligned} \]

Enumeration of basis elements

To define the 2-cardinal word ring \(\wordRing{\quiver{2}}\), we made use of the set of possible words \(\wordSymbol{e}_{\sym{i}}\) as a basis. It was enough that it was defined in some linear order so that we could index over it in the sum.

In the case of the 1-cardinal ring \(\wordRingSymbol [\rform{\card{r}}]\) we could use as basis the bi-infinite sequence \(\list{\ellipsis ,\repeatedPower{\rform{\card{r}}}{-2},\repeatedPower{\rform{\card{r}}}{-1},\repeatedPower{\rform{\card{r}}}{0},\repeatedPower{\rform{\card{r}}}{1},\repeatedPower{\rform{\card{r}}}{2},\ellipsis }\), indexed by \(\mathbb{Z}\). This order allowed us to rewrite the conditional inner sum \(\indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_p} \, \linearCombinationCoefficient{v_q}}{\sym{p} + \sym{q} = \sym{n}}{}} \, \groupPower{\rform{\card{r}}}{\sym{n}}}{\sym{n}}{}\) as \(\indexSum{\paren{\indexSum{\linearCombinationCoefficient{w_p} \, \linearCombinationCoefficient{v_{n - p}}}{\sym{p}}{}} \, \groupPower{\rform{\card{r}}}{\sym{n}}}{\sym{n}}{}\) since it amounted to the requirement that \(\sym{p} + \sym{q} = \sym{n}\), allowing us to solve for \(\sym{q}\) explicitly.

But for 2 or more cardinals, a linear enumeration of the basis elements is both complicated to define, and doesn't allow for such a neat arithmetic form for the inner sum. The larger point is that this linear enumeration of basis elements is a kind of holdover from traditional mathematics, where questions of computation and notation aren't usually primary, and it is useful to think about ring elements as being infinite-dimensional integer "vectors".

Luckily, it turns out there is a more combinatorial and computational way of thinking about group rings that builds them on a different interpretation. To introduce this idea, we first have to define and build intution for an underutilized structure in mathematics, the multiset.

Connection to polynomials

The elements of the word ring \(\wordRingSymbol [\rform{\card{r}}]\) look awfully similar to how one adds and multiply polynomials (where \(\rform{\card{r}}\) plays the role of the indeterminate), except in this case we allow negative powers. Indeed \(\wordRingSymbol [\rform{\card{r}}]\) is a so-called polynomial ring:

\[ \wordRingSymbol [\rform{\card{r}}]\isomorphicSymbol \polynomialRing{\ring{\mathbb{Z}}}{\rform{\card{r}},\inverse{\rform{\card{r}}}} \]

This recalls the Laurent polynomials, although the coefficients appearing in the elements of the word ring are valued in \(\mathbb{Z}\) rather than \(\mathbb{C}\).

The word ring \(\wordRing{\quiver{\sym{k}}}\) for \(\sym{k}>1\) can be thought of as consisting of multivariate, non-commutative polynomials, with negative powers allowed.

Multisets

Sets vs multisets

To contrast sets with multisets, we first repeat some basic facts about sets.

Sets are the building blocks of modern mathematics. They consist of a collection of elements: \(\sym{X} = \set{\sym{x_1},\sym{x_2},\ellipsis ,\sym{x_{\sym{n}}}}\). We can express that an element is a member of a set with the notation \(\elemOf{\setElementSymbol{x}}{\setSymbol{X}}\).

Among the fundamental properties of a sets is that the elements have no defined order. Hence, the expressions \(\set{\rform{\card{r}},\bform{\card{b}}}\textAnd \set{\bform{\card{b}},\rform{\card{r}}}\) describe the same set. Furthermore, an object is either an element of a set or it is not. It is meaningless to say that it occurs twice, for example. Hence, the expressions \(\set{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\textAnd \set{\rform{\card{r}},\bform{\card{b}}}\) describe the same set – especially when constructing sets we rely on this redundancy being irrelevant.

If we instead specify that repetition does matter, we arrive at the idea of a multiset. A multiset can contain an object more than once. The number of times a multiset contains an object will be called the multiplicity of that object.

We'll write multisets with double-struck braces: \(\sym{X} = \multiset{\sym{x_1},\sym{x_2},\ellipsis ,\sym{x_{\sym{n}}}}\). Hence, \(\multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\textAnd \multiset{\rform{\card{r}},\bform{\card{b}}}\) describe different multisets: the multiplicity of \(\rform{\card{r}}\) is \(1\) in the first and \(2\) in the second.

We’ll denote the multiplicity of an object \(\multisetElementSymbol{x}\) in a multiset \(\multisetSymbol{M}\) by \(\multisetSymbol{M}\multisetMultiplicitySymbol \multisetElementSymbol{x}\). For example, in the multiset \(\multisetSymbol{M} = \multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\), we have that \(\multisetSymbol{M}\multisetMultiplicitySymbol \rform{\card{r}} = 2\), \(\multisetSymbol{M}\multisetMultiplicitySymbol \bform{\card{b}} = 1\), and \(\multisetSymbol{M}\multisetMultiplicitySymbol \gform{\card{g}} = 0\).

The set of multisets

The powerset \(\powerSet{\multisetSymbol{B}}\) of a set \(\multisetSymbol{B}\) is the set of subsets of \(\multisetSymbol{B}\). We'll call these the sets on \(\multisetSymbol{B}\), and \(\multisetSymbol{B}\) the base set.

We can similarly form the set of multisets whose objects are taken from \(\multisetSymbol{B}\), written \(\multisets{\multisetSymbol{B}}\). We'll call this the set the multisets on \(\multisetSymbol{B}\).

Any particular object from the base set can occur an unrestricted number of times in one such multiset, so \(\multisets{\multisetSymbol{B}}\) is generally an infinite set (unless \(\multisetSymbol{B}\) is empty, that is). Let's look at some examples of this simple and natural idea.

If \(\multisetSymbol{B}\) is a singleton, that is, contains only one element, then the multisets in \(\multisets{\multisetSymbol{B}}\) can contain this element any finite number of times. Here we list some elements of the set \(\multisets{\multisetSymbol{B}}\) for \(\multisetSymbol{B} = \set{\rform{\card{r}}}\):

\[ \multisets{\set{\rform{\card{r}}}} = \set{\multiset{},\multiset{\rform{\card{r}}},\multiset{\rform{\card{r}},\rform{\card{r}}},\multiset{\rform{\card{r}},\rform{\card{r}},\rform{\card{r}}},\ellipsis } \]

Clearly, we can identify these multisets with the positive integers, since they count the number of times that \(\rform{\card{r}}\) is present.

If \(\multisetSymbol{B}\) contains two elements, then the elements of \(\multisets{\multisetSymbol{B}}\) can be identified with pairs of positive integers, counting how many times the two elements are present. Here we list some elements of the set \(\multisets{\multisetSymbol{B}}\) for \(\multisetSymbol{B} = \set{\rform{\card{r}},\bform{\card{b}}}\):

\[ \multisets{\set{\rform{\card{r}},\bform{\card{b}}}} = \set{\multiset{},\multiset{\rform{\card{r}}},\multiset{\bform{\card{b}}},\multiset{\rform{\card{r}},\rform{\card{r}}},\multiset{\rform{\card{r}},\bform{\card{b}}},\multiset{\bform{\card{b}},\bform{\card{b}}},\multiset{\rform{\card{r}},\rform{\card{r}},\rform{\card{r}}},\multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}},\ellipsis } \]

More generally, we can identify any multiset \(\elemOf{\multisetSymbol{M}}{\multisets{\multisetSymbol{B}}}\) with the function \(\functionSignature{\function{\boundMultiplicityFunction{\multisetSymbol{M}}}}{\multisetSymbol{B}}{\mathbb{N}}\) that takes an element of \(\multisetSymbol{B}\) and returns its multiplicity in \(\multisetSymbol{M}\).

For example, we can identify the multiset \(\multisetSymbol{M} = \multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}}}\) with the function \(\boundMultiplicityFunction{\multisetSymbol{M}} = \assocArray{\mto{\rform{\card{r}}}{2},\mto{\bform{\card{b}}}{1}}\).

Formally, then, we have a bijection between multisets on \(\multisetSymbol{B}\) on one side and functions from \(\multisetSymbol{B}\) to the natural numbers on the other:

\[ \multisets{\multisetSymbol{B}}\bijectiveSymbol \functionSpace{\multisetSymbol{B}}{\baseField{\mathbb{N}}} \]

We'll shortly see how we can encode the natural operations on a multiset in terms of operations on such multiplicity functions.

Sets as multisets

We can identify a set \(\multisetSymbol{X}\) with a multiset in which each element \(\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}\) appears exactly once. For example:

\[ \set{\rform{\card{r}},\bform{\card{b}}}\isomorphicSymbol \multiset{\rform{\card{r}},\bform{\card{b}}} \]

In other words, we have a bijection between on one hand \(\powerSet{\multisetSymbol{B}}\), the sets on \(\multisetSymbol{B}\), and on the other hand \(\multisets{\multisetSymbol{B}}\), multisets on \(\multisetSymbol{B}\) with maximum multiplicity 1:

\[ \powerSet{\multisetSymbol{B}}\bijectiveSymbol \setConstructor{\multisetSymbol{M}}{\elemOf{\multisetSymbol{M}}{\multisets{\multisetSymbol{B}}},\max(\boundMultiplicityFunction{\multisetSymbol{M}}) = 1} \]

To a given set \(\multisetSymbol{X}\) in terms we define the corresponding multiset via its multiplicity function \(\boundMultiplicityFunction{\multisetSymbol{X}}\):

\[ \boundMultiplicityFunction{\multisetSymbol{X}}\defEqualSymbol \mto{\setElementSymbol{b}}{\begin{cases} 1 &\text{if } \elemOf{\setElementSymbol{b}}{\multisetSymbol{X}}\\ 0 &\text{otherwise} \end{cases} } \]

Conversely, given a multiset \(\boundMultiplicityFunction{\multisetSymbol{X}}\) with \(\max(\boundMultiplicityFunction{\multisetSymbol{X}}) = 1\), we define the corresponding set \(\multisetSymbol{X}\) as follows:

\[ \multisetSymbol{X}\defEqualSymbol \setConstructor{\setElementSymbol{b}}{\elemOf{\setElementSymbol{b}}{\multisetSymbol{B}},\function{\boundMultiplicityFunction{\multisetSymbol{X}}}(\setElementSymbol{b}) = 1} \]

Operations on multisets

How can we combine multisets? We'll look to sets for inspiration.

For sets \(\multisetSymbol{X},\multisetSymbol{Y}\), we can form the union \(\multisetSymbol{X}\setUnionSymbol \multisetSymbol{Y}\) – the set of elements that are in \(\multisetSymbol{X}\) and/or \(\multisetSymbol{Y}\), the intersection \(\multisetSymbol{X}\setIntersectionSymbol \multisetSymbol{Y}\) – the set of elements in both \(\multisetSymbol{X}\textAnd \multisetSymbol{Y}\), and the relative complement \(\multisetSymbol{X}\setRelativeComplementSymbol \multisetSymbol{Y}\) – the set of elements in \(\multisetSymbol{X}\) but not in \(\multisetSymbol{Y}\).

\[ \begin{aligned} \multisetSymbol{X}\setUnionSymbol \multisetSymbol{Y}\, &\defEqualSymbol \, \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}}\orSymbol \paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{Y}}}}\\ \multisetSymbol{X}\setIntersectionSymbol \multisetSymbol{Y}\, &\defEqualSymbol \, \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}}\andSymbol \paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{Y}}}}\\ \multisetSymbol{X}\setRelativeComplementSymbol \multisetSymbol{Y}\, &\defEqualSymbol \, \setConstructor{\setElementSymbol{x}}{\paren{\elemOf{\setElementSymbol{x}}{\multisetSymbol{X}}}\andSymbol \paren{\notElemOf{\setElementSymbol{x}}{\multisetSymbol{Y}}}}\\ \end{aligned} \]

For multisets \(\multisetSymbol{M}\textAnd \multisetSymbol{N}\), we now define the equivalent operations in terms of the multiplicity functions \(\boundMultiplicityFunction{\multisetSymbol{M}}\textAnd \boundMultiplicityFunction{\multisetSymbol{N}}\):

\[ \begin{aligned} \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetUnionSymbol \multisetSymbol{N}}}\, &\defEqualSymbol \, \max(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetIntersectionSymbol \multisetSymbol{N}}}\, &\defEqualSymbol \, \min(\boundMultiplicityFunction{\multisetSymbol{M}},\boundMultiplicityFunction{\multisetSymbol{N}})\\ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetRelativeComplementSymbol \multisetSymbol{N}}}\, &\defEqualSymbol \, \max(\boundMultiplicityFunction{\multisetSymbol{M}} - \boundMultiplicityFunction{\multisetSymbol{N}},0)\\ \end{aligned} \]

Here, when we apply \(\max\textAnd \min\) to functions, we mean that e.g. \(\function{\max(\function{f},\function{g})}(\multisetElementSymbol{x})\defEqualSymbol \max(\function{f}(\multisetElementSymbol{x}),\function{g}(\multisetElementSymbol{x}))\).

We note that in the special case of multisets that represent sets, the \(\max\textAnd \min\) functions operate on multiplicites that are 0 and 1, and in this limited range behave like logical \(\andSymbol\) and \(\orSymbol\) operations, recovering the original definitions we had for sets. It's in this sense that our multiset operations generalize the set operations.

Multiset sums

An additional operation is now available to us, which is simply to sum two multisets together:

\[ \boundMultiplicityFunction{\paren{\multisetSymbol{M}\multisetSumSymbol \multisetSymbol{N}}}\defEqualSymbol \boundMultiplicityFunction{\multisetSymbol{M}} + \boundMultiplicityFunction{\multisetSymbol{N}} \]

As with \(\max\textAnd \min\), we are adding functions together in the sense that \(\function{\paren{\function{f} + \function{g}}}(\multisetElementSymbol{x})\defEqualSymbol \function{f}(\multisetElementSymbol{x}) + \function{g}(\multisetElementSymbol{x})\).

Here's an example of multiset sum, with the multiplicity function form of the sum shown as well:

\[ \begin{aligned} \multiset{\rform{\card{r}}}\, &+ \, \multiset{\rform{\card{r}},\bform{\card{b}},\bform{\card{b}}}\, &= \, \, \, &\, \multiset{\rform{\card{r}},\rform{\card{r}},\bform{\card{b}},\bform{\card{b}}}\, &\, \\ \assocArray{\mto{\rform{\card{r}}}{1},\mto{\bform{\card{b}}}{0}}\, &+ \, \assocArray{\mto{\rform{\card{r}}}{1},\mto{\bform{\card{b}}}{2}}\, &= \, \, \, &\, \assocArray{\mto{\rform{\card{r}}}{2},\mto{\bform{\card{b}}}{2}}\, &\, \\ \end{aligned} \]

Signed multisets

Images of unary and binary functions

Group rings as multisets

A concrete interpretation of an element \(\elemOf{\ringElement{ \omega }}{\wordRingSymbol }\) can be given when the integer coefficients are all positive. In this case, we can see \(\ringElement{ \omega }\) as representing a multiset of words, where the number of times a given word \(\elemOf{\groupElement{w}}{\wordGroupSymbol }\) is present in the multiset is represented by the coefficient of \(\groupElement{w}\) in the sum \(\ringElement{ \omega }\). The zero element of the ring is then just the empty multiset. But since coefficients can be negative, it is natural to extend our interpretation to see a general element \(\ringElement{ \omega }\) as representing a signed multiset, in which paths may appear in their ordinary form, or in a "negated" form, with the total multiplicity being described by the coefficient.

From now on, whenever we use the term multiset, it should be interpreted as signed multiset. This elision makes for less clunky language, but more importantly it sets up a simple and useful combinatorial interpretation of the constructions we'll consider. In each case we can still extend this intepretation to the setting of signed multisets, but doing this explicity would bog us down for no real reward.

Operations

Addition of two elements corresponds to merging of the two corresponding multisets.

But how do we multiply two multisets of words? Group rings define multiplication by linearity, where we multiply the formal combinations by distributing the two formal sums through one-another, yielding a sum of pairwise group multipliations – where the group operation in \(\wordGroupSymbol\) is the familiar the concatenation of words. Under the multiset intepretation, this corresponds to forming a multiset of all possible concatenations of a word from the first multiset and a word from the second multiset.

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, whch 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} + \ellipsis \]

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}} + \ellipsis \]

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 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 \(\tuple{\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 group 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{array}{c} 1 \le \sym{i},\sym{j} \le \sym{n} & \\ \elemOf{\wordSymbol{W}}{\matrixPart{\matrix{M}}{\sym{i}}{\sym{j}}} & \end{array} } \]

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.

Plan interpretation

We'll now propose an obvious interpretation for a matrix \(\elemOf{\matrix{M}}{\planRing{\quiver{Q}}}\): it is a collection of plans. A plan is simply a multiset of paths that take us from a "source" vertex \(\vert{v_{\sym{i}}}\) to a "destination" vertex \(\vert{v_{\sym{j}}}\). Each path in the plan represents a route we could attempt to use to go from the source to the destination. These plans are indexed by the pair of source and destination vertex, so that \(\matrixPart{\matrix{M}}{\sym{i}}{\sym{j}}\) is the multiset of the path words for the plan to go from \(\vert{v_{\sym{i}}}\) to \(\vert{v_{\sym{j}}}\). A particular plan can be the empty multiset, meaning that there is "no plan" to go from vertex \(\vert{v_{\sym{i}}}\) to \(\vert{v_{\sym{j}}}\), or it can contain several paths, representing a choice of ways to go from vertex \(\vert{v_{\sym{i}}}\) to \(\vert{v_{\sym{j}}}\). Moreover, a plan can contain invalid paths, meaning that \(\matrixPart{\matrix{M}}{\sym{i}}{\sym{j}}\) contains path words that do not describe any path in the actual quiver – this will happen when the path word references a cardinal that does not label any edge between the relevant vertices. Such a plan is called in invalid plan.

In this sense, elements of the free path ring are "subjective", representing not actual paths but potential paths that an agent might or might not be able to follow. This freedom to form invalid plans is the motivation for the term free in the name “free path ring”. We will shortly force "the rubber to meet the road" and form the (non-free) path ring, but understanding the free path ring is a useful first step.

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}\), whereever 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 form 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}}}{\begin{array}{c} \elemOf{\routeSymbol{X}}{\planSymbol{X}} & \\ \elemOf{\routeSymbol{Y}}{\planSymbol{Y}} & \end{array} } \]

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 negated cardinals below the diagonal. Why is this necessary? The reason is that we can form paths out of cardinals or their negations. In other words, we can traverse an edge \(\tde{1}{2}{\rform{\card{r}}}\) in the forward direction, yielding the path \(\pathWord{1}{\word{\rform{\card{r}}}}{2}\), or we can traverse it in the backward direction, yielding the path \(\pathWord{2}{\word{\rform{\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 negated cardinal present in entries mirrored around the diagonal.

Powers of the adjacency plan

Eigenvectors of adjacency

Plan Laplacian