It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.2K
- Applied Category Theory Course 355
- Applied Category Theory Seminar 4
- Exercises 149
- Discussion Groups 49
- How to Use MathJax 15
- Chat 480
- Azimuth Code Project 108
- News and Information 145
- Azimuth Blog 149
- Azimuth Forum 29
- Azimuth Project 189
- - Strategy 108
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 711
- - Latest Changes 701
- - - Action 14
- - - Biodiversity 8
- - - Books 2
- - - Carbon 9
- - - Computational methods 38
- - - Climate 53
- - - Earth science 23
- - - Ecology 43
- - - Energy 29
- - - Experiments 30
- - - Geoengineering 0
- - - Mathematical methods 69
- - - Meta 9
- - - Methodology 16
- - - Natural resources 7
- - - Oceans 4
- - - Organizations 34
- - - People 6
- - - Publishing 4
- - - Reports 3
- - - Software 21
- - - Statistical methods 2
- - - Sustainability 4
- - - Things to do 2
- - - Visualisation 1
- General 39

Options

In Section 3.2.1 of *Seven Sketches* - and please download today's new version of the book! - Brendan Fong and David Spivak describe a nice way to get categories from graphs. It's very simple, yet important for building databases.

Here's the basic idea. Start with a graph, for example this:

It has a bunch of "edges", like \(f,g,h,i\), going between "nodes" like \(A,B,C,D\). Then build a category where the objects are the nodes and the morphisms are the paths of edges. We compose morphisms by attaching one path onto the end of another.

For example \(f\) is a path of length 1 from \(A\) to \(B\), so it gives a morphism \(f: A \to B \). \(h\) is a path of length 1 from \(B\) to \(D\), so it gives a morphism \(g: B \to D\). We can compose these two morphisms and get \(h \circ f : A \to D\), which is a path of length 2 from \(A\) to \(D\).

There's also another morphism from \(A\) to \(D\), namely \(i \circ g : A \to D\).

In this example the longest paths have length 2, but in general a path could have any natural number as its length, including 0. Paths of length 0 are important because they give the identity morphisms in our category. For example, there's a path of length 0 from \(A\) to \(A\), which you can't see because it has no edges! It gives the identity morphisms \(1_A: A \to A\).

When we build a category from a graph this way, it's called the **free category** on that graph. And if we call the graph \(G\), we call the free category on that graph \(\mathbf{Free}(G)\).

I should warn you that different people mean different things by "graph", depending on:

- whether we put arrows on the edges,
- whether we allow more than one edge going from one node to another,
- whether we allow edges going from a node to itself,
- whether the edges have names, and
- whether we allow infinitely many nodes and edges.

But category theorists have a very specific thing in mind when we say "graph". We are very generous: we say *yes* to all these questions!

So, for example, we allow this graph:

This graph has just one edge. But the free category on this graph has infinitely many morphisms, namely $$ 1_z : z \to z $$ $$ s : z \to z $$ $$ s \circ s : z \to z $$ $$ s \circ s \circ s : z \to z $$ and so on. There's one morphism for each natural number. In fact, this is how category theorists often think about the natural numbers!

We also allow this graph:

**Puzzle 104.** How many paths of length \(n\) go from \(x\) to \(x\) in this graph?

The answer is a famous sequence of numbers. So, you're getting a famous sequence from the free category on a graph!

It may sound complicated to let our graphs have so many features, but it's actually more complicated to *disallow* them. The category theorists' definition of graph is very simple:

**Definition.** A **graph** \(G\) is a set \(N\) of **nodes**, a set \(E\) of **edges**, a function \(s : E \to N\) assigning each edge its **source**, and a function \(t: E \to N\) assigning each edge its **target**.

You can visualize the source and target of an edge using this picture:

but remember: it's possible to have \(s(e) = t(e)\).

If you're a stickler for detail, you may also want to see the precise definition of a "path":

**Definition.** Given a graph, a **path** from a node \(x\) to a node \(y\) is a finite sequence of edges \((e_1, \dots, e_n)\) with

$$ s(e_1) = x, \quad t(e_1) = s(e_2), \quad \dots, \quad t(e_{n-1}) = s(e_n), \quad t(e_n) = y. $$
Here \(n = 0, 1, 2, 3, \dots\) is called the **length** of the path.

Okay, I think that's enough for today! Next time we'll use this idea to think about databases. For now you should try these exercises, or at least look at other students' solutions:

**Exercise 3.** Show that \(\textbf{Free}(G)\) really is a category.

**Exercise 4.** Completely work out the set of morphisms between each pair of objects in the category called \(\textbf{3}\), which is

$$ \textbf{Free}( [ v_1 \overset{f_1}{\rightarrow} v_2 \overset{f_2}{\rightarrow} v_3 ] ) .$$
**Exercise 5.** The category \(\textbf{3}\) is an example of a general idea. For each natural number \(n\) there's a category \(\mathbf{n}\) that works the same way. Figure out what it is, and figure out the total number of morphisms in this category!

And here's a puzzle for people who love numbers. I'll admit it: I love numbers. But math is not only about numbers, so if you don't love them, don't worry: this puzzle is not important for this course, though it *is* part of a big subject in math:

**Puzzle 105**. It's been known since at least the fifth century BC that
$$ \sqrt 2 = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots\,}}}}} $$
If we cut off this continued fraction we get these rational approximations to \(\sqrt{2}\):
$$ \frac11, \frac32, \frac75, \frac{17}{12}, \frac{41}{29}, \frac{99}{70}, \dots$$
where the denominator of the \(n\)th fraction in this list is called the **Pell number** \(P_n\) and the numerator is \(P_n + P_{n-1}\). Find a graph with two nodes \(x\) and \(y\) such that the number of paths of length \(n\) from \(x\) to \(y\)
is the \(n\)th Pell number.

## Comments

Ex 3). Objects - nodes - Ok -1. Morphisms - {f,h,g,i} -Ok -2. Identities - Ok -3. Associative feature also holds -4 - verified 1,2,3,4 true, then it´s a category. Preorder-no.. ok?

`Ex 3). Objects - nodes - Ok -1. Morphisms - {f,h,g,i} -Ok -2. Identities - Ok -3. Associative feature also holds -4 - verified 1,2,3,4 true, then it´s a category. Preorder-no.. ok?`

When \(n=0\), \[\lbrace id_x \rbrace, \\ 1, \] when \(n=1\), \[\lbrace f \rbrace, \\ 1, \] when \(n=2\), \[\lbrace f\circ f, g \circ h \rbrace, \\ 2, \] when \(n=3\), \[\lbrace f\circ f\circ f, f\circ g \circ h, g\circ h\circ f \rbrace, \\ 3, \] when \(n=4\), \[\lbrace f\circ f\circ f\circ f, f\circ f\circ g \circ h, f\circ g \circ h\circ f, g\circ h\circ f \circ f, g\circ h\circ g \circ h \rbrace, \\ 5,\\ \] when \(n=5\), \[\lbrace f\circ f\circ f\circ f\circ f, f\circ f\circ f\circ g \circ h, f\circ f\circ g\circ h\circ f, f\circ g\circ h\circ f \circ f, \\ g\circ h\circ f\circ f\circ f, g\circ h\circ g\circ h\circ f, g\circ h\circ f\circ g\circ h, f\circ g\circ h\circ g \circ h \rbrace, \\ 8,\\ \cdots \]

It's the old Fibonacci sequence.

