寻找矩阵排列矩阵的算法

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. 什么是正确的 P，可以将 elems 矩阵正确地排列成 M' 矩阵？
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)

- Mittenchops

---

我倾向于认为矩阵中不存在P的概念，但我不清楚原因。我知道矩阵elems_prime不可逆，但向量elems也不可逆（向量没有逆），然而elems存在P。如果在矩阵情况下存在P，它不能仅为0,1，必须具有负值，甚至可能是非整数值？ - Mittenchops

Answer 1

注意，M'的列空间比elem'的列空间高阶。这意味着不存在从elem'到M'的线性映射，因为线性映射不能增加矩阵的行或列空间（考虑这个问题时，将其视为基础变换很有用）。

由此可知，任何由elem' * P生成的M'的秩最多为1，只剩下传统置换矩阵可以作为P'的候选。

如果我们考虑从M'返回到elem，那么这是一个完全不同的问题，这种不对称性也值得注意。

- Jared Goguen

---

你是在指 M 和 elems，还是 M' 和 elems'？我担心我不明白后者的列空间对于两个术语都是4的含义：elems' * P = M 3x4 4x4 3x4 - Mittenchops

我指的是 M' 和 elem'（已经进行了更新）。"列空间" 不是指矩阵中的列数，而是指由这些列张成的向量空间的 "维度"。结论是，除了在像你在例子中给出的置换矩阵那样的情况下，P 不存在。如果这个答案还不清楚，请您可能需要复习一些线性代数（特别是向量空间）的知识。 - Jared Goguen

我必须承认，我总是需要更多的线性代数知识，但我不认为你的说法是正确的——M'的列空间是4，因为这是线性无关列的数量：https://en.wikipedia.org/wiki/Row_and_column_spaces。`elem'`确实有线性相关的列，但如果它能为M'生成置换矩阵，我完全可以重新定义该矩阵。 - Mittenchops

elem'的列空间维数为1，由{k*(1, 1, 1) | 对于所有实数k}描述。当你将elem'乘以另一个矩阵M时，积的列再次是elem'中列的线性组合。因此，elem' * M中的每一列都将具有形式a*(1, 1, 1)+b*(1, 1, 1)+c*(1, 1, 1)+d*(1, 1, 1)=k'*(1, 1, 1)，其中k'为某个常数。这表明elem' * M的列是线性相关的，并且维数为1（或可能为0）。因此，elem' * M不可能像您所需的那样等于完全秩矩阵。是的，您需要以不同的方式定义elem'。 - Jared Goguen

Answer 2

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

原因在于，通常情况下，如果我们将一个nxm矩阵乘以一个mxp矩阵，我们会得到一个nxp矩阵。这里的elems是一个向量，是一个1x4矩阵，因此elems * P必须是某种1x?矩阵。通过使P更长，您可以使M更长，但您必须改变elems以使M更高。

顺便说一句，在线性代数中，将向量翻转为列，并将矩阵放在左边是标准做法。原因在于矩阵表示线性函数，这将矩阵放在与线性函数相同的位置。因此，在从函数符号转换为矩阵符号时非常方便。此外，如果您必须编写一个方阵，那么在右侧写一个垂直向量比在左侧写一个水平向量占用更少的页面空间...

- btilly

---

谢谢。对于我提出的第一个情况，这是正确的，但我正在寻找更多关于我的问题的向量。我的elems_prime矩阵是3x4，M_prime是3x4，我正在寻找能够找到一个4x4的P的算法。 - Mittenchops

@Mittenchops 如果是这样，那就回到基础吧。你有12个方程（每个M_prime中的条目一个）和16个变量（每个所需P中的条目一个）。建立线性方程组并通过行约简解决它。你应该得到一个4维解空间。但要注意，很可能没有任何可能的解是置换矩阵。 - btilly

不会有任何解决方案 - 系统是不一致的。观察通过将“elem”第一行与任意列相乘形成的三个方程式（请注意，“M”的列不是“elem”中列的线性倍数）。 - Jared Goguen