How can follow this this guide to construct a graph with matrix/reachability

Question

Let's we have k matrices. For example we have 3 now, where first one is 8x5 ($a_1$ x $b_1$), second one is 5 x 6 ($a_2$ x $b_2$) and last one is 6 x 8 ($a_3$ x $b_3$). And our goal is to figure out if possible to multiply within any given matrices and reach a matrix of dimension x and y, when x and y is given ahead of time. In this example, (8x5) x (5x6) x (6x8), end up a 8x8 matrix. The hints is given, but I cannot visualize. Any more help is appreciated. can understand the first step, but have not idea about the second one.

First, we can define nodes in the graph as the values of each $a_i$ and each $b_i$, and put an edge from $a_i$ to $b_i$.

Second, Whenever there is a chain of matrices $M_{i1},...M_{ik}$, we can multiply, then x=$a_{i1}$ has an edge to $b_{i1} =a_{i2}$, and $a_{i2}$ has an edge to $b_{i2}$ =$a_{i3}$, and so on, up until $b_{ik}$ =y. So there could be a path from x to y in this graph.

Third, Inversely, for any path from x to y, the edges form a chain of matrices that we can multiply, which create a x x y matrix. therefore, x is reachable from y in the graph iff there is a chain of matrices which from the x x y matrix.

The first step create something like this ?

>  x--> 
> n8-->n5
> n5-->n6 
> n6-->n8
>   -->y

What is $M_{i1}$, $a_{i1}$ and $b_{i1}$? How does that differ to $a_{1}$ ?

Answer 1

Okay let's say you got $n$ matrices $M_1,M_2,...,M_n$ with dimensions $a_1\times b_1,...,a_n\times b_n$. Now we look at what happens to the dimension when we multiply two matrices $M_i, M_j, i\neq j$: $$(a_i\times b_i)(a_j\times b_j) = a_i \times b_j$$ Notice that you can only multiply the two matrices iff $b_i = a_j = p$: $$(a_i\times p)(p\times b_j) = a_i \times b_j$$ You might spot the pattern here: only the first dimension of the first matrix and the last dimension of the last matrix matter. Thus in order to get a matrix with dimensions $(x\ times y)$ you need a chain of matrices looking like that: $$(x \times e_1)(e_1 \times e_2)(e_2 \times e_3)...(e_n\times y) = (x\times y)$$ where $e_i$ are just arbitrary numbers. This looks similar to a path in a graph, where you are walking from the node labeled with x to a node labeled with y. Notice that for every node in the graph if it represents the first component of the dimension ($a_i$) of a matrix $M_i$ it's connected to the second component of the dimension ($b_i$). Meaning $a_i$ and $b_i$ are connected. Secondly the second component of a dimension $b_i$ of a matrix $M_i$ is connected to all first components $a_j, i\neq j$ that have the same value ($b_i = a_j$). Now if there is a path from $x$ to $y$ in a graph you can build an equation as shown above.

The graph in your particular example looks like this:

8(a1) -> 5(b1)
5(b1) -> 5(a2)
5(a2) -> 6(b2)
6(b2) -> 6(a3)
6(a3) -> 8(b3)

Now $8 = a_1 = x$ is your starting point and $8 = b_3 = y$ is your end point.

EDIT: Construction algorithm:

Input: arrays a,b with n elements
Output: adjacency list A of size 2*n
A = new array of 2*n lists
for i = 1 to n: A[i].add(i+n)
for i = 1 to n:
   for j = 1 to n:
      if b[i] == a[j]:
          A[i+n].add(j)

Notice that $A[i\leq n]$ corresponds to the node for $a_i$ and $A[n+i\leq 2n]$ corresponds to the node for $b_{i}$. Now if you want to check if you can build a matrix with a certain dimension $(x,y)$ you search through $a$ to find $i$ such that $a[i] = x$ and start a dfs or bfs from node $i$ which has the neighbors $A[i]$ and you stop your search when you arrive at node $n+j$ such that $b[j] == y$.