`><center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/graph_f.png"></center> >**Puzzle 104.** How many paths of length \\(n\\) go from \\(x\\) to \\(x\\) in this graph? >The answer is a famous sequence of numbers. So, you're getting a famous sequence from the free category on a graph! When \\(n=0\\), \\[\lbrace id_x \rbrace, \\\\ 1, \\] when \\(n=1\\), \\[\lbrace f \rbrace, \\\\ 1, \\] when \\(n=2\\), \\[\lbrace f\circ f, g \circ h \rbrace, \\\\ 2, \\] when \\(n=3\\), \\[\lbrace f\circ f\circ f, f\circ g \circ h, g\circ h\circ f \rbrace, \\\\ 3, \\] when \\(n=4\\), \\[\lbrace f\circ f\circ f\circ f, f\circ f\circ g \circ h, f\circ g \circ h\circ f, g\circ h\circ f \circ f, g\circ h\circ g \circ h \rbrace, \\\\ 5,\\\\ \\] when \\(n=5\\), \\[\lbrace f\circ f\circ f\circ f\circ f, f\circ f\circ f\circ g \circ h, f\circ f\circ g\circ h\circ f, f\circ g\circ h\circ f \circ f, \\\\ g\circ h\circ f\circ f\circ f, g\circ h\circ g\circ h\circ f, g\circ h\circ f\circ g\circ h, f\circ g\circ h\circ g \circ h \rbrace, \\\\ 8,\\\\ \cdots \\] It's the old Fibonacci sequence.`

Keith wrote:

Yep. One way to see this is as a dynamical system: state \(x\) represents adult rabbits, and state \(y\) represents newborn / immature rabbits. With a single step of the system, all mature rabbits remain mature; mature rabbits spawn one newborn rabbit each; and any existing newborn rabbits become mature.

Well, this is the story I learned from The Number Devil, at any rate.

`[Keith wrote](https://forum.azimuthproject.org/discussion/comment/18793/#Comment_18793): > It's the old Fibonacci sequence. Yep. One way to see this is as a dynamical system: state \\(x\\) represents adult rabbits, and state \\(y\\) represents newborn / immature rabbits. With a single step of the system, all mature rabbits remain mature; mature rabbits spawn one newborn rabbit each; and any existing newborn rabbits become mature. Well, this is the story I learned from [The Number Devil](https://en.wikipedia.org/wiki/The_Number_Devil), at any rate.`

Right! Let's spell it out: a path \(\gamma: x \to x\) of length \(n \ge 2 \) must either be of the form \( f \circ \delta\) for some path \(\delta : x \to x\) of length \(n-1\), or of the form \( h \circ g \circ \delta \) for some path \(\delta : x \to x\) of length \(n-2\). So, if \(F_n\) is the number of paths of length \(n\), we must have

$$ F_n = F_{n-1} + F_{n-2} $$ for \(n \ge 2\), but also it's easy to see \(F_0 = F_1 = 1\). Fibonacci!

Another way to say it is that the Fibonacci number \(F_n\) counts the number of ways to write \(n\) as an

orderedsum of 1's and 2's. For example$$ 4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 2 + 2 $$ so the fourth Fibonacci number is 5.

`Right! Let's spell it out: a path \\(\gamma: x \to x\\) of length \\(n \ge 2 \\) must either be of the form \\( f \circ \delta\\) for some path \\(\delta : x \to x\\) of length \\(n-1\\), or of the form \\( h \circ g \circ \delta \\) for some path \\(\delta : x \to x\\) of length \\(n-2\\). So, if \\(F_n\\) is the number of paths of length \\(n\\), we must have \[ F_n = F_{n-1} + F_{n-2} \] for \\(n \ge 2\\), but also it's easy to see \\(F_0 = F_1 = 1\\). Fibonacci! Another way to say it is that the Fibonacci number \\(F_n\\) counts the number of ways to write \\(n\\) as an _ordered_ sum of 1's and 2's. For example \[ 4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 2 + 2 \] so the fourth Fibonacci number is 5.`

Puzzle 105.This is a great question.Here's my quick stab at an answer:

`**Puzzle 105.** This is a great question. Here's my quick stab at an answer: ![](https://svgshare.com/i/6t2.svg)`

By the way, Keith, you're writing \(g \circ h\) to mean "do first \(g\) and then \(h\)", while most category theorists - and in particular me - use it to mean "do first \(h\) and then \(g\)", just as we do for functions, where

$$ (g \circ h) (x) = g(h(x)) . $$ I mention this just because it's possible to get very confused when different people are using different systems without knowing it.

Computer scientists sometimes use \(g ; h\) to mean "do first \(g\) and then \(h\)", and that's a nice notation where the first thing comes first yet we don't get confused.

`By the way, Keith, you're writing \\(g \circ h\\) to mean "do first \\(g\\) and then \\(h\\)", while most category theorists - and in particular me - use it to mean "do first \\(h\\) and then \\(g\\)", just as we do for functions, where \[ (g \circ h) (x) = g(h(x)) . \] I mention this just because it's possible to get very confused when different people are using different systems without knowing it. Computer scientists sometimes use \\(g ; h\\) to mean "do first \\(g\\) and then \\(h\\)", and that's a nice notation where the first thing comes first yet we don't get confused.`

Yeah, I noticed that after the fact.

We'll just say we're working with the opposite category because flipping all those morphisms is a lot of work.

`Yeah, I noticed that after the fact. We'll just say we're working with the opposite category because flipping all those morphisms is a lot of work.`

Or, we could say you redefined "\(g\)" to mean "\(h\)", and vice versa. :)

`Or, we could say you redefined "\\(g\\)" to mean "\\(h\\)", and vice versa. :)`

Keith said:

John said:

Hey, this category is isomorphic to its dual! :D

`Keith said: > We'll just say we're working with the opposite category because flipping all those morphisms is a lot of work. John said: > Or, we could say you redefined "\\(g\\)" to mean "\\(h\\)", and vice versa. :) Hey, this category is isomorphic to its dual! :D`

@John

So... I have been trying to write up how to use Lawvere's fixed point theorem to prove Gödel's second incompleteness theorem as per our discussion.

In Lawvere's 1969 paper I think he used the opposite convention for composition :

(the above is from page 4)

It's confusing!

`@John > By the way, Keith, you're writing \\(g \circ h\\) to mean "do first \\(g\\) and then \\(h\\)", while most category theorists - and in particular me - use it to mean "do first \\(h\\) and then \\(g\\)", just as we do for functions, where > > \[ (g \circ h) (x) = g(h(x)) . \] So... I have been trying to write up how to use Lawvere's fixed point theorem to prove Gödel's second incompleteness theorem as per our discussion. In [Lawvere's 1969](http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf) paper I think he used the opposite convention for composition : > Taking the case \\(X = 1\\), one has that every \\(f : A \to Y\\) gives rise to a unique \\( \ulcorner f \urcorner : 1\to Y^A\\) and that every \\(1 \to Y^A\\) is of that form for a unique \\(f\\). > Since for every \\(a : 1\to A\\) one has (dropping the indices \\(A\\), \\(Y\\) on \\(\epsilon\\) when they are clear) > \\[ \langle a, \ulcorner f\urcorner \rangle = a.f \\] > one calls the “evaluation” natural transformation; note however that we do not assume > in general that \\( f\\) is determined by the knowledge of all its “values” \\(a.f\\) (the above is from page 4) It's confusing!`

Can any strictly increasing monotonic sequence of natural numbers be created from length concatenation of edges of a graph? If not, what is a counterexample?

`Can any strictly increasing monotonic sequence of natural numbers be created from length concatenation of edges of a graph? If not, what is a counterexample?`

