9
$\begingroup$

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.

$\endgroup$

2 Answers 2

10
$\begingroup$

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.)

$\endgroup$
5
  • 1
    $\begingroup$ Thanks! I had actually dismissed the product of the weights as being information that was "useless", stupidly ignoring the obvious (and perfectly usual) case where the weights are probabilities. This is what I get for looking at one particular application of digraphs for too long. I attempted to vote up your answer, but alas, I was reputationally (not a word) denied. $\endgroup$
    – user4977
    Mar 28, 2010 at 20:09
  • $\begingroup$ You might write $\beta$ instead of $t$. $\endgroup$ Mar 28, 2010 at 21:20
  • $\begingroup$ Indeed, note that "plus-over-max" is precisely the low-temperature limit of "times-over-plus". Indeed, for $t>0$, define the "temperature-$t$" arithmetic on $\mathbb R \cup \\{-\infty\\}$ by $x \oplus_t y = t^{-1}\log( \exp(tx) + \exp(ty))$ and $x \odot_t y = t^{-1}\log( \exp(tx) + \exp(ty)) = x + y$. Then as $t\to 0$, we have $\lim (x\oplus_t y) = \max(x,y)$. $\endgroup$ Mar 28, 2010 at 23:41
  • $\begingroup$ The bad TeX should read "$\mathbb R \cup \{-\infty\}$". I wish there were either "edit" or "preview" for comments. $\endgroup$ Mar 28, 2010 at 23:41
  • 1
    $\begingroup$ It is unfortunate that the "low-temperature" limit, which is very reasonable terminology, is also called the "tropical" limit (outside Japan, where the convention is reversed). $\endgroup$ Nov 23, 2014 at 1:45
5
$\begingroup$

$\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.

$\endgroup$
1
  • $\begingroup$ Thanks. It is nice to know that the matrix is actually commonly referred to as the weighted adjacency matrix, as that is what I have been calling it. The literature I am familiar with on the topic (which is all in the realm of modeling transportation systems) seems to define the graph from the matrix, never the other way around, so it gives no name to the matrix. To address your comment, I personally don't want anything else from the matrix, but I didn't want to exclude the possibility that there was another natural and useful matrix to represent a weighted digraph. $\endgroup$
    – user4977
    Mar 28, 2010 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.