algorithm - 为什么置换矩阵用于交换数组的行？

Question

使用置换矩阵交换行有什么好处？为什么要创建一个置换矩阵，然后应用矩阵乘法，这比仅使用 for 循环交换行更容易、更有效吗？

Answer 1

置换矩阵是一种有用的数学抽象，因为它们允许使用矩阵代数的正常规则进行分析，而无需引入其他类型的运算。

在软件中，好的实现不会将置换矩阵存储为完整矩阵，它们会存储置换数组并直接应用它(无需完整矩阵乘法)。

根据矩阵的大小以及涉及的操作和访问模式，根本不将置换应用于内存中的数据，而只是将其用作额外的间接寻址可能更便宜。因此，当您请求 (P * M)(i,j) 时，其中 P 是一个置换矩阵，而 M 是一些其他矩阵您正在排列，根本不需要重新排列数据，而是元素访问操作将在您访问元素时查找排列后的行。