graph theory and linear algebra

76 Views Asked by At

I have a flow graph that gives me the flow matrix below. How do I compute $A\odot A$ and $A \odot A \odot A$? I'm not familiar with this operator and can't really find anything about it. The hint that was given is that "Given $A = [a_{ij}]$ and $B = [b_{kl}]$ of size $n × m$ and $m × l$ respectively, we define $A \odot B= [\max_{1\leq k \leq m} \min(a_{ik},b_{kl})]$."

MY WORK The flow graph I get gives me the flow matrix \begin{array}{ccccc} 0 & 0 & 2 & 0 & 0 \\ 3 & 0 & 8 & 1 & 0 \\ 0 & 0 & 0 & 0 & 7 \\ 2 & 0 & 0 & 0 & 4 \\ 0 & 0 & 10 & 0 & 4 \\ \end{array}

NOV 19 Using the method below I got

$A\odot A= \begin{array}{ccccc} 0 & 0 & 0 & 0 & 2 \\ 1 & 0 & 2 & 0 & 7 \\ 0 & 0 & 7 & 0 & 4 \\ 0 & 0 & 4 & 0 & 4 \\ 0 & 0 & 4 & 0 & 7 \\ \end{array}$

$A\odot A\odot A= \begin{array}{ccccc} 0 & 0 & 2 & 0 & 2 \\ 0 & 0 & 7 & 0 & 4 \\ 0 & 0 & 4 & 0 & 7 \\ 0 & 0 & 4 & 0 & 4 \\ 0 & 0 & 7 & 0 & 4 \\ \end{array}$

Did I make a mistake or are these correct?

1

There are 1 best solutions below

1
On BEST ANSWER

The definition $[A⊙B]_{il}= [\max_{1≤k≤m} \min(a_{ik},b_{kl})]$ is enough for us to compute the desired matrices. For example: for $A \odot A$, we compute $$ [A\odot A]_{23} = \max_{1 \leq k \leq 5} \min(a_{2k}, a_{k3})\\ = \max\{\min(3,2),\min(0,8),\min(8,0),\min(1,0), \min(0,10)\} \\ = \max\{2,0,0,0,0)\} = 2 $$ Which is to say that $$ A \odot A = \pmatrix{?&?&?&?&?\\ ?&?&\color{red}2&?&?\\ ?&?&?&?&?\\ ?&?&?&?&?\\ ?&?&?&?&?\\} $$ The computation of the remaining entries is similar.