Number of Walks of Length n
===========================

Using the adjacency matrix of a graph and defined matrix operations, we can provide an algorithm to determine the number of walks of length *n*. To understand this section, it is necessary to be familiar with the operation of matrix multiplication (a well-known operation) and have good intuition about it. You can search for matrix multiplication on the internet to familiarize yourself with it.

.. The Meaning of Matrix Multiplication in Graphs
------------------------------------------------

Consider two graphs with
n
vertices. For example, let's call the blue graph with adjacency matrix
A
and the red graph with adjacency matrix B.
We want to find the number of walks between two vertices
i and j
that have two edges, where the first edge is blue and the second edge is red.
We denote this number by
:math:`C_{i,j}`.
Clearly, to calculate this value we can consider all possible intermediate vertices
(a vertex like k)
then multiply the blue edges from i to k by the red edges from k to j,
and sum the results over all possible k. Mathematically:

.. math:: C_{i,j} = \sum\limits_{k=1}^{n} A_{i,k}B_{k,j}

With careful attention, we can see that matrix
C
is equal to the matrix product of A and B.

.. Matrix Power
   -------------

The power of a matrix is defined similarly to the power of numbers, such that 
:math:`A^n` 
means multiplying A by itself n times. 

According to the theorem we demonstrated above, it can be concluded that **the number of walks of length n from i to j** 
is equal to the (i,j) entry in 
:math:`A^n`. 

To prove this: For each walk of length n-1, place a red edge, and for each edge of the graph, place a blue edge. 
Clearly, every walk of length n corresponds to a walk with one red edge and one blue edge. 
Since 
:math:`A^n = A^{n-1}A`, 
the statement can be proven by induction.

Algorithm and Complexity
------------------------
Therefore, to solve the problem, it is sufficient to compute matrix powers in reasonable time.
Since matrix multiplication is associative (i.e., 
:math:`(AB)C = A(BC)`),
the order of exponentiation does not matter. For even exponents:

.. math:: A^{2k} = (A^k)^2

And for odd exponents:

.. math:: A^{2k+1} = A(A^k)(A^k)

If we compute matrix multiplication using the naive algorithm with 
:math:`O(n^3)` 
complexity, we can recursively compute 
:math:`A^k`
by first calculating 
:math:`A^{\lfloor\frac{k}{2}\rfloor}`
and then using the above relations. The time complexity of this recursive algorithm is:

.. math:: T(k) = T(\frac{k}{2}) + O(n^3) = O(n^3lg(k))

This algorithm is called the **fast exponentiation algorithm**, which can be used whenever we need to repeatedly apply an associative operation to an element. 
For example, the same algorithm can be used for number exponentiation.

Generalization
--------------
The algorithm we examined here is not only used for computing the number of walks of fixed length,
but can also be used to derive other properties of fixed-length walks 
(such as the largest walk or the walk with the minimum edge weight).
For example, suppose we want to find a walk of length k between two vertices 
where the sum of edge weights is maximized.
If we want to solve this problem for a graph with red and blue edges, considering walks that alternate
between one red edge and one blue edge, the solution can be obtained as follows:

.. math:: C_{i,j} = \max\limits_{k=1}^{n} A_{i,k} + B_{k,j}

We can define matrix C as the combination of matrices A and B.
Upon closer inspection, we can see that the combination operation is associative, similar to matrix multiplication.
To prove this, consider a graph with red, blue, and green edges, and derive the maximum-weight 
red-blue-green walk using two different approaches. 
Thus, similar to before, we can define matrix powers and use induction to prove that 
:math:`A^k_{i,j}` 
represents the maximum-weight walk of length k between vertices i and j,
and that there exists an 
:math:`O(n^3lg(k))` 
algorithm to compute this matrix.