5
$\begingroup$

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:

  1. Rows can be swapped
  2. 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.

For example:

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.

UPDATE

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:

  1. pick some cell with a 1
  2. strike through it vertically and horizontally
  3. for each cell containing a 1 which gets struck through, perform the steps 2-3.
  4. 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.

$\endgroup$
  • $\begingroup$ I haven't thought too hard about this yet but I think it might be related to some graph theoretic problem. Do you know any graph theory? $\endgroup$ – Casteels Jun 29 '14 at 7:02
  • $\begingroup$ Yes, I know a little graph theory. I think that would be also interesting to see a graph theoretic formulation of this. Do you have some ideas? $\endgroup$ – proskor Jun 29 '14 at 8:33
  • $\begingroup$ Some ideas maybe, but I need to think through them a bit. By the way, do you always want to get just two "blocks" from your input? That wasn't clear in the original question. $\endgroup$ – Casteels Jun 29 '14 at 8:44
  • $\begingroup$ No, but splitting into two blocks would be enough to serve as an example. The actual problem is to fit a big but sparse matrix on a sheet of paper, such that it looks more or less good. Since the width of the paper sheet is the "bottleneck", only the width of the blocks is relevant. And, of course, if the matrix is really big, more than two blocks would be required. But they should be more or less of the same size, such that the arrangement will be most "compact". So, this is basically an optimization problem. $\endgroup$ – proskor Jun 29 '14 at 8:49
2
$\begingroup$

Basically this is about bipartite graphs: graphs where the vertex set is split into two parts that I will call type $X$ vertices and type $Y$ vertices, and where all edges have one end of type $X$ and another of type $Y$. These graphs represent a relation between elements of type $X$ and $Y$, the relation holding between $x$ and $y$ if there is an edge between $x$ and $y$. In your example type $X$ elements would be row indices and type $Y$ elements would be column indices (so a number that is both a row index and a column index gives rise both to a type $X$ vertex and an unrelated type $Y$ vertex), and the edges of the graph are between pairs $(x,y)$ where the matrix has a nonzero entry in position $(x,y)$. Permuting rows respectively columns now just means renumbering the type $X$ respectively type $Y$ vertices, so you can think of these sets as being unlabelled, which helps you abstract away from the order in which rows and columns are initially given.

Now what you want amounts to partitioning the whole graph into chunks such that there are no edges between different chunks (and moreover you want each chunk to have specified numbers of type $X$ and type $Y$ vertices). The finest partitioning with this property is obtained by computing the connected components of you bipartite graph. There is a straightforward and efficient algorithm to compute connected components. Even for sparse graphs, it is quite possible that there is only one connected component, in which case you are out of luck. Supposing however that there are many connected components, then you next task is to group together connected components into chunks so that the number of type $X$ and type $Y$ vertices matches your specification for each chunk. This is a kind of bin packing problem, but with an extra twist that sizes of items to be packed are pairs of numbers rather than single numbers (namely the numbers of type $X$ and type $Y$ vertices), which sizes are added together as $2$-component vectors.

This does not look as an easy problem, neither with respect to it being likely that there is a solution at all, nor with respect to allowing efficient algorithms for solving the general solvable case. I would personally be somewhat demotivated to even spend much effort on this problem.

$\endgroup$
  • $\begingroup$ So, my fears have been confirmed. Thank You for this great explanation. One last question though: what would you suggest, how should I approach the original problem (fitting a big matrix on a sheet of paper of limited width)? Is there a way to approximate this somehow? I though of using a greedy algorithm, but maybe there is something else I don't know. $\endgroup$ – proskor Jun 29 '14 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.