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

Identify every 1 submatrices

  1. Apr 6, 2014 #1
    In the following 0/1 matrix I'm trying to identify every largest submatrices formed by 1's as shown in the picture.
    Submatrices can have just one row only if they have more than 3 columns.
    Submatrices can have just one column only if they have more than 3 rows.
    Submatrices should have less than maxcol columns and maxrow rows and more than mincol and minrow. In the picture mincol=minrow=2. maxrow=maxcolumn=6.
    I've been searching for this problem, looks like an already solved problem but couldn't find it elsewhere.
     

    Attached Files:

  2. jcsd
  3. Apr 6, 2014 #2

    Mark44

    Staff: Mentor

    From your picture, a submatrix should have at least minrow rows and at least mincol columns. This is different from what you said, which would imply that a two-dimensional submatrix would have to be 3 X 3 or larger.

    Also, it should be possible for a submatrix to have at most minrow rows and at most mincol columns for a matrix all of whose entries are 1's.
    Presumably this is a problem that you want to automate; otherwise you could visually inspect the matrix and pick out the submatrices.

    Finding the one-dimensional submatrices shouldn't be too hard, but finding the two-dimensional submatrices will be harder, I believe. For the the horizontal 1D submatrices, for each row, scan across it until you reach a 1. From this cell, continue scanning for 1's. If you encounter three or more in that row, you have a submatrix. You'll need to remember where the submatrix started, and how many 1 cells there were in it.

    For the vertical 1D submatrices, for each column do essentially the same as described above, but scan downward. Again, if you hit a submatrix, you need to keep track of its starting cell and how many cells are in it.

    Finding the 2D submatrices is harder. I have several ideas, but none of them are fully thought out.

    I mentioned earlier about the need for keeping track of the starting cells and lengths of the 1D submatrices. One possibility would be to create a tracking matrix of the same size as the one you're working with, but whose cells contain a pair of numbers. Here are some examples of a cell entry in this tracking matrix (T) that I envision:
    T(1, 2) = (3, 0)
    The cell at row 1, column 2 is the start of a horizontal submatrix of length 3.

    T(2, 1) = (0, 3)
    The cell at row 2, column 1 is the start of a vertical submatrix of length 3.

    T(2, 1) = (3, 4)
    The cell at row 2, column 1 is the start of a horizontal submatrix of length 3 and a vertical submatrix of length 4.

    All other entries in the tracking matrix would be (0, 0).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook