创建并求逆大规模Galois域矩阵

Question

我有一个128x128的矩阵。这个矩阵里的每个元素都是二进制的，简单来说就是只有0和1。我想在matlab里对这个矩阵进行求逆操作。我发现matlab里有一些函数可以处理有限域的矩阵求逆，具体可以参考这个链接 http://www.mathworks.com/help/comm/galois-field-computations.html。

不过，这些内置的函数只支持最大16x16的矩阵。有没有其他方法可以解决这个限制呢？我也愿意尝试其他工具，比如python或者C/C++。

如果你想试试你的方法，这里有一个测试用的矩阵和它的逆矩阵。

矩阵 A [0,0,0,1,0,0,1,0;1,1,1,0,1,0,1,1;1,1,1,0,1,1,0,1;0,1,0,0,0,0,1,0;0,1,1,1,1,1,1,0;1,0,1,1,0,0,1,0;0,0,1,0,0,0,1,0;0,0,0,0,0,1,0,0]

矩阵 A^-1 [1,1,1,0,0,1,1,1;0,1,1,1,0,0,0,1;0,1,1,0,0,0,1,1;1,1,1,0,0,0,0,1;1,0,0,1,1,0,1,1;0,0,0,0,0,0,0,1;0,1,1,0,0,0,0,1;0,1,0,0,1,1,1,1]

Answer 1

在伽罗瓦域中求一个矩阵的逆，可以通过对 [A | I] 进行 高斯消元法（在伽罗瓦域内进行所有运算）来实现，最终会得到 [I | A^-1]。

下面是一些伪代码，用于执行高斯消元法（行简化）。

def row_reduce(A):
    A_rre = A.copy()
    p = 0  # The pivot

    for j in range(A.shape[1]):
        # Find a pivot in column `j` at or below row `p`
        idxs = np.nonzero(A_rre[p:,j])[0]
        if idxs.size == 0:
            continue
        i = p + idxs[0]  # Row with a pivot

        # Swap row `p` and `i`. The pivot is now located at row `p`.
        A_rre[[p,i],:] = A_rre[[i,p],:]

        # Force pivot value to be 1
        A_rre[p,:] /= A_rre[p,j]

        # Force zeros above and below the pivot
        idxs = np.nonzero(A_rre[:,j])[0].tolist()
        idxs.remove(p)
        A_rre[idxs,:] -= np.multiply.outer(A_rre[idxs,j], A_rre[p,:])

        p += 1
        if p == A_rre.shape[0]:
            break

    return A_rre

我遇到了这个需求，但找不到可以实现这个功能的Python库。所以我创建了一个Python包 galois，它扩展了NumPy数组以支持伽罗瓦域。这个包支持使用普通的 np.linalg 函数进行线性代数运算。

这里有一个使用你测试矩阵的示例。

In [1]: import numpy as np                                                                              

In [2]: import galois                                                                                   

In [3]: GF = galois.GF(2)                                                                               

In [4]: A = GF([[0,0,0,1,0,0,1,0],[1,1,1,0,1,0,1,1],[1,1,1,0,1,1,0,1],[0,1,0,0,0,0,1,0],[0,1,1,1,1,1,1,0
   ...: ],[1,0,1,1,0,0,1,0],[0,0,1,0,0,0,1,0],[0,0,0,0,0,1,0,0]]); A                                    
Out[4]: 
GF([[0, 0, 0, 1, 0, 0, 1, 0],
    [1, 1, 1, 0, 1, 0, 1, 1],
    [1, 1, 1, 0, 1, 1, 0, 1],
    [0, 1, 0, 0, 0, 0, 1, 0],
    [0, 1, 1, 1, 1, 1, 1, 0],
    [1, 0, 1, 1, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1, 0, 0]], order=2)

In [5]: A_inv = np.linalg.inv(A); A_inv                                                                 
Out[5]: 
GF([[1, 1, 1, 0, 0, 1, 1, 1],
    [0, 1, 1, 1, 0, 0, 0, 1],
    [0, 1, 1, 0, 0, 0, 1, 1],
    [1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 1, 1, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 1],
    [0, 1, 1, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 1, 1, 1, 1]], order=2)

In [6]: A @ A_inv                                                                                       
Out[6]: 
GF([[1, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 0, 0, 1]], order=2)