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?

  • $\begingroup$ Yes, but at one of the steps (mostly at 2.) you need to take the inverse permutation. $\endgroup$ – Berci Apr 15 at 14:51
  • $\begingroup$ @Berci I'm struggling with this a bit. When I do the math, it seems like the standard $RMR^T$ transform. But when I think about it logically, it does not make sense. In the above notation, there is no fundamental difference between the rows dimension and the columns dimension. Why should one of them be permuted differently than the other? $\endgroup$ – Aleksejs Fomins Apr 16 at 8:39

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.

| cite | improve this answer | |

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.