Quantcast

Got Homework?

Connect with other students for help. It's a free community.

  • across
    MIT Grad Student
    Online now
  • laura*
    Helped 1,000 students
    Online now
  • Hero
    College Math Guru
    Online now

Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

RolyPoly Group Title

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

  • 4 months ago
  • 4 months ago

  • This Question is Open
  1. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

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

    How do you know? :O

    • 4 months ago
  3. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 4 months ago
  4. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 4 months ago
  5. RolyPoly Group Title
    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...

    • 4 months ago
  6. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    What do you mean by MI?

    • 4 months ago
  7. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Ehm, sorry, induction.

    • 4 months ago
  8. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

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

    • 4 months ago
  9. Crixpack Group Title
    Best Response
    You've already chosen the best response.
    Medals 1

    King George is correct. Wahid yes ;)

    • 4 months ago
  10. RolyPoly Group Title
    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!

    • 4 months ago
  11. RolyPoly Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    Would you mind explaining the intuition behind?

    • 4 months ago
  12. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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}\]

    • 4 months ago
  13. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    After that, it's a counting argument.

    • 4 months ago
  14. Crixpack Group Title
    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)

    • 4 months ago
  15. KingGeorge Group Title
    Best Response
    You've already chosen the best response.
    Medals 0

    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.

    • 4 months ago
  16. RolyPoly Group Title
    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\).

    • 4 months ago
  17. experimentX Group Title
    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.

    • 4 months ago
  18. experimentX Group Title
    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} \]

    • 4 months ago
  19. experimentX Group Title
    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.

    • 4 months ago
  20. experimentX Group Title
    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)\]

    • 4 months ago
    • Attachments:

See more questions >>>

Your question is ready. Sign up for free to start getting answers.

spraguer (Moderator)
5 → View Detailed Profile

is replying to Can someone tell me what button the professor is hitting...

23

  • Teamwork 19 Teammate
  • Problem Solving 19 Hero
  • You have blocked this person.
  • ✔ You're a fan Checking fan status...

Thanks for being so helpful in mathematics. If you are getting quality help, make sure you spread the word about OpenStudy.

This is the testimonial you wrote.
You haven't written a testimonial for Owlfred.