----- > [!proposition] Proposition. ([[number of walks of given length on a network]]) > For $r \in \mathbb{Z}_{\geq_{}0}$, the number of walks of length $r$ from node $j$ to node $i$ on a [[network]] $G$ is $[A^{r}]_{ij},$ > where $A$ denotes the [[adjacency matrix]] of the [[network]]. > \ > As a corollary, the total number of walks from a node to itself of length $r$ is equal to $[A^{r}]_{ii}$; and hence the [[trace of a matrix|trace]] $\text{Tr }A^{r}$ tells us the number of [[parameterized curve|paths]] of length $r$ in a [[network]] that end where they begin. > [!proof]- Proof. ([[number of walks of given length on a network]]) > The element $a_{ij}$ of the [[adjacency matrix]] of $G$ is $1$ if there is a edge connecting $j$ to $i$ and $0$ otherwise. It follows that $a_{ik}a_{kj}=1$ iff there is a length-2 walk from $j\to k \to i$. To find the number of length-2 walks from $j \to i$ via *any* node, we sum over the possible $k$: $\sum_{k=1}^{n}a_{ik}a_{kj}=A_{i,:}A_{:,j}=[A^{2}]_{ij}$. The induction process is clear: there are $[A^{r}]_{ij}$ walks from $i$ to $j$ of length $r$. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```