Suppose we have a block-diagonal matrix $M$, but the block diagonal structure is not immediately apparent from looking at the matrix because the rows/columns are shuffled.
I wish to find a reordering of rows and columns, $M' = P M P^{-1}$, where $P$ is a permutation matrix, that will make the block structure apparent.
When this problem is solved, I wish to do the same for the case when the matrix does not have a perfect block structure, but there are a few non-zero elements scattered here and there.
One idea is to look at the eigenvectors, and the position of non-zero elements in each eigenvector will show the elements (i.e. row/column indices) belonging to t he respective blocks. Is this correct?
Any pointers are welcome. I'm sure there must be an easy solution to this.
Best Answer
If the matrix corresponds to a $d$-regular graph, then one can make some easy observations. For instance, if it is a block matrix with $k$ components, then there will be a $k$-dimensional eigenspace of vectors with eigenvalue $d$. As you say, this gives significant information about the blocks. You can't say that an arbitrary eigenvector will pick out a component, but you can say that the eigenspace will be generated by characteristic functions of components, and the eigenvectors will be constant on the components. One would have to make the notion of approximation precise, but presumably there are reasonable notions of approximation such that if a matrix is approximately a block matrix with $k$ components and is still $d$-regular, then there are several vectors $v$ that approximately satisfy $Av=dv$ and that are approximately constant on the approximate components. And finally, if all you're interested in is the components, then probably it's not too important what the values of the matrix are (as long as they are clearly zero or clearly non-zero), so perhaps you can reweight them so as to reduce to something like the regular case -- but I'm less sure about that last idea. All this would of course rely on points within components being significantly more connected than points in different components.
Another, related, way of detecting this would be to look at powers of the matrix, which would fill up the approximate components much more quickly than the links between components. In fact, I'd be tempted to pick a point and apply the matrix a few times to that point (considered as a unit vector) in order to identify its "approximate component". In the exact case, the component would consist of all points where the value is non-zero, whereas in the approximate case one would have to go for some kind of cutoff. Then one could repeat for other points. The resulting "components" might overlap a bit, but one could then just arbitrarily assign points in the overlap to some component or other.
I'm not sure what to make of your suggestion that coming up with a precise definition is part of the problem: I think there are probably several reasonable precise definitions, each of which leads to a different version of the problem. So either you should be more specific about why you want to do this or you should just choose your method of proof and define the problem in such a way that the method works. (So, for instance, you might decide on the above cutoff method and then choose a notion of "approximate block matrix" that guarantees that that process approximately identifies -- in some other sense that you make precise -- the approximate blocks.)
This kind of question is of interest in additive combinatorics. If $E$ is a set of integers, one can define a matrix $A$, indexed by $E\times E$, where $A(x,y)$ is the number of pairs $(z,w)\in E^2$ such that $x-y=z-w$. It would be nice to have a good way of splitting $E$ up into "approximate components" of this matrix/weighted graph, which would be "approximate additive components" of $A$. Even nicer would be to be able to say something nice about the additive structure of these components, on the assumption that there are at least $c|E|^3$ quadruples $(x,y,z,w)\in E^4$ with $x-y=z-w$.