Some Matrix product $A \odot B$ 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$.
 A: 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$.

A: 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.
