# Finding a row permutation that makes a matrix more “blocks-like”

Disclaimer: what follows arise in a context from Computer Science, but it seems to me that my questions were more likely to be solved from mathematicians than from computer scientists.

Let suppose the following scenario, pointing out that everything should be stated in asymptotic terms. Let $M$ a logical and "almost-block" matrix of the form $\left (\begin{array}{cc} A &\ \epsilon\\ \epsilon &\ B \end{array} \right )$, where $A$ and $B$ are block of dimension circa $\frac{n}{2}\times \frac{n}{2}$ with $\log n$ nonzero entries for each row, and the $\epsilon$ are almost-zero-matrix with at most one nonzero entry on some row but not exceeding a total of $\log n$ nonzero entries.

Given a permutation matrix $P$, we can conjugate $M$ by $P$ obtaining $W=P^{-1}MP$ that could be quite far from being an almost-block matrix. The question is: starting with $W$, knowing that it come from a almost-block matrix $M$ by a similarity transformation with a permutation matrix $P$, is there a way to efficiently find $P$? That is to say, a efficient way to find $M$? About this question, on Wikipedia I found a more strong case, where both $M$ and $W$ are known and only $P$ has to be found. Is there something more general that could be said?

As a related question, is there a rigorous way to measure how much a matrix is near to being a block matrix? I mean, some kind of "norm".

My heuristic approach to the problem above was the following. Both $M$ and $W$ are the adjacency matrix of a certain graph with $n$ vertices that has a minimal cut of $\log n$ edges between two component of $\frac{n}{2}$ vertices having an average degree of $\log n$. $W$ and $M$ are then equivalent up to a relabeling of the vertices (that is, the permutation matrix we are looking for). Since every edge is given a weight of one, as is well known, the $n$-th power of these matrices represent on their entries $a_{ij}$ how many distinct paths of length $n$ are there to go from a node $i$ to the other node $j$. Since between the two component (that are, the two blocks of $M$), there are far less edges than among their own nodes, it follows that from a node $i$ there are lots more paths to other nodes in its component than to the nodes in the other component (in an absolutely intuitive sense, we are estimating a kind of "flow" that the cut edges choke from a component to the other). Then, we can just consider $W^k$ for a suitable $k$; it should be feasible to recognize the two submatrix just by dropping out the smaller entries.

-
Maybe it's better to just try to get some 0-1 permutation matrix into block form than the general case that you have here. The blocks probably consist of the cycles of the permutation... – Peter Sheldrick Oct 3 '12 at 19:22
If you consider the nonzero entries of $W$ as the adjacency matrix of a graph, this seems very similar to a graph partitioning problem. – Rahul Oct 3 '12 at 19:53
I found it being somehow related to the conductance of the underlining graph. – Immanuel Weihnacht Oct 4 '12 at 16:59
It seems that is just a problem of clustering: given $W$, we have to solve the uniform sparsest cut problem for the graph whose adjacency matrix is $W$. – Immanuel Weihnacht Oct 8 '12 at 16:07