Is there an "adjacency matrix" for weighted directed graphs that captures the weights?

Question

I am currently writing up some notes on the max-plus algebra $\mathbb{R}_{\max}$ (for those that have never seen the term "max-plus algebra", it is just $\mathbb{R}$ with addition replaced by $\max$ and multiplication replaced by addition. For some reason, authors whose main interest is control-theoretic applications never seem to use the term "tropical", and I have been reading from such authors). There is a nice result which says the following:

$\textbf{Theorem.}$ Let $G$ be a directed graph on $n$ vertices such that each arc $(i,j)$ in $G$ has a real weight $w(i,j)$. Define the $n \times n$ matrix $A$ by $(A)_{ij} = w(i,j)$ if $(i,j)$ is an arc, and $(A)_{ij} = -\infty$ otherwise. Then for each $k > 0$, the maximum weight of a path of length $k$ from vertex $i$ to vertex $j$ is given by $(A^{\otimes k})_{ij}$ (here, $A^{\otimes k}$ is just the $k$th power of $A$, computed using the $\mathbb{R}_{\max}$ operations).

This result is certainly analagous to the standard result that the $ij$-entry of the $k$th power of the adjacency matrix gives the number of walks of length $k$ from vertex $i$ to vertex $j$. When writing up my notes I found myself claiming that the above theorem provides some evidence that $\mathbb{R}_{\max}$ is in fact a natural setting in which to study weighted digraphs, since there is no natural definition of an ``adjacency matrix'' of a weighted digraph (in the usual setting of $\mathbb{R}^{n \times n}$) that gives useful information about the weights. This seemed like too strong of a claim, especially since I am no expert in networks or combinatorial optimization. This leads to the question:

$\textbf{Question.}$ Is there a standard matrix (in $\mathbb{R}^{n \times n}$) associated with a weighted digraph that is analogous to the adjacency matrix and captures in a useful way the weights of the arcs?

$\textbf{Clarification:}$ By "analogous to the adjacency matrix" I mean a matrix that is defined simply in terms of the graph (vertices, arcs, and weights). I imagine there are all sorts of matrices associated to weighted digraphs so that computers can be used to analyze networks. But I am not interested in, say, a matrix that requires a complicated algorithm to compute its entries.

Answer 1

It looks like in your definition the weight of a path is the sum of the weights of its edges. In many combinatorial applications a natural definition of the weight of a path is the product of the weights of the edges, and there one uses precisely the weighted adjacency matrix $A_{ij} = w(i, j)$ (as an element of the usual $\mathbb{R}$). This is the definition relevant to, for example, the theory of Markov chains, where $w(i, j)$ is a transition probability.

One way to get information about sums of weights is to use $B_{ij} = e^{w(i, j)}$, but what you'll get in the end is a sum of exponentials of weights instead of (direct) information about the maximum or minimum weight. I think one can instead consider $B_{ij}(t) = e^{t w(i, j)}$ and in the "low-temperature" limit as $t \to \infty$ this approaches the tropical result; the largest term will dominate. (I think physicists call these things partition functions.)

Answer 2

$\textbf{Question.}$ Is there a standard matrix (in $\mathbb{R}^{n \times n}$) associated with a weighted digraph that is analogous to the adjacency matrix and captures in a useful way the weights of the arcs?

Yes, and in fact it is essentially the matrix that you define in the theorem that you state. (Typically one sets A[i,j] = $\infty$, since this matrix is used to help find shortest paths in a graph.) This is generally known (at least in the algorithms and data structures community) as the "weighted adjacency matrix."

I don't know what else you would want from a matrix that is supposed to represent a weighted digraph.

Concerning Qiaochu's comment: In fact there is an algorithm for computing the "max-plus matrix product" that uses precisely this trick, and relies on the existence of fast matrix multiplication over rings.

Theorem [Alon, Galil, Margalit]: If $n \times n$ matrix multiplication over the integers can be done in $O(n^{\omega})$ arithmetic operations, then the max-plus matrix product of two $n \times n$ matrices with entries in the range $[-M,M]$ can be computed in about $O(M n^{\omega})$ bit operations.

Given a matrix $A$ with weights, the idea is to make a matrix $B[i,j] = (n+1)^{A(i,j)}$, compute $B \cdot B$ (over the integers) and check the high-order terms to find the largest $k$ such that $A(i,k) + A(k,j)$ is maximized.