@KeithEPeterson I presume you mean...

Puzzle 104+. Given an arbitrary connected graph having a node labeled 'x', how many paths of length 'n' go from 'x' to 'x' in that graph? Where the resulting function \( H: \mathbb{N} \rightarrow \mathbb{N} \) is used to produce a sequence. For which sequences is it possible to construct a graph which encodes the sequence?Edit: Make the question more general

Edit: Make it a puzzle

Edit: Strike monotonic

EditStated another way... Given a function as defined above... $$ J : \textbf{Graph} \rightarrow ( \mathbb{N} \rightarrow \mathbb{N} ) $$ Does \(J\) have an inverse? Does \(J\) have a right adjoint? $$ J^{-1} : ( \mathbb{N} \rightarrow \mathbb{N} ) \rightarrow \textbf{Graph} $$`[@KeithEPeterson](https://forum.azimuthproject.org/discussion/comment/18803/#Comment_18803) I presume you mean... **Puzzle 104+**. Given an arbitrary connected graph having a node labeled 'x', how many paths of length 'n' go from 'x' to 'x' in that graph? Where the resulting function \\( H: \mathbb{N} \rightarrow \mathbb{N} \\) is used to produce a sequence. For which sequences is it possible to construct a graph which encodes the sequence? [Edit: Make the question more general](https://forum.azimuthproject.org/discussion/comment/18810/#Comment_18810) [Edit: Make it a puzzle](https://forum.azimuthproject.org/discussion/comment/18805/#Comment_18805) [Edit: Strike monotonic](https://forum.azimuthproject.org/discussion/comment/18810/#Comment_18810) **Edit** Stated another way... Given a function as defined above... \[ J : \textbf{Graph} \rightarrow ( \mathbb{N} \rightarrow \mathbb{N} ) \] Does \\(J\\) have an inverse? Does \\(J\\) have a right adjoint? \[ J^{-1} : ( \mathbb{N} \rightarrow \mathbb{N} ) \rightarrow \textbf{Graph} \]`

Are you making a puzzle, Fredrick?

`Are you making a puzzle, Fredrick?`

@KeithEPeterson I thought I was restating your puzzle. Generating graphs that encode monotonically increasing functions on the natural numbers sounds interesting.

`@KeithEPeterson I thought I was restating your puzzle. Generating graphs that encode monotonically increasing functions on the natural numbers sounds interesting.`

I wasn't really making a puzzle, but conjecturing out loud.

Though, you should make that into a puzzle.

Edit: The reasoning I'm thinking out loud is because every strictly increasing monotonic sequence of natural numbers has an associated real number attached to it (Beatty sequences).

It would, therefore, stand to reason that if every such sequence also has a graph, that we could then associate to each graph the real number that's associated to each sequence.

`I wasn't really making a puzzle, but conjecturing out loud. Though, you should make that into a puzzle. Edit: The reasoning I'm thinking out loud is because every strictly increasing monotonic sequence of natural numbers has an associated real number attached to it ([Beatty sequences](https://en.wikipedia.org/wiki/Beatty_sequence#)). It would, therefore, stand to reason that if every such sequence also has a graph, that we could then associate to each graph the real number that's associated to each sequence.`

Matthew wrote:

It's not

veryconfusing, because he is deliberately using the nonstandard notation \(a . f\) to mean "do first \(a\), then \(f\)". That's just a variant of the computer scientist's \(a ; f\). It only getsveryconfusing when people use \(a \circ f\) to mean "do first \(a\), then \(f\)", because 99.5% of mathematicians use it to mean "do first \(f\), then \(a\)".I'll admit to having been one of the 0.5%. But that was when I was young and didn't choose my battles wisely!

`Matthew wrote: > It's confusing! It's not _very_ confusing, because he is deliberately using the nonstandard notation \\(a . f\\) to mean "do first \\(a\\), then \\(f\\)". That's just a variant of the computer scientist's \\(a ; f\\). It only gets _very_ confusing when people use \\(a \circ f\\) to mean "do first \\(a\\), then \\(f\\)", because 99.5% of mathematicians use it to mean "do first \\(f\\), then \\(a\\)". I'll admit to having been one of the 0.5%. But that was when I was young and didn't choose my battles wisely!`

Keith wrote:

I have a hunch that the sequence must have a strictly increasing derivative (well, divided difference) everywhere. For instance, every sequence \(p_i = 1, 3, 4, \cdots\) is unobtainable, since in order to go from one null path to three unit-length paths, you must have three self-loops on the start vertex. The next step would multiple those three unit-length paths into nine length-two paths.

EDIT:Strictly increasing, not positive. Positive derivative just means monotonic function; I expect that the derivativeitselfneeds to be monotonic, too, as a necessary (but perhaps insufficient) condition.`[Keith wrote](https://forum.azimuthproject.org/discussion/comment/18803/#Comment_18803): > Can any strictly increasing monotonic sequence of natural numbers be created from length concatenation of edges of a graph? If not, what is a counterexample? I have a hunch that the sequence must have a strictly increasing derivative (well, [divided difference](https://en.wikipedia.org/wiki/Finite_difference)) everywhere. For instance, every sequence \\(p_i = 1, 3, 4, \cdots\\) is unobtainable, since in order to go from one null path to three unit-length paths, you must have three self-loops on the start vertex. The next step would multiple those three unit-length paths into nine length-two paths. **EDIT:** Strictly increasing, not positive. Positive derivative just means monotonic function; I expect that the derivative _itself_ needs to be monotonic, too, as a necessary (but perhaps insufficient) condition.`

Fredrick puzzled:

No, there's not one for

$$ 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, \dots $$ I leave it as a puzzle to figure out why!

I don't think "monotonic" is especially relevant here. For example, it's pretty easy to find graphs where the number of paths from \(x\) to \(x\) goes like

$$ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, \dots $$ or

$$ 1, 0, 0, 2, 0, 0, 4, 0, 0, 8, 0, 0, 16, 0, 0, \dots $$

`Fredrick puzzled: > Is there a graph for every possible monotonic sequence? No, there's not one for \[ 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, \dots \] I leave it as a puzzle to figure out why! I don't think "monotonic" is especially relevant here. For example, it's pretty easy to find graphs where the number of paths from \\(x\\) to \\(x\\) goes like \[ 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, \dots \] or \[ 1, 0, 0, 2, 0, 0, 4, 0, 0, 8, 0, 0, 16, 0, 0, \dots \]`

John wrote:

Aha -- rose graphs! (Except each petal has its own vertex, rather than all petals being self-loops.)

EDIT: You added more zeroes when I refreshed. :(`John wrote: > \[ 1, 0, 2, 0, 4, 0, 8, 0, 16, 0, \dots \] Aha -- [rose graphs](https://en.wikipedia.org/wiki/Rose_(topology))! (Except each petal has its own vertex, rather than all petals being self-loops.) **EDIT**: You added more zeroes when I refreshed. :(`

Sorry, I decided to add more zeros, just to spice it up! Both sequences describe the number of paths of length \(n\) for some graph.

`Sorry, I decided to add more zeros, just to spice it up! Both sequences describe the number of paths of length \\(n\\) for some graph.`

Considering fibonacci - golden ratio relation, is it possible to devise a explict connection/translation between the puzzle 104´s graph and the x²=1+x equation?

`Considering fibonacci - golden ratio relation, is it possible to devise a explict connection/translation between the puzzle 104´s graph and the x²=1+x equation?`

Here's my attempt -

Assume you want to compute the number of paths of length \(n\), starting from \(x\). You can start counting by taking one of two paths:

Let \(f_n\) be the number of paths. Then

\[ f_n = f_{n-1} + f_{n-2} \tag{★} \]

Now consider

\[ \phi := \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}} \]

