I have a mathematical problem which can be expressed in the following form.
I am given a small number (less than 10) of typically 50x50 matrices. Each column of each of these matrices has one 1 and 49 0s, but there is no restriction on the number of 1s in each row; it may range from 0 to 50. Hence these matrices include the permutation matrices, but are in general not invertible and usually have zero determinant.
My task is to efficiently determine whether certain other matrices of similar form (in particular, matrices in which all the 1s have been moved to a single column) are part of the semi-group generated by the given matrices. I have written a couple of algorithm relying on pretty effective heuristics to solve this problem in 99% of cases in about 1 ms. However, running the algorithm on randomly generated sets of matrices shows that in about 1% of cases the heuristics fail and the determination can take up to several minutes, which for my purposes is unacceptable.
Can anyone suggests a way to solve this problem?
One thought that occurs is that this problem is rather similar to the one solved by the Schreier-Sims algorithm for the case of groups with generators in permutation form. However: 1. Does the Schreier-Sims algorithm even work for semi-groups? 2. Algorithms to generate permutation representations from the matrix representation I have are known, but a bit of a pain. 3. So is the implementation of Schreier-Sims itself.
Still, is that the path I need to take?