Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

RolyPoly

  • 2 years ago

Given an undirected graph H, let C be the adjacency matrix of H. What is the meaning of entries in \(C^n\)?

  • This Question is Open
  1. KingGeorge
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    If I'm remembering correctly...and I may not be, the \(i,j\)-th entry in \(C^n\) is the number of paths of length \(n\) between the \(i\)-the vertex and the \(j\)-th vertex.

  2. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    How do you know? :O

  3. KingGeorge
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    I think I saw this in a combinatorics class I had last year. I could probably dig out the proof if you want.

  4. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ah! I would love to know the proof, at least to understand why. :)

  5. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    By the way, if the proof involves MI, please, please do not post it...

  6. KingGeorge
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    What do you mean by MI?

  7. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Ehm, sorry, induction.

  8. KingGeorge
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Ah. Well my proof does do it by induction...

  9. Crixpack
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    King George is correct. Wahid yes ;)

  10. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Haha, because the hint of the proof is to prove by induction, and I don't want to copy your work, lol!

  11. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Would you mind explaining the intuition behind?

  12. KingGeorge
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Well, it's actually a pretty short proof. The main part that uses induction, is where you write\[C^n=C^{n-1}C,\]and for a given entry \(C_{ij}\), you can write\[(C^{n-1}C)_{ij}=\sum_{k}(C^{n-1})_{ik}C_{kj}\]

  13. KingGeorge
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    After that, it's a counting argument.

  14. Crixpack
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    This is really rough but you can think of it like this: the i,jth entry of C is 1 only if i and j are connected. Now if we multiply C by itself, to get the i,kth entry (of C^2), we would be multiply the ith row of C by the kth column of C now the ith row would be 1's in places where i is adjacent to some other node and 0's elsewhere and the kth column would be the same, 1's only where k was adjacent to some node, and 0's elsewhere so to get the i,kth entry of C^2, it would only be non-zero if i and k were adjacent to some other node, which would imply that there was a path of length 2 from i to k, and everytime they shared a common node, it would add 1 to the entry, so the entry counts the number of patsh of length 2 and then u go up from there, each power basically extends the path by 1 edge if it is possible, (if it not possible the product would just be 0)

  15. KingGeorge
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    So I guess the underlying idea of the proof, is to count the number of paths of length \(n-1\) from a vertex \(i\) to a vertex \(k\), and then the number of paths of length \(1\) from the vertex \(k\) to the vertex \(j\). And then let \(k\) vary over the whole graph.

  16. RolyPoly
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Not sure if it looks good. Base case: When n=1, \(A^1 = A\), which shows the number of path to vertex j, \(v_j\), to vertex i, \(v_i\), with the path length being 1. So, it is true for n=1. Induction step: Assume it is true for n=m-1. Consider the i,j-th entry of \(A^m\), \[(A^m)_{ij}\]\[ = (AA^{m-1})_{ij} \]\[= A_{i1}(A^{m-1})_{1j} + A_{i2}(A^{m-1})_{2j} +...+A_{in}(A^{m-1})_{nj}\]\[=\sum_{k}A_{ik}(A^{m-1})_{kj}\] Consider \( A_{i1}(A^{m-1})_{1j}\), \( A_{i1}(A^{m-1})_{1j}\) is the number of paths of length 1 from \(v_i\) to \(v_1\) times the number of paths of length m-1 from \(v_1\) to \(v_j\), which is equal to the number of paths of length m from \(v_i\) to \(v_j\) with \(v_1\) being the second vertex visited. This argument follows for each term \( A_{ik}(A^{m-1})_{kj}\), where \( A_{ik}(A^{m-1})_{kj}\) is the number of paths of length m from \(v_i\) to \(v_j\) with \(v_k\) being the second vertex visited. Hence, \(\sum_{k}A_{ik}(A^{m-1})_{kj}\) is the total number of all possible paths with length m from \(v_i\) to \(v_j\).

  17. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    let's take this graph for example http://en.wikipedia.org/wiki/Adjacency_matrix#Examples also let's take that we are at vertex 3 of that graph.

  18. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    from 3, you can go to vertex 2 or vertex 4. now let us represent the vertex 3 by \[ V = \begin{bmatrix} 0\\ 0\\ 1\\ 0\\ 0\\ 0 \end{bmatrix} \] Let the adjacency matrix be A. \[ A V = \begin{bmatrix} 0\\ 1\\ 0\\ 1\\ 0\\ 0 \end{bmatrix} \]

  19. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    it means that ... after one step, either you end up in vertex 2 or vertex 4. therefore it makes sense to construct adjacency matrix this way, and represent state by vectors.

  20. experimentX
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    now let's look at \[ A^2 V = A \begin{bmatrix} 0\\ 1\\ 0\\ 1\\ 0\\ 0 \end{bmatrix} = A \left( \begin{bmatrix} 0\\ 1\\ 0\\ 0\\ 0\\ 0 \end{bmatrix} +\begin{bmatrix} 0\\ 1\\ 0\\ 0\\ 0\\ 0 \end{bmatrix} \right)\]

  21. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy