# Separate "blocks" in a matrix by permuting rows and columns

The input is a huge $n \times n$ matrix. I know that, without changing the basis as a set, but only the order of its elements, this matrix is divided in certain blocks.

To clarify, this $5 \times 5$ matrix \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 2 & 0 & 1 & 0 \\ 4 & 0 & 1 & 0 & 3 \end{pmatrix} should become \begin{pmatrix} 1 & 2 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 3 & 1 & 4 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix}

Is there any utility or software available to do this easily? I do not care about the specific permutation, I just need to look at such blocks without crossing my eyes.

To clarify more: this corresponds to finding a "correct" ordering of the elements of the basis, i.e., permutation matrix $A$ (i.e. a matrix with only one $1$ in each column, and the rest $0$) such that $AMA^{-1}$ has the required form.

• What's the purpose for permutating the vectors to divide the matrix into blocks? This action may not preserve a lot of things (similarity, congruence, eigenvalues, determinants etc.). So it may not be applicable in the ways you think..
– Vim
May 11 '18 at 16:58
• Er, what? It is equivalent to conjugating it with a permutation matrix, which is invertible and has determinant $1$ May 11 '18 at 16:59
• @AnalysisStudent0414 First permutations can have both 1 or -1 as their determinant, and second, I don't think it's called conjugation since the row and column operation aren't necessarily symmetric.
– Vim
May 11 '18 at 17:02
• $B=PAP^T$, just the change of basis that corresponds to stuff like "instead of considering $v_1, v_2, v_3$ consider $v_2, v_3, v_1$" May 11 '18 at 17:02
• @AnalysisStudent0414 this clarifies. Would you care to put it in the main text of your question to better convey what you mean?
– Vim
May 11 '18 at 17:03

You will just take the first row/column, and put $P_{1}$ to be an arbitrary permutation (matrix) that moves all of the $1 \leq j \leq n$ such that either $A_{1,j}$ or $A_{j,1} \neq 0$ to positions $1,2,3,\ldots,k_{1}$.
Then take the second row/column, and put $P_{2}$ to be an arbitrary permutation (matrix) that leave $1$ fixed and moves all of the $2 \leq j \leq n$ with $A_{2,j}$ or $A_{j,2} \neq 0$ to positions $2,3, \ldots, k_{2}$.
Continue this process for $1 \leq i \leq n$, so at step $i$, you put $P_{i}$ to be a permutation that leaves $1,2, \ldots, i-1$ fixed and moves all of the $i \leq j \leq n$ with $A_{i,j}$ or $A_{j,i} \neq 0$ to positions $i,i+1,\ldots,k_{i}$.
Then you will have $P = P_{n}P_{n-1}\ldots P_{1}$.