Let's continue the story of matrix calculation from the last time. It's a bit cumbersome to write the same adjacency matrix every time, let's call this station connection matrix \(M_{bahn}\) since Bahn means train in German.
\begin{eqnarray*} M_{bahn} &= & \left[ \begin{array}{cccc} 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} \right] \end{eqnarray*}
We can compute neighbor stations by applying \(M_{bahn}\) to the station vector. If we apply the \(M_{bahn}\) twice to the the station vector, you can get the reachable station by two hops. The resulting number means how many possible paths to reach the station. Let's apply the \(M_{bahn}\) twice to the station vector that means one is at the Weinmeisterstr.
\begin{eqnarray*} (M_{bahn})^2 \left[ \begin{array}{c} 1 \\ 0 \\ 0 \\ 0 \\ \end{array} \right] &=& \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \end{eqnarray*}
The resulting element of the vector is how many paths to get the each station by 2 hops. Namely:
\begin{eqnarray*} \left[ \begin{array}{c} 2 \\ 2 \\ 1 \\ 1 \\ \end{array} \right] \begin{array}{cccl} \mbox{Wein.} & \rightarrow & \mbox{Wein.} & \mbox{2 paths} \\ \mbox{Wein.} & \rightarrow & \mbox{Alex.} & \mbox{2 paths} \\ \mbox{Wein.} & \rightarrow & \mbox{Hack.} & \mbox{1 path} \\ \mbox{Wein.} & \rightarrow & \mbox{Jann.} & \mbox{1 path.} \\ \end{array} \end{eqnarray*} For instance, the first entry is 2, this means there are two paths from Weinmeisterstr to Weinmeisterstr by two hops. The first path is
Wein. \(\rightarrow\) Alex. \(\rightarrow\) Wein.that first hop is go to Alexanderplatz, then second hop is go back to the Weinmeisterstr. The second path is
Wein. \(\rightarrow\) Wein. \(\rightarrow\) Wein.that first hop is stay at Weinmeisterstr and second hop is also stay at Weinmeisterstr. Therefore, two different paths to go to Weinmeisterstr with two hops.
I recommend to use octave [6] or matlab to compute this kind of computation. I personally like matlab, but, the license is too expensive for me to do my personal hobby. I will definitely buy if they provide 5 years older version including toolboxes with 100 Euro. I am looking for the matlab Home edition like Mathematica Home edition. However, it seems it is 100 times expensive. So, I usually use octave. This free software is also a great software. The followings show the computation result by octave. (I edited the output result to fit into the column.)
octave:6> Mb = [1 1 0 0; 1 1 1 1;
0 1 1 0; 0 1 0 1];
octave:7> w = [1 0 0 0]';
octave:8> Mb * w
ans =
1
1
0
0
octave:9> Mb * Mb * w
ans =
2
2
1
1
How is the three steps.
octave:10> Mb^3 * w
ans =
4
6
3
3
The first element is 4, this means there are four paths from Weinmeisterstr to Weinmeisterstr with three hops as the following.
\begin{eqnarray*} \begin{array}{ccccccc} \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} \\ \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} & \rightarrow & \mbox{W} \\ \mbox{W} & \rightarrow & \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} \\ \mbox{W} & \rightarrow & \mbox{A} & \rightarrow & \mbox{A} & \rightarrow & \mbox{W} \\ \end{array} \end{eqnarray*}
Where W is Weinmeisterstr, A is Alexanderplatz. There are three allows, this means three movements (or stay).
Here you saw how you used an adjacency matrix to know where you were after n steps movement.
By the way, why does an adjacency matrix tells us the number of paths? (The following explanation assumes you know about the relationship between the column space and the solution space. If you are not familiar with them, you can skip this paragraph.) First of all, we need to transpose the matrix if the graph is a directed graph. Then each column represents connection of the neighbor nodes. The matrix has now number of column dimension column space which is the neighborhood connection space. The solution space is a linear combination of the column space. Thus this is a connection combination. The column space has all the possibility of the neighbor connection. How we can get a linear combination of the column space? The answer is applying the matrix to a vector. This is the brief reason why an adjacency matrix can tell us the reachable nodes. If you know the solution, like you know how many paths you need to visit the stations, you can also know the last step by solving the system. Though this is not so interesting question for me of the station connection graph. Since my usual question is where can I reach to in some steps, not which station I came from.
Now we know how to write a graph in a matrix form and how to use the adjacency matrix. Next article, we are going to look into the property of the matrix by the eigenanalysis.
Comments