Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Random Matrix

  1. Oct 15, 2007 #1
    Does anybody know how to generate a random matrix with entries 0 and 1 only(binary matrix). Numbers of 1 and 0 are fixed every time matrix is generated.
    Possibly a program in 'C'.

  2. jcsd
  3. Oct 15, 2007 #2
    Numbers are not truly random so perhaps you would like to look at random number generators. You could take your seed and square it, then take out the bits. and the square is your new seed. Or think of another mathematical formula for generating random numbers.

    You can change the seed to be the same for the matricies you wish to have the same 1/0.
  4. Oct 15, 2007 #3
    is the size of the matrix random as well?
  5. Oct 16, 2007 #4
    No, size of matrix is finite.
    Basically the problem is to generate random networks with fixed number of nodes and fixed number of links. Network is being represented by a binary matrix where the entry '1' means that a link exists between the corresponding row and column and '0' means the link does not exist.
    I have to make sure that in generating new network(or matrix) the network should remain connected. It shouldn't break into two or more smaller networks.
    I haven't done graph theory so if somebody can help me with some kind of algorithm, it would be great.

  6. Oct 16, 2007 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Are you generating a incidence matrix (matrix is indexed by nodes and vertices; element ij is one if node i is an endpoint of vertex j) or an adjacency matrix (element ij is one if some vertex connects node i to node j)? A network is a directed graph, so the adjacency matrix is asymmetric.

    Determining whether a random NxN unitary matrix with M ones represents a digraph is the NP-complete problem called the clique problem.
  7. Oct 16, 2007 #6
    I want to generate random adjacency matrices where element ij is 1 if an edge connects node i to node j. Yes it is asymmetric.
  8. Oct 16, 2007 #7


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    ..and you wish to do so with a fixed number of "1"s?

    This might not be the most efficient:

    initialize A=0

    For k ones,
    do this k times
    select randomly i from 1 to n, and j from 1 to n
    if A[i,j]=1, go back and get another pair (without changing k)
    else set A[i,j]=1

    If necessary, discard proposed links to oneself (i.e. reject the pair if i=j).
    Last edited: Oct 16, 2007
  9. Oct 16, 2007 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Nodes in a network can link to themselves. For example, in finite state machine, it is often best to explicitly represent the time steps during which the machine remains in one state as a transition from that state to that same state.

    One problem with this approach is that it most likely will not generate a "network". You could wrap this approach in an outer loop that tests whether the adjacency network represents a single graph. If it doesn't, try again. Determining whether this is the case might take a lot of CPU time (its NP-complete).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook