12
$\begingroup$

I came across the formula to find the number of walks of length $n$ between two vertices by raising the adjacency matrix of their graph to the $n$-th power.

I took me quite some time to understand why it actually works. I thought it would be useful to write the proof by induction for this in my own words.


Theorem: Raising an adjacency matrix $A$ of simple graph $G$ to the $n$-th power gives the number of $n$-length walks between two vertices $v_i$, $v_j$ of $G$ in the resulting matrix.

Proof by induction: Let $P(n)$ be the predicate that the theorem is true for $n$. We let $F^{(n)}_{ij}$ be the number of $n$-length walks between vertex $v_i$ and $v_j$. $P(n)$ is then the predicate that $F^{(n)}_{ij} = A^n_{ij}$. We proceed by induction on $n$.

Base case: $P(1)$

Case 1: $F^{(1)}_{ij} = A^{(1)}_{ij} = 1$ if $\{v_i, v_j\} \in E$, so there is is a walk of length $1$ between $v_i$, $v_j$.

Case 2: $F^{(1)}_{ij} = A^{(1)}_{ij} = 0$ if $\{v_i, v_j\} \notin E$, so there can't be any walk of length $1$ between $v_i$ and $v_j$.

In both cases $F^{(1)}_{i j} = A^{(1)}_{ij}$ holds, hence $P(1)$ is true.

Inductive step: $P(n+1)$ For purpose of induction, we assume $P(n)$ is true, that is $F^{(n)}_{i j} = A^{(n)}_{ij}$ holds for $n$.

We can express a walk of length $n+1$ from $v_i$ to $v_j$ as a $n$-length walk from $v_i$ to $v_k$ and a walk of length 1 from $v_k$ to $v_j$.

That means, the number of $n+1$-length walks from $v_i$ to $v_j$ is the sum over all walks from $v_i$ to $v_k$ times the number of ways to walk in one step from $v_k$ to $v_j$. Thus:

$$F^{(n+1)}_{ij} = \sum_{k=1}^{|V|} A_{kj}F^{(n)}_{ik} = \sum_{k=1}^{|V|} A_{kj}A^{(n)}_{ik}$$

Which is the formula for the dot-product, used in matrix multplications.


Any feedback appreciated.

$\endgroup$
3
  • $\begingroup$ Looks ok. Some remarks: 1. You define $P(n)$ as induction statement and as number of walks. I think your should reread your proof and fix this. 2. In the induction base, the case $\{v_i,v_j\}\notin E$ does not imply that there is no walk, but just no walk of length one. $\endgroup$
    – M. Winter
    Commented Sep 18, 2017 at 13:36
  • $\begingroup$ @M.Winter Thanks a lot, I fixed #2, good catch. For #1, you mean $P^{(n)}_{i j} = A^n_{ij}$ should be defined as something else, to not collide with $P(n)$? Like, maybe $F^{(n)}_{i j} = A^n_{ij}$? Please feel free to write an answer, too, if you like. I would be happy to accept it. :-) $\endgroup$
    – BMBM
    Commented Sep 19, 2017 at 1:15
  • $\begingroup$ @Max I think the issue is simply with the phrase "...where $P(n)$ is the number of...". It looks overwhelmingly like a simple typo and you just meant to write $P_{ij}^{(n)}$ here. $\endgroup$
    – Erick Wong
    Commented Sep 19, 2017 at 1:58

1 Answer 1

2
$\begingroup$

Your idea looks correct. Just some remarks on your notation.

You chose $P(n)$ to denote the induction statement. And you (apparently) chose $P_{i,j}^{(n)}$ to denote the number of $v_i$-$v_j$-walks of length $n$. But you use it in the following inconsistent ways: $P(n)$, $P_{i,j}$, $P_{i,j}(n)$. The first one is the most irritating one because it conflicts with your notation for the induction statement. Please keep attention on being consistent with your notation. Mathematics is very exact and to be precise, when you defined $P_{i,j}^{(n)}$, the expression $P_{i,j}(n)$ has still no meaning and is undefined! It will probably be considered a typo, but better be sure and stick to standard or defined notations.

Please note that it is not wrong to use $P$ for both, but keep them distinct by indices or decoration. It however is recommended to use different letters for very different concepts $-$ there are 26 of them and many more symbols when using other alphabets.

$\endgroup$
8
  • $\begingroup$ I updated the notation, do you think it's clearer now? $\endgroup$
    – BMBM
    Commented Sep 20, 2017 at 8:44
  • $\begingroup$ @Max Somehow better and somehow worse. Lets do it point by point: $P_{ij}^{(n)}$ is defined as a number of paths. But then you write "[...] we assume $P_{ij}^{(n)}$ is true.". This makes no sense. How can a number be true? $\endgroup$
    – M. Winter
    Commented Sep 20, 2017 at 10:53
  • $\begingroup$ So what you are saying is that I should leave $P(n)$ and maybe define $P^{(n)}_{i j}$ as for example $F^{(n)}_{i j}$? Then I can use $P(n)$ for induction and have defined $F^{(n)}_{i j}$ as the number of paths. $\endgroup$
    – BMBM
    Commented Sep 21, 2017 at 1:10
  • $\begingroup$ Yes. You can rename it to $F_{ij}^{(n)}$ but you do not have to. Maybe it is better for you because you seem to be confused by using the letter $P$ for both. Just make sure that every notation has a single meaning! $\endgroup$
    – M. Winter
    Commented Sep 21, 2017 at 8:28
  • $\begingroup$ Thanks for your time and your patience, much appreciated. :-) $\endgroup$
    – BMBM
    Commented Sep 22, 2017 at 1:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .