Is there an "adjacency matrix" for weighted directed graphs that captures the weights? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T10:56:44Z http://mathoverflow.net/feeds/question/19652 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/19652/is-there-an-adjacency-matrix-for-weighted-directed-graphs-that-captures-the-wei Is there an "adjacency matrix" for weighted directed graphs that captures the weights? TS 2010-03-28T19:25:21Z 2010-03-28T21:27:45Z <p>I am currently writing up some notes on the max-plus algebra <code>$\mathbb{R}_{\max}$</code> (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: </p> <p>$\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 <code>$(A)_{ij} = w(i,j)$</code> if $(i,j)$ is an arc, and <code>$(A)_{ij} = -\infty$</code> otherwise. Then for each $k > 0$, the maximum weight of a path of length $k$ from vertex $i$ to vertex $j$ is given by <code>$(A^{\otimes k})_{ij}$</code> (here, $A^{\otimes k}$ is just the $k$th power of $A$, computed using the $\mathbb{R}_{\max}$ operations).</p> <p>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 <code>$\mathbb{R}_{\max}$</code> 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:</p> <p>$\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?</p> <p>$\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.</p> http://mathoverflow.net/questions/19652/is-there-an-adjacency-matrix-for-weighted-directed-graphs-that-captures-the-wei/19653#19653 Answer by Qiaochu Yuan for Is there an "adjacency matrix" for weighted directed graphs that captures the weights? Qiaochu Yuan 2010-03-28T19:33:04Z 2010-03-28T19:33:04Z <p>It looks like in your definition the weight of a path is the <strong>sum</strong> of the weights of its edges. In many combinatorial applications a natural definition of the weight of a path is the <strong>product</strong> 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.</p> <p>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.)</p> http://mathoverflow.net/questions/19652/is-there-an-adjacency-matrix-for-weighted-directed-graphs-that-captures-the-wei/19668#19668 Answer by Ryan Williams for Is there an "adjacency matrix" for weighted directed graphs that captures the weights? Ryan Williams 2010-03-28T21:27:45Z 2010-03-28T21:27:45Z <blockquote> <p>$\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?</p> </blockquote> <p>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." </p> <p>I don't know what else you would want from a matrix that is supposed to represent a weighted digraph.</p> <p>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. </p> <blockquote> <p><em>Theorem</em> [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.</p> </blockquote> <p>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.</p>