随机二进制矩阵可逆的概率分析Probability that a random binary matrix is invertible

最近两篇帖子都涉及元素为0和1的可逆矩阵。如果随机填充一个n×n的0-1矩阵，它可逆的概率有多大？

什么样的逆矩阵？

要计算二进制矩阵可逆的概率，有几种方法，具体取决于你对“逆”的定义。

假设你有一个由0和1构成的矩阵M，正在寻找一个矩阵N，使得MN等于单位矩阵。你是否希望N的元素也必须是0或1？另外，你在进行矩阵乘法时，是执行普通的整数运算，还是在模2下进行？

在之前的文章中，我们是在GF(2)（包含两个元素0和1的有限域）上进行的运算。矩阵中的所有元素只能是0或1，且所有算术运算都在模2下进行。在这种设定下，可以得出一个关于方阵可逆概率的简洁表达式。

如果你是在实数域上工作，那么一个二进制矩阵可逆的概率会更高。一种理解方式是：一个二进制矩阵的逆矩阵可以是二进制的，但这并非必须满足的条件。

另一种理解方式是观察行列式。如果你将一个矩阵M视为一个实数矩阵，其元素碰巧只有0或1，那么M可逆当且仅当其行列式非零。但如果你将M视为GF(2)上的矩阵，其元素只能是0或1，那么M可逆当且仅当它在GF(2)下的行列式非零。如果M作为实数矩阵的行列式是一个非零偶数，那么M在实数域上是可逆的，但在GF(2)上不可逆。

GF(2)上的可逆概率

在GF(2)上，一个随机矩阵可逆的概率是多少？实际上，更容易回答一个更一般的问题：一个在GF(q)（包含q个元素的有限域）上的随机n×n矩阵可逆的概率是多少？这个概率是

当q=2且n=8时，这个概率约为0.289919。对于更大的n值，这个概率大致相同，并随着n→∞而收敛到约0.288788。

ℝ上的可逆概率

一个8×8的、元素为随机0和1的矩阵在实数域上可逆的概率是多少？我们可以通过模拟来估计这个概率。

import numpy as np

def simulate_prob_invertible_real(n, numreps=1000):
    s = 0
    for _ in range(numreps):
        M = np.random.randint(0, 2, size=(n, n))
        det = np.linalg.det(M)
        if abs(det) > 1e-9:
            s += 1
    return s/numreps

当n=8时，我运行了10,000次代码，得到的概率约为0.5477。

当n=32时，我得到的概率是1。显然，一个32×32的二进制矩阵有可能是奇异的，但在10,000次随机抽取中，这种情况并未发生。