I am not a mathematician, so please excuse me if this question turns out to be trivial. I need this at work, but I could not figure out how to solve this efficiently, though it looks like it might be a very common, and perhaps simple (however I have a bad feeling about this) problem.
Anyway, given is a matrix of boolean values, i.e. zeros and ones.
Allowed operations are:
- Rows can be swapped
- Columns can be swapped
The problem: using only these two operations, is it possible to convert the input matrix to a kind of a block diagonal matrix, except that the blocks should not necessarily be square matrices, but of restricted size, i.e. the number of rows (or columns) in each block should be equal to a given number.
Let the input matrix be:
a b c d e f --+------------ w | 1 0 0 0 1 0 x | 0 0 0 1 0 1 y | 1 0 1 0 0 0 z | 0 1 0 1 0 0
And the blocks should have the size (2,3), then one possible solution would be:
a e c d b f --+------------ w | 1 1 0 0 0 0 y | 1 0 1 0 0 0 x | 0 0 0 1 0 1 z | 0 0 0 1 1 0
Here, the rows x and y and the columns b and e have been swapped.
The problem can also be relaxed such that only the number of columns (or rows, but not both) of the sub-matrices is fixed.
I need this in order to fit a rather big but sparse matrix on a sheet of paper of limited width, and the idea was to rearrange it like described above and split it in half. I know that it is not always possible, but in cases where it is, I would proceed by displaying the result matrix like this:
a e c --+------ w | 1 1 0 y | 1 0 1 d b f --+------ x | 1 0 1 z | 1 1 0
So my question is: what is this problem called generally? Is there an alternative formulation? And, most importantly, is there an (efficient) algorithm to solve it (I mean, there must be one, right)? Is there a text or something on the web where I can look it up?
Thank you very much in advance.
I did some progress on this and - if I didn't make a mistake - it turns out that it reduces to PARTITION.
Basically, it is relatively easy to group columns in equivalence classes by checking whether there are any rows which have 1s in both of the columns. I came up with this algorithm:
- pick some cell with a 1
- strike through it vertically and horizontally
- for each cell containing a 1 which gets struck through, perform the steps 2-3.
- remove the sub-matrix containing struck out rows and columns and repeat steps 1-4 till there are no 1s left
That way we get the set of smaller sub-matrices which should then be combined to form two matrices of equal width (the goal was to split the input matrix in half). Actually, in case where there are all-0-columns, these can be used to pad other matrices to a required size, but this just complicates things.
Also, in the second phase (combining the sub-matrices), only the width of the sub-matrices is relevant, therefore we can consider a multi-set of positive integers representing the width of each sub-matrix.
Requiring that this set is to be partitioned into two sub-sets which sum up to equal size, well, that's exactly PARTITION (I knew there was something bad about this problem ಠ_ಠ).
By the way, splitting the matrix into more than two chunks of more or less equal size reduces to BIN PACKING.