Python - 获取将矩阵转换为 RREF 所需的步骤

Question

我有以下问题：

我有两个二进制矩阵，可能看起来像这样：

    | 1 | 0 | 1 | 0 | 0 | 1 |       | 1 | 0 | 0 | 0 | 0 | 0 |
    | 0 | 1 | 1 | 1 | 0 | 1 |       | 0 | 1 | 0 | 0 | 0 | 0 |
a = | 0 | 0 | 0 | 1 | 1 | 0 |   b = | 0 | 0 | 1 | 0 | 0 | 0 |
    | 1 | 0 | 0 | 0 | 0 | 1 |       | 0 | 0 | 0 | 1 | 0 | 0 |
    | 0 | 0 | 0 | 1 | 0 | 0 |       | 0 | 0 | 0 | 0 | 1 | 0 |
    | 1 | 0 | 1 | 0 | 0 | 1 |       | 0 | 0 | 0 | 0 | 0 | 1 |

现在我想找到矩阵 a 的行梯队形式（不一定是简化的行梯队形式），然后在矩阵 b 上应用相同的矩阵运算，这将导致如下所示：

    | 1 | 0 | 1 | 0 | 0 | 1 |       | 1 | 0 | 0 | 0 | 0 | 0 |
    | 0 | 1 | 1 | 1 | 0 | 1 |       | 0 | 1 | 0 | 0 | 0 | 0 |
a = | 0 | 0 | 1 | 0 | 0 | 0 |   b = | 1 | 0 | 0 | 1 | 0 | 0 |
    | 0 | 0 | 0 | 1 | 1 | 0 |       | 0 | 0 | 1 | 0 | 0 | 0 |
    | 0 | 0 | 0 | 0 | 1 | 0 |       | 0 | 0 | 1 | 0 | 1 | 0 |
    | 0 | 0 | 0 | 0 | 0 | 0 |       | 1 | 0 | 1 | 0 | 1 | 1 |

使用 numpy 将第一个矩阵转换为 rref 效果很好，除了我无法知道执行了哪些行操作，所以我无法在第二个矩阵上应用相同的操作。

现在这只是一个例子，但实际矩阵将是 50.000x50.000 或更大，不一定是正方形。我尝试实施自己的解决方案，但它太慢了。是否有一些东西可以做我想做的事，或者我是否必须尝试优化我自己的解决方案？

感谢您的帮助

/莫滕

Answer 1

水平连接矩阵c = np.c_[a,b]并在该矩阵上使用rref，这样您就不需要存储中间矩阵。

请注意，rref在计算上是无用的，除非非常非常特殊的场合。因此，如果有必要，更喜欢 LU 分解。

Answer 2

事实证明，它有点混乱，但有一个解决方案。 scipy.linalg.qr https://en.wikipedia.org/wiki/QR_decompositionhttp://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.qr.html#scipy.linalg.qr

import scipy.linalg as la
matrix = [[randint(2) for k in range(4)] for j in range(5)]
(q, r) = la.qr(matrix)

矩阵：

[[1, 1, 1, 1], [0, 1, 1, 1], [0, 0, 0, 1], [1, 1, 1, 1], [1, 0, 0, 1]]

r ：

array([[-1.73205081, -1.15470054, -1.15470054, -1.73205081],
       [ 0.        , -1.29099445, -1.29099445, -0.77459667],
       [ 0.        ,  0.        ,  0.        ,  1.        ],
       [ 0.        ,  0.        ,  0.        ,  0.63245553],
       [ 0.        ,  0.        ,  0.        ,  0.        ]])

numpy.dot(q,r) ：

array([[  1.00000000e+00,   1.00000000e+00,   1.00000000e+00,
          1.00000000e+00],
       [  0.00000000e+00,   1.00000000e+00,   1.00000000e+00,
          1.00000000e+00],
       [  0.00000000e+00,   0.00000000e+00,   0.00000000e+00,
          1.00000000e+00],
       [  1.00000000e+00,   1.00000000e+00,   1.00000000e+00,
          1.00000000e+00],
       [  1.00000000e+00,   0.00000000e+00,   1.11022302e-16,
          1.00000000e+00]])

所以matrix = q*r，r是matrix的排梯队形式。剩下要做的就是解决 x 的matrix2 = q*x。0并不总是完全0的舍入问题是以数字方式求解矩阵的已知问题。