With (★) we have

\[ \begin{align} \phi & = \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}} \\ & = \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-1} + f_{n-2}}{f_{n-1}} \\ & = \underset{n \to \infty}{\mathrm{lim}} \left(1 + \frac{f_{n-2}}{f_{n-1}} \right) \\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-2}}{f_{n-1}} \\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-1}}{f_{n}} \\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \left(\frac{f_{n}}{f_{n-1}}\right)^{-1} \\ & = 1 + \left(\underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}}\right)^{-1} \\ & = 1 + \phi^{-1} \\ \end{align} \]

Hence \(\phi = 1 + \phi^{-1}\). Now multiply both sides by \(\phi\). This gives:

\[ \phi^2 = \phi + 1 \]

...as you wanted to see...

`> Considering fibonacci - golden ratio relation, is it possible to devise a explict connection/translation between the puzzle 104's graph and the x²=1+x equation? Here's my attempt - Assume you want to compute the number of paths of length \\(n\\), starting from \\(x\\). You can start counting by taking one of two paths: - Go along \\(f\\), and end up at \\(x\\). Then count the number paths of length \\(n - 1\\) - Go along \\(h \circ g\\), and end up at \\(x\\) again. Then count the number of paths of length \\(n - 2\\). Let \\(f_n\\) be the number of paths. Then \\[ f_n = f_{n-1} + f_{n-2} \tag{★} \\] Now consider \\[ \phi := \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}} \\] With (★) we have \\[ \begin{align} \phi & = \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}} \\\\ & = \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-1} + f_{n-2}}{f_{n-1}} \\\\ & = \underset{n \to \infty}{\mathrm{lim}} \left(1 + \frac{f_{n-2}}{f_{n-1}} \right) \\\\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-2}}{f_{n-1}} \\\\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \frac{f_{n-1}}{f_{n}} \\\\ & = 1 + \underset{n \to \infty}{\mathrm{lim}} \left(\frac{f_{n}}{f_{n-1}}\right)^{-1} \\\\ & = 1 + \left(\underset{n \to \infty}{\mathrm{lim}} \frac{f_{n}}{f_{n-1}}\right)^{-1} \\\\ & = 1 + \phi^{-1} \\\\ \end{align} \\] Hence \\(\phi = 1 + \phi^{-1}\\). Now multiply both sides by \\(\phi\\). This gives: \\[ \phi^2 = \phi + 1 \\] ...as you wanted to see...`

Puzzle 105: I can't see Matthew's answer in comment #5, so I will write my own. Following what John wrote in comment #4, it seems like it should be sufficient to add an arrow \(k\) from \(x\) to itself. That way, every path of length \(n+2\) will come from composing either \(f\) or \(k\) with a path of length \(n+1\), or composing \(h\circ g\) with a path of length \(n\). Since this gives the recurrence relation $$P_{n+2}=2P_{n+1}+P_n$$ that is satisfied by the Pell numbers (with \(P_0=1\) and \(P_1=2\) due to \(\{\text{id}_x\}\) being the only path starting and ending at \(x\) of length zero and \(\{f\},\{k\}\) being the only paths of length one).Generalizing slightly, one can get any recursion relation of the form $$a_{n+2}=\alpha a_{n+1}+\beta a_n\qquad\text{for }\alpha,\beta\in\mathbb{N}$$ by starting with the node \(x\) and its identity arrow, and adding \(\alpha\) arrows from \(x\) to itself and \(\beta\) nodes, each with a pair of arrows connecting each node to the node \(x\) (restricting to the case with just two nodes, \(x\) and \(y\), one can get any \(\alpha\in\mathbb{N}\) and square betas \(\beta=m^2, \forall m\in\mathbb{N}\) with the appropriate arrows).

To every recursion relation with specified base case(s) there is associated a generating function. For example, for $$F_{n+2}=F_{n+1}+F_n\qquad\text{with }P_0=1,\,P_1=1$$ there is associated the generating function $$F(z)=\frac{1}{1-z-z^2},$$ which has the Fibbonacci sequence as the sequence of coefficients in its formal power-series expansion. Does the generating function associated with a graph tell us anything interesting about the graph?

`**Puzzle 105**: I can't see Matthew's answer in [comment #5](https://forum.azimuthproject.org/discussion/comment/18796/#Comment_18796), so I will write my own. Following what John wrote in [comment #4](https://forum.azimuthproject.org/discussion/comment/18795/#Comment_18795), it seems like it should be sufficient to add an arrow \\(k\\) from \\(x\\) to itself. That way, every path of length \\(n+2\\) will come from composing either \\(f\\) or \\(k\\) with a path of length \\(n+1\\), or composing \\(h\circ g\\) with a path of length \\(n\\). Since this gives the recurrence relation $$P_{n+2}=2P_{n+1}+P_n$$ that is satisfied by the Pell numbers (with \\(P_0=1\\) and \\(P_1=2\\) due to \\(\\{\text{id}_x\\}\\) being the only path starting and ending at \\(x\\) of length zero and \\(\\{f\\},\\{k\\}\\) being the only paths of length one). Generalizing slightly, one can get any recursion relation of the form $$a_{n+2}=\alpha a_{n+1}+\beta a_n\qquad\text{for }\alpha,\beta\in\mathbb{N}$$ by starting with the node \\(x\\) and its identity arrow, and adding \\(\alpha\\) arrows from \\(x\\) to itself and \\(\beta\\) nodes, each with a pair of arrows connecting each node to the node \\(x\\) (restricting to the case with just two nodes, \\(x\\) and \\(y\\), one can get any \\(\alpha\in\mathbb{N}\\) and square betas \\(\beta=m^2, \forall m\in\mathbb{N}\\) with the appropriate arrows). To every recursion relation with specified base case(s) there is associated a generating function. For example, for $$F_{n+2}=F_{n+1}+F_n\qquad\text{with }P_0=1,\,P_1=1$$ there is associated the generating function $$F(z)=\frac{1}{1-z-z^2},$$ which has the Fibbonacci sequence as the sequence of coefficients in its formal power-series expansion. Does the generating function associated with a graph tell us anything interesting about the graph?`

The sequence given by \(a_0=1\), \(a_1=0\), \(a_{n+2}=4a_n\), i.e., \(1,0,4,0,16,...,0,2^{n},0,2^{n+2},...\) can be obtained from either the graph with two nodes \(x\) and \(y\) with non-identity arrows \(g,g':x\to y\), \(h,h':y\to x\), or from the graph with five nodes \(x\), \(y_i\) where \(i\in\{1,2,3,4\}\) and arrows \(g_i:x\to y_i\) and \(h_i:y_i\to x\).

Fredrick wrote:

Since there are cases where at least two graphs give the same sequence, J is not injective, so it cannot have an inverse.

`The sequence given by \\(a_0=1\\), \\(a_1=0\\), \\(a_{n+2}=4a_n\\), i.e., \\(1,0,4,0,16,...,0,2^{n},0,2^{n+2},...\\) can be obtained from either the graph with two nodes \\(x\\) and \\(y\\) with non-identity arrows \\(g,g':x\to y\\), \\(h,h':y\to x\\), or from the graph with five nodes \\(x\\), \\(y_i\\) where \\(i\in\\{1,2,3,4\\}\\) and arrows \\(g_i:x\to y_i\\) and \\(h_i:y_i\to x\\). [Fredrick wrote](https://forum.azimuthproject.org/discussion/comment/18804/#Comment_18804): >\[ J : \textbf{Graph} \rightarrow ( \mathbb{N} \rightarrow \mathbb{N} ) \] Does \\(J\\) have an inverse? Does \\(J\\) have a right adjoint? Since there are cases where at least two graphs give the same sequence, J is not injective, so it cannot have an inverse.`

