2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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.. $\endgroup$
    – Vim
    May 11 '18 at 16:58
  • 1
    $\begingroup$ Er, what? It is equivalent to conjugating it with a permutation matrix, which is invertible and has determinant $1$ $\endgroup$ May 11 '18 at 16:59
  • $\begingroup$ @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. $\endgroup$
    – Vim
    May 11 '18 at 17:02
  • 1
    $\begingroup$ $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$" $\endgroup$ May 11 '18 at 17:02
  • 1
    $\begingroup$ @AnalysisStudent0414 this clarifies. Would you care to put it in the main text of your question to better convey what you mean? $\endgroup$
    – Vim
    May 11 '18 at 17:03
1
$\begingroup$

You can implement something to do this in MatLab, or any other software.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.