Maximal weight of path in directed graph (using max-plus algebra) I am working with matrices over the max-plus algebra $(\mathbb{R}_\max,\oplus,\otimes)$. For $A \in \mathbb{R}_\max^{n\times n}$, the graph $\mathcal{G}(A)$ has vertex set $\{1,\dots,n\}$ and edges $(i,j)$ whenever $a_{ij} \neq -\infty$. The weight of edge $(i,j)$ is given by $a_{ij}$.
The maximal weight of a path from $i$ to $j$ of length $k$ in $\mathcal{G}(A)$ is given by $A^{\otimes k}$. Thus the maximal weight of any path from i to j is given by the (i,j)th entry of the matrix
$$
A^+ := \bigoplus_{k=1}^\infty A^{\otimes k}
$$
and we can include 'empty' circuits by starting the max-plus sum from $0$, giving the matrix
$$
A^* := \bigoplus_{k=0}^\infty A^{\otimes k}
$$
My question is, how can I prove that the $^*$ operator is invariant under the (max-plus) addition of the identity matrix $E$? I.e., for any matrix $A$:
$$
A^* = (A\oplus E)^*
$$
It's intuitively obvious since any loops of negative weight are clearly not maximal. But I don't know how to prove the result. Any help appreciated!
 A: We show by induction on $n$ that: $$(A\oplus E)^{\otimes n}=\bigoplus_{k=0}^n A^{\otimes k}$$
For $n=0$ $$(A\oplus E)^{\otimes 0}=E=\bigoplus_{k=0}^0 A^{\otimes k}$$
Assume the property to be true for some $n>0$:
$$(A\oplus E)^{\otimes n+1}=(A\oplus E)\otimes (A\oplus E)^{\otimes n}=(A\oplus E)\otimes\bigoplus_{k=0}^n A^{\otimes k}$$
$$= A\otimes\bigoplus_{k=0}^n A^{\otimes k}\oplus E\otimes\bigoplus_{k=0}^n A^{\otimes k}=\bigoplus_{k=0}^n A^{\otimes k+1}\oplus E\otimes\bigoplus_{k=0}^n A^{\otimes k} $$
$$=\bigoplus_{k=1}^{n+1} A^{\otimes k}\oplus E\otimes A^0 \oplus E\otimes\bigoplus_{k=0}^n A^{\otimes k}= \bigoplus_{k=0}^{n+1} A^{\otimes k}\oplus  E\otimes\bigoplus_{k=0}^n A^{\otimes k} = \bigoplus_{k=0}^{n+1} A^{\otimes k}$$
the last equality comes from the fact that the elements on the diagonal of $E\otimes\bigoplus_{k=0}^n A^{\otimes k}$ are equal to the elements on the diagonal of $\bigoplus_{k=0}^n A^{\otimes k}$ and hence less than or equal to the elements of $ \bigoplus_{k=0}^{n+1} A^{\otimes k}$. All the other elements (not on the diagonal) are equal to $-\infty$ hence less than or equal to the elements of $ \bigoplus_{k=0}^{n+1} A^{\otimes k}$. Thus the max operation can be removed.
Hence we have  $$\bigoplus_{k=0}^n (A\oplus E)^{\otimes k}=\bigoplus_{k=0}^n\bigoplus_{j=0}^k A^{\otimes j}=\bigoplus_{k=0}^n A^{\otimes k}$$
Hence $(A\oplus E)^*=A^*$.
