Some Matrix product $A \odot B$

Question

I'm confronted with the following problem:

Let $G=(V,E)$ be a directed graph with edge costs $c:E\rightarrow \mathbb{R}$ (Negative cycles do not matter). Let $V=\{v_1,\dots,v_n\}$. For Matrices $A$ and $B$ $\in \mathbb{R}^{n \times n}$, we define a matrix product $\odot$ as follows: $A \odot B = C$ with $$c_{i,j} = \min\left\{a_{i,l}+b_{l,j}|1\leq l \leq n\right\}.$$ We write $A=A^{\odot 1}, A \odot A = A^{\odot 2}$, etc. Let $M \in \mathbb{R}^{n \times n}$ be given by $$m_{i,j} = c(v_i,v_j)$$ with $$c(v_i,v_j)=\infty \text{ if }(v_i,v_j) \not\in E$$ Interpret the values of the matrix $M^{\odot k}$ for $K\in \mathbb{N}$, $k\geq 1$.

Does anyone know this function? For what purposes it can be used?

I wrote a script to study the behaviour of this matrix $M^{\odot k}$ and tested some instances. It seems that:

If there is a negative cycle the entries $m_{i,j}$ tend to $-\infty$ $ \forall i,j$for large $k$.

If there is a no negative cycle the entries $m_{i,j}=\infty$ $ \forall i,j$ for large $k$

If there are negative edges but no negative cycles some $m_{i,j}=\infty$ and some $-\infty<m_{i,j}<\infty$ for large $k$.

Answer 1

Note that $\otimes$ is the usual matrix product, but $+$ is replaced with $\min$ and $\cdot $ is replaced with $+$.

The $(i,j)$ entry of $M^{\odot k}$ gives you the cost of the cheapest length $k$ path from $v_i$ to $v_j$. You can show this by induction.

In the light of this description your observations need some corrections:

• If there is a negative cycle, long enough paths may be found with strongly negative cost by looping a lot along such a negative cycle. However, this is not quite true as in general some lengths may be impossible (in which case we get a cost of $+\infty$). Also, the negative loop may not be useable for all connections
• We only have $m_{ij}=\infty$ for $M^{\odot k}$ if there is no path of length $k$ from $v_i$ to $v_j$. For example with two cycles of coprime length and if $G$ is strongly connected, all entries will be finite for sufficiently large $k$.

Answer 2

You can check by induction that the $(i,j)$th entry of $M^{\odot k}$ is the smallest weight of a path that (1) leads from $i$ to $j$, (2) contains $k$ edges.

As to the behavior of $M^{\odot k}$ as $k$ gets large.

(i) If the initial graph has a negative cycle, then we can move around it as many times as we want, so the entries of $M^{\odot k}$ tend to $-\infty$.

(ii) If all cycles of the graph are positive, then, since any sufficiently long path moves through the same cycle too many times, and the values of $M^{\odot k}$ tend to $+\infty$.

(iii) For the similar reason, if neither (i) nor (ii) hold, the values of $M^{\odot k}$ remain bounded.