Results 1 to 11 of 11

Math Help - a question about matrices

  1. #1
    Pip
    Pip is offline
    Newbie
    Joined
    Jul 2009
    Posts
    5

    a question about matrices

    I don't know much about math, but from what I read, this seems to be the place to post my question.

    I'm working on a computer program where I have a two-dimensional matrix of variable dimensions. What I need to figure out is, based on the dimensions of the matrix, how many potential neighboring connections can be made. So, for example, (0,0) can connect to (0,1) and (1,0) while (3,4) can connect with (2,4) (4,4) (3,3) (3,5).

    As it stands, I have the program counting these connections manually, but such a method slows down the program, and it would go quicker if there was a formula that could compute the potential neighbors directly. Is there? Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by Pip View Post
    I'm working on a computer program where I have a two-dimensional matrix of variable dimensions. What I need to figure out is, based on the dimensions of the matrix, how many potential neighboring connections can be made. So, for example, (0,0) can connect to (0,1) and (1,0) while (3,4) can connect with (2,4) (4,4) (3,3) (3,5).
    I must not understand the concept of neighboring connections.
    From what you have written it seems that (a,b)~\&~(c,d) are neighboring connections if a=c\text{ or }b=d.
    But can't be it because that means there inifinitely many neighboring connections.
    Please clarify.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Pip
    Pip is offline
    Newbie
    Joined
    Jul 2009
    Posts
    5
    What I mean is that a neighbor is only one cell away (either 'up', 'down', 'left', or 'right'). So, with a coordinate (a,b), the neighbors would be (a+1,b),(a-1,b),(a,b+1),(a,b-1), unless such coordinates would be outside the bounds of the matrix. This is why (0,0) only has two neighbors since it can't go 'up' or 'left'. Does that help clear it up?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by Pip View Post
    What I mean is that a neighbor is only one cell away (either 'up', 'down', 'left', or 'right'). So, with a coordinate (a,b), the neighbors would be (a+1,b),(a-1,b),(a,b+1),(a,b-1), unless such coordinates would be outside the bounds of the matrix. This is why (0,0) only has two neighbors since it can't go 'up' or 'left'. Does that help clear it up?
    Write a function f\left[ {\left( {a,b} \right),\left( {c,d} \right)} \right] = \left| {a - c} \right| + \left| {b - d} \right|.
    If f\left[ {\left( {a,b} \right),\left( {c,d} \right)} \right] = 1 then the two points are neighbors otherwise they are not.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Pip
    Pip is offline
    Newbie
    Joined
    Jul 2009
    Posts
    5
    That function would require a comparison of individual cells, which isn't any more efficient than the manual count that I'm doing. Is it possible to determine the number of unique potential connections based solely on the dimensions of the matrix?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by Pip View Post
    That function would require a comparison of individual cells, which isn't any more efficient than the manual count that I'm doing. Is it possible to determine the number of unique potential connections based solely on the dimensions of the matrix?
    What matrix? Please describe the complete problem.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member alunw's Avatar
    Joined
    May 2009
    Posts
    188
    Surely every entry in the matrix has either 2,3 or 4 neighbours.
    The four corner values have 2 neighbours. All the other entries along the edges of the matrix have 3 nieghbours, and all the other entries have 4 neighbours. So lets count up the number of neighouring pairs which counts each connection twice.
    So if you have an m*n matrix the number of neighbour pairs is 4*m*n-2*(m+n) so the number of possible connections is 2*m*n-(m+n)
    Putting m=n=2 we get 4 which is correct
    putting n=1 we get m-1 which is also correct.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Pip View Post
    That function would require a comparison of individual cells, which isn't any more efficient than the manual count that I'm doing. Is it possible to determine the number of unique potential connections based solely on the dimensions of the matrix?
    Maybe I'm missing something here, but basically if you have an n \times m matrix then there are (n-2)(m-2) coordinates that are not at the edge and so have 4 connections. There are (n-2)+(n-2)+(m-2)+(m-2) = 2n+2m-8 edge coordinates that are not corners, each of which has 3 connections, and there are 4 coordinates (the four corners) that only have 2 connections. Thus we have 4.(n-2)(m-2)+3.(2n+2m-8)+2.(4), which simplifies to 4nm-2n-2m, connections in total.

    Note that (n-2)(m-2)+(2n+2m-8)+4 = nm-2n-2m+4+2n+2m-4=n.m, as we would expect.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Pip
    Pip is offline
    Newbie
    Joined
    Jul 2009
    Posts
    5
    Well, in computer terms, a matrix is a list of lists (or an array of arrays). This would be a 5x5 matrix:

    Code:
    AD000
    0000B
    00000
    00C00
    00000
    (A) has two potential connections with neighbors, to the right and below. (B) has three potential connections (up, down, and left). Finally, (C) has four potential (up, down, right, and left).

    However, I only want to count unique connections. So, for example, even though (A) has two neighboring nodes and (D) has three, the connection between them should only be counted once.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Pip View Post
    However, I only want to count unique connections. So, for example, even though (A) has two neighboring nodes and (D) has three, the connection between them should only be counted once.

    To get rid of connections counted more than once then just divide my formula, above, by two. This is because it counts each connection twice. So, we have that the total number of connections in an n \times m matrix is just 2nm-n-m.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Pip
    Pip is offline
    Newbie
    Joined
    Jul 2009
    Posts
    5
    That does it. I knew there had to be an easier way. Thanks alunw and Swlabr.
    Last edited by Pip; July 30th 2009 at 07:56 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question about matrices
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 29th 2011, 07:54 AM
  2. Matrices question
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: April 20th 2011, 10:58 PM
  3. matrices question
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 6th 2009, 05:33 PM
  4. Question about 3 X 3 matrices
    Posted in the Algebra Forum
    Replies: 3
    Last Post: July 24th 2008, 12:00 PM
  5. Matrices question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 13th 2006, 02:53 AM

Search Tags


/mathhelpforum @mathhelpforum