计算所有子矩阵的满级排序数

Question

我想计算其中元素为1或-1的n个矩阵有多少m具有其所有floor(m/2)+1 by n子矩阵都具有满秩的属性.我当前的方法是天真和缓慢的,并在以下python/numpy代码中.它只是迭代所有矩阵并测试所有子矩阵.

import numpy as np
import itertools
from scipy.misc import comb

m = 8
n = 4

rowstochoose = int(np.floor(m/2)+1)

maxnumber = comb(m, rowstochoose, exact = True)

matrix_g=(np.array(x).reshape(m,n) for x in itertools.product([-1,1], repeat = m*n))

nofound = 0
for A in matrix_g:
    count = 0
    for rows in itertools.combinations(range(m), int(rowstochoose)):
       if (np.linalg.matrix_rank(A[list(rows)]) == int(min(n,rowstochoose))):
           count+=1
       else:
           break
    if (count == maxnumber):
         nofound+=1   
print nofound, 2**(m*n)

有更好/更快的方法吗？我想对n和m进行最多20次的计算,但任何重大改进都会很好.

语境.我有兴趣为https://math.stackexchange.com/questions/640780/probability-that-every-vector-is-not-orthogonal-to-half-of-the-others获取一些确切的解决方案.

---

作为比较实现的数据点.n,m = 4,4应该输出26880. n,m=5,5对我来说太慢了.对于n =2,m = 2,3,4,5,6输出应该是8, 0, 96, 0, 1280.

---

现状2014年2月2日:

• leewangzhong的答案很快但m> n不正确.leewangzhong正在考虑如何解决它.
• Hooked的答案不适用于m> n.

Answer 1

由于还没有人回答，这里有一个没有代码的答案。我看到的有用的对称性如下。

1. 将行乘以 -1。
2. 将列乘以 -1。
3. 排列行。
4. 排列列。

我将通过详尽地生成非同构、过滤它们并对它们的轨道大小求和来解决这个问题。nauty对于第一步和第三步非常有用。假设大多数矩阵几乎没有对称性（对于 n 大来说无疑是一个很好的假设，但先验有多大并不明显），我预计 8x8 是可行的，9x9 是边界性的，而 10x10 是遥不可及的。

扩展伪代码：

1. 生成一个代表 (m - 1) × (n - 1) 0-1 矩阵的每个轨道，该矩阵由行和列排列生成的组所作用，以及轨道的大小 (= (m - 1)! (n - 1)!/自同构群的大小)。也许蒂姆链接的论文的作者愿意分享他的代码；否则，请参见下文。

2. 对于每个矩阵，将条目 x 替换为 (-1)^x。添加一行和一列的 1。将其轨道大小乘以 2^(m + n - 1)。这考虑了符号变化的对称性。

3. 过滤矩阵并对剩余矩阵的轨道大小求和。您可以通过自己实现 Gram--Schmidt 来节省一些计算时间，这样当您按字典顺序尝试所有组合时，就有机会重用共享前缀的部分结果。

无同构枚举：

McKay 的模板可用于以适合深度优先搜索的方式，从 m × n 0-1 矩阵的代表生成 (m + 1) × n 0-1 矩阵的代表。对于每个 m × n 0-1 矩阵，将一个二部图与 m 个黑色顶点、n 个白色顶点以及每个 1 个条目的适当边相关联。对每个 m × n 代表执行以下操作。

1. 对于每个长度为 n 的向量，构建由代表和新向量组成的 (m + 1) x n 矩阵的图，并运行 nauty 以获得规范标签和顶点轨道。

2. 过滤掉新向量对应的顶点与编号最小的黑色顶点处于不同轨道的可能性。

3. 过滤掉具有重复规范标签的可能性。

nauty 还计算自同构群的阶。