11. Matrices and Graphs

Existence of a Walk

A walk of length $k$ exists between two nodes $i$ and $j$ if there exists any walks of length $k-1$ from $i$ to $s$ and an edge from $s$ to $j$. Formally:

$$L_{i,j}^{(k)}=\underset{s=1}{\overset{n}{\bigvee }}\left(L_{i,s}^{(k-1)}\wedge L_{s,j}^{(1)}\right).$$

$L^{(1)}=$ adjacency matrix

To check the existence of a path of length less than $k$, add a self loop at every node.

Cheapest Walk

The cost of a walk of length $k$ is the cheapest walk from $i$ to some node $s$ of length $k-1$ and the weight of $s$ to $j$.

$$M_{i,j}^{(k)}=\underset{s=1}{\overset{n}{\min }}\left(M_{i,s}^{(k-1)}+M_{s,j}^{(1)}\right).$$

$M^{(1)}=$ adjacency matrix with 1s replaced by edge weight

Number of Walks

The number of walks from $i$ to $j$ of length $k$ equals the sum over all intermediate nodes $s$ of: walks from $i$ to $s$ of length $k-1$ $\times$ number of edges from $s$ to $j$.

$$N_{i,j}^{(k)}=\sum _{s=1}^n\left(N_{i,s}^{(k-1)}\cdot N_{s,j}^{(1)}\right).$$

$N^{(1)}=$ adjacency matrix

Similarly to existence: add a self-edge of weight 0 to get the number of walk of length at least $k$.

The formula above is identical to matrix multiplication. Therefore: $N^{(k)}=N^{(k-1)}\cdot N^{(1)}$.

Iterative Squaring

$A^4=A^2{A}^2$ $⟹$ we can compute $A^4$ using two multiplications instead of 4. Formally:

$$A^k=\{\begin{array}{ll}(A^{k/2}{)}^2,& \text{if }k\text{ is even}\\ A\cdot (A^{(k-1)/2}{)}^2,& \text{if }k\text{ is odd}\end{array}$$

That reduces the number of matrix multiplications from $\mathcal{O}(n)$ to $\mathcal{O}(\log n)$.