If you still can't see my diagram, you should know this is my solution (I didn't write the justification, though).

`> Following what John wrote in [comment #4](https://forum.azimuthproject.org/discussion/comment/18795/#Comment_18795), it seems like it should be sufficient to add an arrow \\(k\\) from \\(x\\) to itself. If you still can't see my diagram, you should know this is my solution (I didn't write the justification, though).`

Re composition on the left or the right – there's a very neat approach to this in this textbook:

Berwick & Keating: Categories and Modules

The authors define two types of categories –

right categorieswhereffollowed bygis writtengf, andleft categorieswhere it is writtenfg. So every category has a "chirality" (left or right), and every functor can be co-chiral or contra-chiral. In particular we have a contra-chiral "mirror functor" that sends every category to its mirror (same objects, same arrows in the same direction, but composition is the other way round).The motivation for this is they want to deal with bimodules over non-commutative rings, where one ring acts on the left and the other acts on the right. So they need to treat both conventions equally, and have a clean way of switching back and forth.

It took me a little time to understand why one might want to think of chirality as a structural feature of a category relating to how composition is defined, as opposed to a mere "matter of notation". But I do like the way it doesn't arbitrarily choose one convention as normal and the other as perverse.

And it fits with practical computer programming – many languages use both left and right composition (eg in JavaScript functions are written on the left

`foo(bar)`

while methods are written on the right`bar.foo()`

).`Re composition on the left or the right – there's a very neat approach to this in this textbook: [Berwick & Keating: Categories and Modules](http://www.cambridge.org/gb/academic/subjects/mathematics/algebra/categories-and-modules-k-theory-view?format=HB&isbn=9780521632768#Et30rSgOpdXmwcab.97) The authors define two types of categories – *right categories* where **f** followed by **g** is written **gf**, and *left categories* where it is written **fg**. So every category has a "chirality" (left or right), and every functor can be co-chiral or contra-chiral. In particular we have a contra-chiral "mirror functor" that sends every category to its mirror (same objects, same arrows in the same direction, but composition is the other way round). The motivation for this is they want to deal with bimodules over non-commutative rings, where one ring acts on the left and the other acts on the right. So they need to treat both conventions equally, and have a clean way of switching back and forth. It took me a little time to understand why one might want to think of chirality as a structural feature of a category relating to how composition is defined, as opposed to a mere "matter of notation". But I do like the way it doesn't arbitrarily choose one convention as normal and the other as perverse. And it fits with practical computer programming – many languages use both left and right composition (eg in JavaScript functions are written on the left `foo(bar)` while methods are written on the right `bar.foo()`).`

