Why are permutation matrices used to replace array strings?

Question

What are the benefits of using a permutation matrix to replace strings? Why is it necessary to create a permutation matrix, and then apply matrix multiplication, is simpler and more efficient than just changing lines with a for loop?

Answer 1

Permutation matrices are a useful mathematical abstraction because they allow you to analyze using the normal rules of matrix algebra without having to introduce another type of operation.

In software, good implementations do not save the permutation matrix as a complete matrix, they store an array of permutations and directly apply it (without full matrix multiplication).

Depending on the size of the matrices and the operations and access patterns used, it may be cheaper not to apply the permutation to the data in memory in general, but simply use it as an additional indirectness. So, when you ask for (P * M)(i,j) , where P is the permutation matrix, and M is some other matrix that you rearrange, the data does not need to be reset at all, and the element access operation will look like a permutation string when accessing an item.

Answer 2

The first thing that comes to my mind is a problem called spatial locality. Caching technologies suggest that when accessing a memory location, it is possible to access nearby memory locations. In some programming languages, elements in rows are neighbors, while elements in columns are neighbors in others. It depends on the implementation. I assume that permutation matrices are designed to solve this problem, since matrix multiplication optimization is one of the problems that the scientific community algorithms mainly work on improving. A simple loop structure will not be able to use caching technology to improve performance.