求矩阵置换矩阵的算法

Question

我看到一些类似的问题：

• 从排列向量生成排列矩阵
• https://math.stackexchange.com/questions/345166/what-is-the-name-for-a-non-square-permutation-matrix

给定元素：

elems =  [1,2,3,4] # dimensions 1x4

如果我有一个向量：

M = [4,2,3,1] # dimensions 1x4

我知道有一些排列矩阵p可以相乘elems * p = M，在这种情况下是：

p = 
[ 
  0 0 0 1
  0 1 0 0 
  0 0 1 0 
  1 0 0 0 
] # dimensions 4x4

# eg: 
# elems * P = M
  1x4   4x4 = 1x4

现在，对于我的问题，我感兴趣的是当 M 是非向量、非方阵时它会是什么样子，例如：

M' = [ 
  4 2 3 1 
  4 3 2 1
  1 2 3 4
] # dimensions 3x4

对于相同的

elems' = [
 1 2 3 4
 1 2 3 4
 1 2 3 4
] # where this is now tripled to be conformant dimensions
# dimensions 3x4
#
# meaning P is still 4x4

您可以看到M_prime，elems_prime在这种情况下， 和 仍然只是排列，但现在是多变量，而不是像原来那样只是单个向量。

我知道我不能只做以下事情，因为矩阵不是方形的，因此不可逆：

elems' * P = M'
         P = elems'^-1 * M'

# eg: 
# elems' * P = M'
  3x4   4x4  = 3x4

当我尝试时，至少在 R 中，我看到：

> P <- ginv(elems_prime) %*% M_prime
     [,1]       [,2]       [,3]       [,4]
[1,]  0.1 0.07777778 0.08888889 0.06666667
[2,]  0.2 0.15555556 0.17777778 0.13333333
[3,]  0.3 0.23333333 0.26666667 0.20000000
[4,]  0.4 0.31111111 0.35555556 0.26666667

这能让我恢复M'吗？

> elems_prime %*% P
     [,1]     [,2]     [,3] [,4]
[1,]    3 2.333333 2.666667    2
[2,]    3 2.333333 2.666667    2
[3,]    3 2.333333 2.666667    2

!= M' # No, does not.

所以这是不对的。

我的问题是：

1. 将 elems' 矩阵正确排列到 M' 矩阵中的正确 P 是什么？
2. 找到它的算法的名称是什么？（用 R、Haskell 或伪代码实现都很棒）
3. 有没有办法将 P 的值限制为整数，最好是 0 或 1？

对于 R 再现性

> dput(elems_prime)
structure(c(1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4), .Dim = 3:4)
> dput(M_prime)
structure(c(4, 4, 1, 2, 3, 2, 3, 2, 3, 1, 1, 4), .Dim = 3:4)

Answer 1

当 M 不是向量时，这是不可能的。

这就是原因。一般来说，如果我们将一个nxm矩阵乘以一个mxp矩阵，我们就会得到一个nxp矩阵。这elems是一个向量，它是一个1x4矩阵，因此elems * P必须是1x?某种矩阵。通过做得P更长，你可以做得M更长，但你必须改变elems才能做得更好M更高。

顺便说一句，在线性代数中，标准的做法是将向量翻转为列并将矩阵放在其左侧。原因是矩阵表示线性函数，并且将矩阵放在线性函数所在的位置。因此，从函数符号转换为矩阵符号时非常好。另外，如果你无论如何都必须写一个方阵，那么在右侧写一个垂直向量而不是在左侧写一个水平向量在页面上占用的空间更少......