1
$\begingroup$

I was given problem 6.7 out of the book "Networks: An Introduction" as a question. The problem is defined as follows:

Consider the set of all paths from node $s$ to node $t$ on an undirected network with adjacency matrix A. Let us give each path a weight equal to $\alpha^r$, where $r$ is the length of the path.

a) Show that the sum of the weights of all the paths from $s$ to $t$ is given by $Z_{st}$ which is the $st$ element of the matrix $Z = (I - \alpha A)^ {-1}$, where $I$ is the identity matrix

b) What condition must $\alpha$ satisfy for the sum to converge?

Where do I even start on this problem? Since the graph is undirected, I know that A must be a symmetric matrix. Other than that I don't quite know what more information there is to go on.

$\endgroup$
4
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – Raphael
    Oct 23, 2016 at 22:00
  • $\begingroup$ If you were given this problem, all necessary techniques were probably covered earlier in lecture or other exercises. Go through your notes and see what applies! $\endgroup$
    – Raphael
    Oct 23, 2016 at 22:01
  • 2
    $\begingroup$ What did you try? Where did you get stuck? "Where do I even start?" isn't a question. You start by trying things. $\endgroup$ Oct 24, 2016 at 8:00
  • $\begingroup$ Tried to improve the title. I searched all of my notes before asking this question, yet nothing presented applies to this proof! @DavidRicherby: If you got nothing to say to get closer to a solution, why even bother answering? I tried to figure out where and how I could get from $\alpha^r$ to $\alpha$. Something never presented was applying Taylor expansion on matrices. $\endgroup$
    – vonludi
    Oct 26, 2016 at 18:01

1 Answer 1

3
$\begingroup$

A few hints:

  • Find out what the entries of $A^2$ mean. How about $A^k$? (Start by a very small adjacency matrix, multiply it with itself and try to think what each entry means).
  • Lookup and understand the Taylor expansion of $f(x) = 1/(1-x)$.
  • Realize that the sum of weights of all paths from $s$ to $t$ is the sum of weights of paths of length 0, 1, 2, ...
$\endgroup$
6
  • $\begingroup$ If I understand your hints correctly, $A_{i,j}^k$ describes the number of paths of length $k$ between nodes $i$ and $j$. The Taylor expansion seems to be exactly what we want ($1 + x + x^2 + x^3 + ... $). So I assume $\alpha$ should be in $ -1 < x < 1$? I don't know how to show point a. Could you give me some more hints for that? Thank you. $\endgroup$
    – vonludi
    Oct 23, 2016 at 18:15
  • $\begingroup$ I'm not quite sure where exactly $A^k$ comes into play, though, since $\alpha A$ should be a scalar multiplication, shouldn't it? $\endgroup$
    – vonludi
    Oct 23, 2016 at 18:26
  • $\begingroup$ @vonludi Correct the entries of the matrix are the number of paths of length k. So next hint: what is $(\alpha A)^k = \alpha^k A^k$? $\endgroup$
    – aelguindy
    Oct 23, 2016 at 18:53
  • $\begingroup$ Yes $\alpha A$ is the scalar multiplication. $\endgroup$
    – aelguindy
    Oct 23, 2016 at 18:54
  • 1
    $\begingroup$ Yes, it is the paths of lengths k multiplied by $\alpha^k$, which is what is required. The solution from here should be very straightforward.. Sum over all paths lengths and you get the total cost. Use the sum and the fact that the taylor expansion of $(I - \alpha A)^{-1}$ to get a proof for part (a). $\endgroup$
    – aelguindy
    Oct 23, 2016 at 20:16

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.