CODEWITHSUNDEEP
algorithmmatrixlanguage-agnostic
Simd
Simd

Reputation: 21223

Determine if some row permutation of a matrix is Toeplitz

A Toeplitz matrix "is a matrix in which each descending diagonal from left to right is constant." Given a binary matrix M, is there an efficient algorithm to determine if there is a permutation of the rows which makes it Toeplitz?

For example, set 

M= [0 1 1]
   [1 1 0]
   [1 0 1]

If you swap the first and second row you get

[1 1 0]
[0 1 1]
[1 0 1]

which is Toeplitz.

In python you can make a random binary matrix as follows.

n = 10
h = 10
M =  np.random.randint(2, size=(h,n))

I would like to apply the test to M.

(Note the matrix M does not need to be square.)

Upvotes: 14

Views: 1412

Answers (3)

Evgeny Kluev
Evgeny Kluev

Reputation: 24647

This problem can be solved in linear O(h*w) time, where h is number of rows and w is number of columns.

Construct a graph where each vertex corresponds to (w-1)-length substring which may be either prefix or suffix of some row in the matrix. One vertex may correspond to several duplicate substrings. Connect these vertexes with h edges. Each edge corresponds to row of the matrix. It is directed from the vertex corresponding to this row's prefix to the vertex corresponding to this row's suffix.

To determine if some row permutation is a Toeplitz matrix, it is enough to check if constructed graph is Eulerian graph. To find permutation itself, it is enough to find Eulerian path in this graph.

We need some efficient way to interconnect vertexes and edges. Straightforward approach assumes comparing each row-substring pair. This is not very interesting because of O(h2*w) time complexity.

Building Generalized suffix tree (or suffix array) for rows of the matrix needs only O(h*w) time. And this tree allows to interconnect vertexes and edges also in linear time: each internal node with depth w-1 represents some (w-1)-length substring (vertex); each leaf attached to this node represents some row's suffix (incoming edge); and each leaf attached to this node's children represents some row containing this substring as a prefix (outgoing edge).

Other alternative is to use hash map. With (w-1)-length substring of matrix row as a key and pair of lists of row indexes (for rows where this substring is prefix/suffix) as a value. Comparing to suffix tree/array approach, this allows simpler implementation, needs less memory (each key needs only space for hash value and pointer to beginning of the substring), should work faster (on average), but has inferior worst-case complexity: O(h2*w).

Upvotes: 10

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

You can conduct a pre-preliminary check for elimination condition:

  1. Find out the column-wise sum of all the columns of the matrix.
  2. Now in any permutation of rows, the values in the columns shall stay in the same column.
  3. So the difference between the sum of any two neighbouring columns should be at the maximum 1.

Also, if i and i+1 are two neighbouring columns, then:

  1. If sum(i+1) = sum(i) + 1, then we know that bottom-most element in column i should be 0 and top-most element in column (i+1) should be 1.

  2. If sum(i+1) = sum(i) - 1, then we know that bottom-most element in column i should be 1 and top-most element in column (i+1) should be 0.

  3. If sum(i+1) = sum(i), then we know that bottom-most element in column i should be equal to top-most element in column (i+1).

You can also conduct a similar check by summing the rows and see if there is any permutation in which the difference between sum of any two neighbouring rows is at most one.

Ofcourse, you will still have to conduct some combinatorial search, but the above filter may reduce the search scenarios.

This is because you now have to search for a pair of (candidate top and bottom) rows that satisfies the above 3 conditions for each pair of neighbouring columns.

Also, this optimization shall not be very helpful if the number of rows is much larger than the number of columns.

Upvotes: 3

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

One simple-minded approach that would work for small matrices is:

Sort the rows of M
For each choice of start row
    For each choice of end row
         construct a Toeplitz matrix T from the given start and end row
         Sort the rows of T and compare to M
         If you find a match then T is a permutation of M that is Toeplitz

This is based on the fact that a Toeplitz matrix is uniquely defined once you know the start and end rows.

However, this approach is not particularly efficient.

Example Python Code

M= [[0, 1, 1],
   [1, 1, 0],
   [1, 0, 1]]

n=len(M)
M2 = sorted(M)
for start in M2:
    for end in M2:
        v = end+start[1:]
        T = [v[s:s+n] for s in range(n-1,-1,-1)]
        if sorted(T)==M2:
            print 'Found Toeplitz representation'
            print T

prints

Found Toeplitz representation
[[0, 1, 1], 
 [1, 0, 1], 
 [1, 1, 0]]
Found Toeplitz representation
[[1, 0, 1],
 [1, 1, 0],
 [0, 1, 1]]
Found Toeplitz representation
[[1, 1, 0], 
 [0, 1, 1], 
 [1, 0, 1]]

Upvotes: 4

Related Questions