The identity morphism is a path of length zero! For some reason I never tried to see it that way. Since all composites exist (say, because it's easy to check – proving that two paths commute is the hard part) I always thought of all links (conflating paths and arrows) as essentially having length 1. Which sort of works, too, but having paths and arrows separate like this is nice!

Regarding puzzle 104, hah, there's just one canonically famous sequence... However, I had to look twice to get rid of the feeling that things should get multiplied somehow.

It seems we should call these categories Fibonacci and Pell. Is that something people do?

`The identity morphism is a path of length zero! For some reason I never tried to see it that way. Since all composites exist (say, because it's easy to check – proving that two paths commute is the hard part) I always thought of all links (conflating paths and arrows) as essentially having length 1. Which sort of works, too, but having paths and arrows separate like this is nice! Regarding puzzle 104, hah, there's just one canonically famous sequence... However, I had to look twice to get rid of the feeling that things should get multiplied somehow. It seems we should call these categories Fibonacci and Pell. Is that something people do?`

Fredrick wrote approximately:

(Here \(\mathbb{N}^\mathbb{N} \) is my preferred notation for the set of functions from \(\mathbb{N}\) to itself - that is, sequences of natural numbers

This is a great thing to think about. The questions as stated don't make sense, for two reasons. Both these problems can be fixed:

A. It is not a graph that gives a sequence of numbers, but a

pointed graph: a graph with a chosen node. This lets us count the number of paths of length \(n\) starting and ending at that node, and get a sequence of natural numbers. There is a category \(\textbf{Graph}_\ast\) of pointed graphs, where a morphism is a map of graphs that sends the chosen node of one to the chosen node of the other.B. \(\textbf{Graph}_\ast \) is a

categorywhile \(\mathbb{N}^\mathbb{N} \) is a mereset. Thus, it's not clear what \(J\) should be: a functor (a map between categories) or a function (a map between sets). We can cure this problem in two equivalent ways:Turn the category \(\textbf{Graph}_\ast \) into a set, namely the set of isomorphism classes of pointed graphs.

Turn the set \(\mathbb{N}^\mathbb{N} \) into a category with only identity morphisms.

Since they're equivalent we can use the first, less stressful approach.

There is indeed a well-defined function \(J\) from the set of isomorphism classes of pointed graphs to the set of sequences of natural numbers, where we count the number of paths of length \(n\) from the chosen node to itself.

This function \(J\) is neither one-to-one nor onto. The interesting question are thus:

Which sequences of natural numbers arise by counting the number of paths of length \(n\) from the chosen node in a pointed graph to itself?

When do two pointed graphs give the same sequence?

I know a nice answer to the first, which I'll explain if nobody can guess it, but I'm pretty clueless about the second.

I think Matthew Doty at least can guess the answer to the first question here, since he rapidly translated the Pell sequence into a pointed graph that gives it.

I think the easiest way to tackle the first question is to figure out a nice general formula for the number of paths of length \(n\) from any node in a graph to any other node.

`Fredrick wrote approximately: > \[ J : \textbf{Graph} \rightarrow \mathbb{N}^\mathbb{N} \] > Does \\(J\\) have an inverse? Does \\(J\\) have a right adjoint? (Here \\(\mathbb{N}^\mathbb{N} \\) is my preferred notation for the set of functions from \\(\mathbb{N}\\) to itself - that is, sequences of natural numbers This is a great thing to think about. The questions as stated don't make sense, for two reasons. Both these problems can be fixed: A. It is not a graph that gives a sequence of numbers, but a **pointed graph**: a graph with a chosen node. This lets us count the number of paths of length \\(n\\) starting and ending at that node, and get a sequence of natural numbers. There is a category \\(\textbf{Graph}_\ast\\) of pointed graphs, where a morphism is a map of graphs that sends the chosen node of one to the chosen node of the other. B. \\(\textbf{Graph}\_\ast \\) is a _category_ while \\(\mathbb{N}^\mathbb{N} \\) is a mere _set_. Thus, it's not clear what \\(J\\) should be: a functor (a map between categories) or a function (a map between sets). We can cure this problem in two equivalent ways: 1. Turn the category \\(\textbf{Graph}_\ast \\) into a set, namely the set of isomorphism classes of pointed graphs. 2. Turn the set \\(\mathbb{N}^\mathbb{N} \\) into a category with only identity morphisms. Since they're equivalent we can use the first, less stressful approach. There is indeed a well-defined function \\(J\\) from the set of isomorphism classes of pointed graphs to the set of sequences of natural numbers, where we count the number of paths of length \\(n\\) from the chosen node to itself. This function \\(J\\) is neither one-to-one nor onto. The interesting question are thus: 1. Which sequences of natural numbers arise by counting the number of paths of length \\(n\\) from the chosen node in a pointed graph to itself? 1. When do two pointed graphs give the same sequence? I know a nice answer to the first, which I'll explain if nobody can guess it, but I'm pretty clueless about the second. I think Matthew Doty at least can guess the answer to the first question here, since he rapidly translated the Pell sequence into a pointed graph that gives it. I think the easiest way to tackle the first question is to figure out a nice general formula for the number of paths of length \\(n\\) from any node in a graph to any other node.`

David Lambert wrote:

Yes! I may be confused, but I think generating function you're talking about is associated with a

pointedgraph, as explained in my comment above. Anyway, there's a field called algebraic graph theory that studies things like this.`David Lambert wrote: > Does the generating function associated with a graph tell us anything interesting about the graph? Yes! I may be confused, but I think generating function you're talking about is associated with a _pointed_ graph, as explained in my comment above. Anyway, there's a field called [algebraic graph theory](https://en.wikipedia.org/wiki/Algebraic_graph_theory) that studies things like this.`

John asked:

I'll consider a simpler graph: one that has distinct loops of lengths \(a_1, ... a_k\). Then the number of paths with length \(n\) that start and end at the chosen node is the number of ways to pick nonnegative integer coefficients \(b_i\) such that:

\(n=\sum_i^k a_i \cdot b_i\)

Edit: that's not good enough! See my discussion with John below.I have no idea how to simplify that expression, but I claim it to be the answer to John's first question.

Regarding the second question, if two graphs give the same sequence then they contain the same kinds of loops and the same number of them. I have no proof for this at the moment, just a strong hunch.

`John asked: > Which sequences of natural numbers arise by counting the number of paths of length n from the chosen node in a pointed graph to itself? I'll consider a simpler graph: one that has distinct loops of lengths \\(a_1, ... a_k\\). Then the number of paths with length \\(n\\) that start and end at the chosen node is the number of ways to pick nonnegative integer coefficients \\(b_i\\) such that: \\(n=\sum_i^k a_i \cdot b_i\\) _Edit: that's not good enough! See my discussion with John below._ I have no idea how to simplify that expression, but I claim it to be the answer to John's first question. Regarding the second question, if two graphs give the same sequence then they contain the same kinds of loops and the same number of them. I have no proof for this at the moment, just a strong hunch.`

Use

`\cdot`

, which is a centered dot, instead of`\mdot`

. Example: \[ x \cdot y. \]or if you want a big round dot, use

`\bullet`

. Example: \[ x \bullet y. \]`Use `\cdot`, which is a centered dot, instead of `\mdot`. Example: \\[ x \cdot y. \\] or if you want a big round dot, use `\bullet`. Example: \\[ x \bullet y. \\]`

Thanks, Keith, I figured that one out while you were typing. But I forgot how to create a standalone formula... No need to answer that one, I'll simply have a look at your comment's source as soon as I'm back in front of my laptop. Thanks again, to you, and in advance :^)

`Thanks, Keith, I figured that one out while you were typing. But I forgot how to create a standalone formula... No need to answer that one, I'll simply have a look at your comment's source as soon as I'm back in front of my laptop. Thanks again, to you, and in advance :^)`

Robert wrote:

There are two issues here:

how you are reducing the case of a general graph to the simpler sort of graph you're discussing, and

how your formula works for those simpler graphs.

I'll focus on point 2. Could you illustrate how your formula works if I start with the "Fibonacci graph"?

It seems to be of your simpler sort, with a loop of length 1 and a loop of length 2.

`Robert wrote: > Which sequences of natural numbers arise by counting the number of paths of length n from the chosen node in a pointed graph to itself? > I'll consider a simpler graph: one that has distinct loops of lengths \\(a_1, ... a_k\\). Then the number of paths with length \\(n\\) that start and end at the chosen node is the number of ways to pick nonnegative integer coefficients \\(b_i\\) such that: > \[ n=\sum_i^k a_i \cdot b_i \] > I have no idea how to simplify that expression, but I claim it to be the answer to John's first question. There are two issues here: 1. how you are reducing the case of a general graph to the simpler sort of graph you're discussing, and 2. how your formula works for those simpler graphs. I'll focus on point 2. Could you illustrate how your formula works if I start with the "Fibonacci graph"? <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/graph_f.png"></center> It seems to be of your simpler sort, with a loop of length 1 and a loop of length 2.`

Robert wrote:

No, not as far as I've ever heard. I like it, though.

Puzzle.There's another famous sequence, theLucas numbers, also defined by a linear recurrence:$$ L_0 = 2,\quad L_1 = 1,\quad L_{n+2} = L_{n+1} + L_n $$ Can we get this sequence as the number of loops of length \(n\) starting and ending at some chosen node in a graph? If not, can we do it for a shifted version of this sequence? Or can we get it as the number of paths of length \(n\) starting at some chosen node and ending at some

otherchosen node of a graph?A study of 657 sunflowers show that most of them have Fibonacci numbers of spirals, while some have Lucas numbers.

`Robert wrote: > It seems we should call these categories Fibonacci and Pell. Is that something people do? No, not as far as I've ever heard. I like it, though. **Puzzle.** There's another famous sequence, the **[Lucas numbers](https://en.wikipedia.org/wiki/Lucas_number)**, also defined by a linear recurrence: \[ L_0 = 2,\quad L_1 = 1,\quad L_{n+2} = L_{n+1} + L_n \] Can we get this sequence as the number of loops of length \\(n\\) starting and ending at some chosen node in a graph? If not, can we do it for a shifted version of this sequence? Or can we get it as the number of paths of length \\(n\\) starting at some chosen node and ending at some _other_ chosen node of a graph? [A study of 657 sunflowers](http://rsos.royalsocietypublishing.org/content/3/5/160091) show that most of them have Fibonacci numbers of spirals, while some have Lucas numbers. <center><img src = "https://upload.wikimedia.org/wikipedia/en/thumb/e/e7/Lucas_number_spiral.svg/640px-Lucas_number_spiral.svg.png"></center>`

Hey yes, my formula is wrong! Thanks! Let me translate your labeling of the Fibonacci graph to a loop signature.

\(f \rightarrow a_1=1\)

\(h°g \rightarrow a_2=2\)

I had proposed to count paths like this example with length 4:

\(2\cdot a_1+1\cdot a_2\)

While in fact these paths are all different:

\(a_1a_1a_2\)

\(a_1a_2a_1\)

\(a_2a_1a_1\)

I still like naming loops. The formula I gave simply isn't

enough! For each such sum I'd also have to count the permutations which look different. Counting them shouldn't be too hard, but armed with such an ability there might be a better way to count them alltogether. Or even general paths with arbitrary start and end...If it weren't a bit late for me, I might find out how to count these permutations right away, and then perhaps nevertheless try to correct my formula that way.

`Hey yes, my formula is wrong! Thanks! Let me translate your labeling of the Fibonacci graph to a loop signature. \\(f \rightarrow a_1=1\\) \\(h°g \rightarrow a_2=2\\) I had proposed to count paths like this example with length 4: \\(2\cdot a_1+1\cdot a_2\\) While in fact these paths are all different: \\(a_1a_1a_2\\) \\(a_1a_2a_1\\) \\(a_2a_1a_1\\) I still like naming loops. The formula I gave simply isn't _enough_! For each such sum I'd also have to count the permutations which look different. Counting them shouldn't be too hard, but armed with such an ability there might be a better way to count them alltogether. Or even general paths with arbitrary start and end... If it weren't a bit late for me, I might find out how to count these permutations right away, and then perhaps nevertheless try to correct my formula that way.`

So, going in a different direction, we get a weird directed two category if we index the morphisms of the free category by length.

(Not just an enriched category of some sort because id and composition only hold while moving to a later index)

Or you can look at the graph as a binary valued matrix then take powers of it as a matrix of natural numbers, then the sequences of particular diagonals are the sequences generated by the graph pointed at that node.

So would looking at traces and determinants help with building a pointed graph that generates a particular sequence?

`So, going in a different direction, we get a weird directed two category if we index the morphisms of the free category by length. (Not just an enriched category of some sort because id and composition only hold while moving to a later index) Or you can look at the graph as a binary valued matrix then take powers of it as a matrix of natural numbers, then the sequences of particular diagonals are the sequences generated by the graph pointed at that node. So would looking at traces and determinants help with building a pointed graph that generates a particular sequence?`

Robert - good, you see the problem.

You might try counting the paths of various lengths in this graph:

and compare it to taking powers of this matrix:

$$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) .$$

`Robert - good, you see the problem. You might try counting the paths of various lengths in this graph: <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/graph_f.png"></center> and compare it to taking powers of this matrix: \[ \left( \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right) .\]`

Who would have guessed: glancing at a problem and putting down one's first hunch unchecked tends to give wrong answers :-D

Your suggestion indeed looks highly elegant: write down the adjacency matrix, take it to the n'th power, and then, as Christopher Upshaw said, simply read off... something... from the main diagonal. I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix.

I'll have to take a closer look, especially to find out why that works! That is, once I get my hands free, which might well happen before the Americas wake up again.

`Who would have guessed: glancing at a problem and putting down one's first hunch unchecked tends to give wrong answers :-D Your suggestion indeed looks highly elegant: write down the adjacency matrix, take it to the n'th power, and then, as Christopher Upshaw said, simply read off... something... from the main diagonal. I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix. I'll have to take a closer look, especially to find out why that works! That is, once I get my hands free, which might well happen before the Americas wake up again.`

Robert wrote:

The trace would give you the number of paths of length \(n\) either of type \(x \to x\) or of type \(y \to y\). For instance, the square of that matrix gives:

$$ \left( \begin{array}{cc} 2 & 1 \\ 1 & 1 \end{array} \right) .$$ The trace of this matrix is 3, but we know there are only two paths of length 2 from x to itself. Do you see what's happening? (It has to do with the fact that the original matrix is, as you observed, the

adjacency matrixfor this graph.)Also, notice that the adjacency matrix doesn't have to be binary-valued here. If we have two self-loops on a vertex, we'd need to put a 2 down for that vertex.

(I love the matrix approach to this problem! It's a wonderful example of one of Pólya's principles: sometimes, in order to prove a thing, you should prove a stronger thing instead.)

`[Robert wrote](https://forum.azimuthproject.org/discussion/comment/18891/#Comment_18891): > I guess we'd be looking for the sum of the numbers on the resulting main diagonal: the trace of the matrix. The trace would give you the number of paths of length \\(n\\) either of type \\(x \to x\\) or of type \\(y \to y\\). For instance, the square of that matrix gives: \[ \left( \begin{array}{cc} 2 & 1 \\\ 1 & 1 \end{array} \right) .\] The trace of this matrix is 3, but we know there are only two paths of length 2 from x to itself. Do you see what's happening? (It has to do with the fact that the original matrix is, as you observed, the _adjacency matrix_ for this graph.) Also, notice that the adjacency matrix doesn't have to be binary-valued here. If we have two self-loops on a vertex, we'd need to put a 2 down for that vertex. (I love the matrix approach to this problem! It's a wonderful example of one of [Pólya's principles](https://en.wikipedia.org/wiki/How_to_Solve_It): sometimes, in order to prove a thing, you should prove a stronger thing instead.)`

Thanks @Matthew Dotty for the comment #22

`Thanks @Matthew Dotty for the comment #22`

Yeah, I'm trying to remember what I know about raising a matrix to a power. Oh, the natural number powers of a matrix of natural numbers are again natural numbered matrices. So we can then reinterpret them as a graph. Which means given a pointed graph that generates a sequence, we can construct a graph that generates every nth value of the series. Which is pretty non obvious I think!

Well the determinant of the product is the product of the determinants, so \(1 \centerdot 0 - 1 \centerdot 1 = -1\) means that for the Fibonacci graph, the determinant of the power is going to alternate from negative one and one.

`Yeah, I'm trying to remember what I know about raising a matrix to a power. Oh, the natural number powers of a matrix of natural numbers are again natural numbered matrices. So we can then reinterpret them as a graph. Which means given a pointed graph that generates a sequence, we can construct a graph that generates every nth value of the series. Which is pretty non obvious I think! Well the determinant of the product is the product of the determinants, so \\(1 \centerdot 0 - 1 \centerdot 1 = -1\\) means that for the Fibonacci graph, the determinant of the power is going to alternate from negative one and one.`

Christopher wrote:

