Results 1 to 3 of 3

Math Help - Walks and Matrices

  1. #1
    Newbie
    Joined
    Sep 2006
    From
    Edmonton, AB
    Posts
    8

    Walks and Matrices

    Let G be a graph with vertices (1,2,...,n) and adjacency matrix A= (a subtext ij)

    1) Find an expression for the number of walks of the form i-k-j.


    I'm puzzled. I thought I had it figured out as:

    entry in ik + entry in kj -1

    but this did not hold when I looked at graphs with multiple loops. Any thoughts?

    Here is another that I can't even figure out where to begin with.

    2) Show that the number of walks of length 2 from vertex i to vertex j in G is the ijth entry of the matrix A^2.

    I know how to multiply matrices, but I'm not sure how to put it in general terms to help me.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jaidon View Post
    Let G be a graph with vertices (1,2,...,n) and adjacency matrix A= (a subtext ij)

    1) Find an expression for the number of walks of the form i-k-j.
    I wish I can understand you
    What do you mean by i-j-k walk?

    2) Show that the number of walks of length 2 from vertex i to vertex j in G is the ijth entry of the matrix A^2.
    This is difficult to explain and messy.
    But the general theorem is that the number of walks of length k between two verticies is the entry in the adjancey matrix A^k.
    Try to think of it like this:
    The a_ij entry in the adjancey matrix is the dot product between the i-th row and j-colomum. Thus, since it consists of only 1's and 0's is the sum of these numbers (after the dot product). The sum is the number of the entries which are common to both (otherwise is zero) this is your walk from these two verticies.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2006
    From
    Edmonton, AB
    Posts
    8
    as far as i-k-j walk goes this is how the question is written. i assume it means a walk from i to k then to j. not too sure how this fits in with the definition of this particular matrix
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. 'Random walks on boundary groups'
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: June 17th 2010, 01:56 PM
  2. Random walks and the reflection principle.. HELP!
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: May 19th 2010, 03:09 PM
  3. A man walks then runs...
    Posted in the Algebra Forum
    Replies: 2
    Last Post: June 20th 2009, 05:17 AM
  4. Gambler's Ruin - Random Walks
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 2nd 2009, 12:59 PM
  5. Markov Processes and Random Walks
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: October 6th 2008, 10:39 AM

Search Tags


/mathhelpforum @mathhelpforum