已知非方阵满秩矩阵A通过交换行的位置以及列的位置得到B,P*A*Q=B,已知A和B,怎么求得P和Q?只是互换位置,行（列）与行（列）之间不进行加减运算
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/28 04:48:33
已知非方阵满秩矩阵A通过交换行的位置以及列的位置得到B,P*A*Q=B,已知A和B,怎么求得P和Q?只是互换位置,行（列）与行（列）之间不进行加减运算
已知非方阵满秩矩阵A通过交换行的位置以及列的位置得到B,P*A*Q=B,已知A和B,怎么求得P和Q?
只是互换位置,行（列）与行（列）之间不进行加减运算
已知非方阵满秩矩阵A通过交换行的位置以及列的位置得到B,P*A*Q=B,已知A和B,怎么求得P和Q?只是互换位置,行（列）与行（列）之间不进行加减运算
满秩这个条件其实不重要,不过显然不应该用SVD来解这个问题,不仅计算量大,而且会由于舍入误差引发不必要的麻烦,更严重的问题是出现重奇异值的时候不保证成功,那么对应的奇异向量可以差一个普通的正交变换而未必是排列阵,不保证求得出解.
理论上讲这个问题一定可以归结为二分图匹配,不过感觉上这样还是太麻烦了一点.
如果只考虑平均情况的话,所谓的“观察法”确是合理的手段,因为如果A中没有重复的元素,那么每个元素所在的行和列都唯一确定.这样只要A的大多数元素不重复只要简单遍历一遍就能唯一确定P和Q,所以困难的只是A有较多重复元素的情形.
注意对于这个问题而言通常P和Q可以独立地确定,也就是说可以归结为向量的匹配.
先定义对称函数：
f(a1,a2,...,an)=f(ak1,ak2,...,akn),其中k1,k2,...,kn是1,2,...,n的任一排列.
比如f(a1,a2,...,an)=a1+a2+...+an就是一个对称函数.
给定一个对称函数f,对A的每行都算出f的值得到f1,f2,...,fm,对B也算一遍,就可以直接进行匹配（最不济也可以先排序再匹配）,运气好的话这样已经足够确定行变换P.
当然运气不好的话对部分行而言会出现fi=fj的情形,所以上述过程应该先将fk分组,然后只需继续在每组中确定相应的行排列,那么再换一个对称函数.
为了保证算法可行,可以先取每行的最大值及行和,然后每一个无法区分的组中继续用sum ai^2,sum ai^3,...这样的基本对称多项式,如果一个分组中含k个元素,那么最多取到k次就够了.由Vieta定理可以知道如果这样仍不能区分就可以唯一确定这些行的所有元素（包括重数）,只是相差一个次序,这种最坏情况再引进列排序就完全解决.
当然,考虑运气的因素的话比较合理的次序是先做一两次行检测再做一两次列检测,迅速压缩未确定的子阵,然后才对行列交错地使用高次的对称多项式,最后如果取完必要的对称多项式之后仍有无法确定的行或列,只要随意地将相等的元素匹配起来就行了.
如果要针对有非常多的重复元素的矩阵进行进一步的改进,那么先对重复元素进行计数（这事实上也是一种对称函数）,可以减少对于对称多项式的依赖.
这个只能观察A,B的元素的特点
写出对应的初等变换, 再转换成初等矩阵
把A,B给出来我帮你我用了奇异值分解，算然满足P*A*Q=B，但是P和Q矩阵都是小数。 我先给出A和B吧奇异分解我不会哦 我用的是初等方法 A --> r2<->r4 1 0 0 0 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 c2<->c...
全部展开
这个只能观察A,B的元素的特点
写出对应的初等变换, 再转换成初等矩阵
把A,B给出来我帮你
收起