In some sense, a free category is the union over the sequence of all such graphs! (We don't even have to worry about pointed graphs in particular: powers of the adjacency matrix tell us about the number of paths between every pairs of vertices.)

`[Christopher wrote](https://forum.azimuthproject.org/discussion/comment/18902/#Comment_18902): > Which means given a pointed graph that generates a sequence, we can construct a graph that generates every nth value of the series. Which is pretty non obvious I think! In some sense, a free category is the union over the sequence of all such graphs! (We don't even have to worry about pointed graphs in particular: powers of the adjacency matrix tell us about the number of paths between every pairs of vertices.)`

Christopher wrote

I made some Project Euler-esque puzzles after thinking about

Puzzle 105andPuzzle 104in Fun With RecurrencesI'll try to post some answers to those tonight and show how do to matrix exponentiation in the process.

`[Christopher wrote](https://forum.azimuthproject.org/discussion/comment/18902/#Comment_18902) > Yeah, I'm trying to remember what I know about raising a matrix to a power. I made some Project Euler-esque puzzles after thinking about **Puzzle 105** and **Puzzle 104** in [Fun With Recurrences](https://forum.azimuthproject.org/discussion/2207/fun-with-recurrences) I'll try to post some answers to those tonight and show how do to matrix exponentiation in the process.`

Robert wrote:

Who would have guessed! It's fine to make guesses here; I'm more interested in getting people thinking - and thinking out loud - than having people be infallible.

I believe your original formula was correct except that you need to count

orderedsums of the loop lengths \(a_i\), not ordinary sums. For example, the Fibonacci graph has loops of length 1 and 2 based at the point \(x\):and the number of loops of length \(n\) based at this point is the number of ways of writing \(n\) as an

orderedsums of 1's and 2's. For example$$ 4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 2 + 2 $$ so there are four loops of length 5... and the fourth Fibonacci number is 5.

`Robert wrote: > Who would have guessed: glancing at a problem and putting down one's first hunch unchecked tends to give wrong answers :-D Who would have guessed! It's fine to make guesses here; I'm more interested in getting people thinking - and thinking out loud - than having people be infallible. I believe your original formula was correct except that you need to count _ordered_ sums of the loop lengths \\(a_i\\), not ordinary sums. For example, the Fibonacci graph has loops of length 1 and 2 based at the point \\(x\\): <center><img src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/graph_f.png"></center> and the number of loops of length \\(n\\) based at this point is the number of ways of writing \\(n\\) as an _ordered_ sums of 1's and 2's. For example \[ 4 = 1 + 1 + 1 + 1 = 2 + 1 + 1 = 1 + 2 + 1 = 1 + 1 + 2 = 2 + 2 \] so there are four loops of length 5... and the fourth Fibonacci number is 5.`

John replied:

Thanks! Guessing is fun, especially in groups! But shush now, or other people might think I'm worse than lazy.

Let's work a bit, as a distraction from work. Matrix multiplication works like this:

\[ c_{ij} = \sum_k^n a_{ik} \cdot b_{kj} \]

Let's say a is our adjacency matrix, and b the n-1th power of a. Every element \(a_{ij}\) tells us wether there's an arrow \(i \rightarrow j\). You can skip thinking recursively for now and just assume that \(b=a\). Then \(c_{ij}\) is the sum of all those \(b_{kj}\) for which a states that there's an arrow \(i \rightarrow k\). Nonrecursively, these are just the neighbours' arrows!

So these square matrices are just perfect for recording the inflow any element gets!

I still have to check how my initial formula relates to all this. Until then, maybe some of the folks reading here might enjoy this 5 page short distraction as much as I did:

"On the computation of the nth power of a matrix"byNikolaos Halidias(2017): https://arxiv.org/abs/1705.04994`John replied: > Who would have guessed! Thanks! Guessing is fun, especially in groups! But shush now, or other people might think I'm worse than lazy. Let's work a bit, as a distraction from work. Matrix multiplication works like this: \\[ c_{ij} = \sum_k^n a_{ik} \cdot b_{kj} \\] Let's say a is our adjacency matrix, and b the n-1th power of a. Every element \\(a_{ij}\\) tells us wether there's an arrow \\(i \rightarrow j\\). You can skip thinking recursively for now and just assume that \\(b=a\\). Then \\(c_{ij}\\) is the sum of all those \\(b_{kj}\\) for which a states that there's an arrow \\(i \rightarrow k\\). Nonrecursively, these are just the neighbours' arrows! So these square matrices are just perfect for recording the inflow any element gets! I still have to check how my initial formula relates to all this. Until then, maybe some of the folks reading here might enjoy this 5 page short distraction as much as I did: _"On the computation of the nth power of a matrix"_ by **Nikolaos Halidias** (2017): https://arxiv.org/abs/1705.04994`

Wait a minute...

If these arrows are weight by probabilities, then the above construction produces a Markov chain.

So the number of arrow or morphisms of a pointed graph is like a Markov chain with weight 1 for each arrow.

`Wait a minute... If these arrows are weight by probabilities, then the above construction produces a [Markov chain](https://en.wikipedia.org/wiki/Markov_chain). So the number of arrow or morphisms of a pointed graph is like a Markov chain with weight 1 for each arrow.`

That's exactly right, Keith, if you can stomach the words "Markov chain"!

`That's exactly right, Keith, if you can stomach the words "Markov chain"!`

Right, and if we want to be able to go backwards on a sequence, then we want to allow

negativenumbers of arrows. So the "graph" that will take us to the left on the Fibonacci sequence is \[ \left( \begin{array}{cc} 0 & 1 \\ 1 & -1 \end{array} \right) .\] I don't have a good interpretation of what that means as a path count, maybe just the standard difference between path counts? I don't think that works...@KeithEPerterson a Markov chain is just a normalized path count. (Well if you have rational probabilities. :) )

`Right, and if we want to be able to go backwards on a sequence, then we want to allow _negative_ numbers of arrows. So the "graph" that will take us to the left on the Fibonacci sequence is \\[ \left( \begin{array}{cc} 0 & 1 \\\ 1 & -1 \end{array} \right) .\\] I don't have a good interpretation of what that means as a path count, maybe just the standard difference between path counts? I don't think that works... @KeithEPerterson a Markov chain is just a normalized path count. (Well if you have rational probabilities. :) )`

Christopher:

It becomes obvious if you take a small example, like the matrix

$$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) $$ coming from this graph

and square, cube, etc. the matrix while also counting paths of length 2, 3, etc. by hand. You'll see that the formula for matrix multiplication

$$ (AB)_{ij} =\sum_k A_{ik} B_{kj} $$ is exactly what you need for path counting, because the right-hand side says "to count the number of ways to go from node \(j\) to node \(i\), sum over all ways to go first from \(j\) to some other node \(k\) and then from \(k\) to \(i\)".

There are few things so good for understanding math as actually multiplying matrices by hand. After working through this example for half an hour, it will seem so obvious that you'll realize this is exactly one of the things matrix multiplication was made for!

Heisenberg reinvented matrix multiplication when developing quantum mechanics, for more or less the same reason. Back then, in the 1920's, even good physicists didn't all know about matrices! So Heisenberg reinvented matrix multiplication. Then he told his thesis advisor, Max Born, who said something like "that's just matrix multiplication - read this book".

And thus matrix mechanics was born. Only much later did it become clear what was really going on: an interesting relation between quantum mechanics and category theory!

`Christopher: > Yeah, I'm trying to remember what I know about raising a matrix to a power. Oh, the natural number powers of a matrix of natural numbers are again natural numbered matrices. So we can then reinterpret them as a graph. Which means given a pointed graph that generates a sequence, we can construct a graph that generates every nth value of the series. Which is pretty non obvious I think! It becomes obvious if you take a small example, like the matrix \[ \left( \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right) \] coming from this graph <center><img width = "200" src = "http://math.ucr.edu/home/baez/mathematical/7_sketches/graph_f.png"></center> and square, cube, etc. the matrix while also counting paths of length 2, 3, etc. by hand. You'll see that the formula for matrix multiplication \[ (AB)\_{ij} =\sum_k A\_{ik} B\_{kj} \] is exactly what you need for path counting, because the right-hand side says "to count the number of ways to go from node \\(j\\) to node \\(i\\), sum over all ways to go first from \\(j\\) to some other node \\(k\\) and then from \\(k\\) to \\(i\\)". There are few things so good for understanding math as actually multiplying matrices by hand. <img src = "http://math.ucr.edu/home/baez/emoticons/tongue2.gif"> After working through this example for half an hour, it will seem so obvious that you'll realize this is exactly one of the things matrix multiplication was made for! Heisenberg reinvented matrix multiplication when developing quantum mechanics, for more or less the same reason. Back then, in the 1920's, even good physicists didn't all know about matrices! So Heisenberg reinvented matrix multiplication. Then he told his thesis advisor, Max Born, who said something like "that's just matrix multiplication - read this book". And thus [matrix mechanics](https://www.google.com/search?q=matrix+mechanics&ie=utf-8&oe=utf-8&client=firefox-b-1) was born. Only much later did it become clear what was really going on: an interesting relation between quantum mechanics and category theory!`

To make the adjacency matrix notion painfully obvious.

$$ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array} \right) $$ $$ \left( \begin{array}{c | cc} s \rightarrow t & x & y \\ \hline x & \lbrace f \rbrace & \lbrace g \rbrace \\ y & \lbrace h \rbrace & \emptyset \end{array} \right) $$

`To make the [adjacency matrix](https://forum.azimuthproject.org/discussion/comment/18927/#Comment_18927) notion painfully obvious. \[ \left( \begin{array}{cc} 1 & 1 \\\\ 1 & 0 \end{array} \right) \] \[ \left( \begin{array}{c | cc} s \rightarrow t & x & y \\\\ \hline x & \lbrace f \rbrace & \lbrace g \rbrace \\\\ y & \lbrace h \rbrace & \emptyset \end{array} \right) \]`