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

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

2010-03-28T19:25:21Z

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 by Qiaochu Yuan for Is there an "adjacency matrix" for weighted directed graphs that captures the weights?

2010-03-28T19:33:04Z

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 by Ryan Williams for Is there an "adjacency matrix" for weighted directed graphs that captures the weights?

2010-03-28T21:27:45Z

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