I've the following Matlab code:

r = symrcm(A(2:end, 2:end)); 
prcm = [1 r + 1]; 
spy(A(prcm, prcm));

where A should be sparse connectivity matrix.

I understood what it does:

  1. Finds a permutation vector r of the submatrix of A A(2:end, 2:end) (produced by the reverse Cuthill-McKee algorithm)

  2. Creates a vector prcm which is basically a vector with a $1$ in the first position and all other elements of r increased by $1$.

  3. This prcm vector applied to A as A(prcm, prcm) logically means that we're going to permutate all rows and columns of A according to the reverse Cuthill-McKee algorithm except the first row and the first column. So the resulting matrix would look something like this:

    enter image description here

    Ignore the specific numbers that you see in the plot.


Why would one want such a permutation of the rows and columns of a matrix?

From what I've been reading and I've observed applying, for example, the guassian elimination to this matrix would produce a disastrous fill-in after trying to remove all entries of the first row (Check chapter 5.7 from "A first course in numerical methods" by Ascher and Greif). So, who wrote this code definitely didn't want to find a permutation of $A$ to apply the guassian elimination...

  • $\begingroup$ Well, I have no idea at the moment, but it would be much easier to guess if you told us what the purpose of the full program is, or at least what it does with $A$ after the permutation. $\endgroup$ Oct 15, 2016 at 11:26
  • $\begingroup$ Looks like the author is performing a visual inspection and for some reason doesn't want to include the first row col and symrcm is compacting the visual inspection area. That's my two cents of razors. $\endgroup$
    – percusse
    Dec 18, 2016 at 20:34

2 Answers 2


From your comment "The plot emphasises expectedly the connections of node 1", I guess that maybe the idea is showing that node 1 is connected not only to a set of nodes that are "one close to the other", but its interconnections are spread somewhat evenly across the graph.

Reverse Cuthill-McKee in theory reorders the nodes so that clusters are mapped into nearby positions. Or at least some clusters: those which include the starting vertex. Or something morally similar, at least. So the fact that the nonzeros in row 1 are not an almost adjacent set of entries, (say, $\{2,3,\dots,20\}$), but are spread uniformly across the matrix somehow shows that 1 is a 'well-connected node'.

If that is really the answer, then it seems quite an odd way to measure 'well-connectedness'. There is a lot of academic literature on measures of centrality of vertices in a graph, from Pagerank to the Estrada index, and I have never seen RCM used for this purpose.


A very simple hypothesis is that a problem has to be solved in which the "degree of freedom" of node 1 is "constrained". Suppose that the degree of freedom at node $i$ is $u_i$ and that the problem to be solved is $$K\,u=f,$$ where matrix $K$ is symmetric and singular, and we now that $f$ belongs to the range of $K$. A common approach in such cases, if the null space of $K$ has dimension 1, is to impose $u_1 = 0$ and simply solve $$K_{{2\dots N},{2\dots N}} \; u_{2\dots N} = f_{2\dots N}$$

  • $\begingroup$ No, I mean $u_1=0$, so that you obtain the solving system simply by deleting first row and column of matrix $K$. This is a common situation say in heat equation with Neumann b.c, where the solution is determined up to an additive constant. $\endgroup$
    – Stefano M
    Nov 15, 2016 at 15:15
  • $\begingroup$ Oh, ok, you are right, I was thinking to a different setup (finding $u$ in the kernel of $K$, so the indetermination is on a multiplicative coefficient). $\endgroup$ Nov 15, 2016 at 15:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.