Permute a matrix given vector permutation

matricespermutationsvectors

Let $M_{i,j} = f(x_i, x_j)$ where $\vec{x}$ is an n-dimensional vector and $f$ is some well-behaved function. Now, let $\tilde{x}$ be a permutation of the elements of $x$. I would like to find the matrix $\tilde{M}_{i,j} = f(\tilde{x}_i, \tilde{x}_j)$. I suspect that I can achieve this the following way:

  1. Compute matrix $M$
  2. Permute rows of matrix $M$
  3. Then, permute columns of matrix $M$ using the same permutation

Is this true?

Best Answer

Ok, I think I have found out the answer for my problem. There are two ways to think about the sandwich matrix multiplication

  1. $\tilde{M}_{ij} = \sum_{kl}R_{ik} R_{jl} M_{kl}$
  2. $\tilde{M} = RMR^T$

It is easy to see that both are equivalent ways of writing the same thing. But logically they are somewhat different ways to approach the same problem.

  1. If I want to permute the matrix by manually exchanging the order of rows and columns, I would perform EXACTLY THE SAME operation on both rows and columns, because there is no fundamental difference between dimensions.

  2. If I want to permute the matrix using the rules of matrix multiplication, then according to those rules I have to multiply by the transpose of the permutation matrix from the right.

Related Question