Find a permutation matrix (using the Matlab's function $symrcm$) of a matrix $A(2:end, 2:end)$

Question

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:

   

   Ignore the specific numbers that you see in the plot.

Question

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...

Answer 1

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.

Answer 2

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}$$