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

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

• 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. Oct 15 '16 at 11:26
• 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. Dec 18 '16 at 20:34

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'.
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}$$
• 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. Nov 15 '16 at 15:15
• 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). Nov 15 '16 at 15:18