Let’s we have k matrices. For example we have 3 now, where first one is 8×5 ($ 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, (8×5) x (5×6) x (6×8), end up a 8×8 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 fromxtoyin 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

xxymatrix. therefore,xis reachable fromyin the graph iff there is a chain of matrices which from thexxymatrix.

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}$ ?