计算所有子矩阵的满秩矩阵数

Question

我想计算有多少个元素为1或-1的m×n矩阵具有其所有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日：

• 李旺忠的回答很快，但对m>；n并不正确。李旺忠正在考虑如何修复。在
• Hooked的答案不适用于m>；n。在

Answer 1

你需要从数学的角度重新思考这个问题。也就是说，即使使用暴力，也有一些编程技巧可以用来加快进程（编程站点也是如此）。像不重新计算int(min(n,rowstochoose))和itertools.combinations(range(m), int(rowstochoose))这样的小技巧可以节省几个百分点——但真正的好处来自记忆。其他人也提到过，但我认为有一个完整、有效的代码示例可能会有用：

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

m,n = 4,4

rowstochoose = int(np.floor(m/2)+1)
maxnumber    = comb(m, rowstochoose, exact = True)
combo_itr    = (x for x in itertools.product([-1,1], repeat = m*n))
matrix_itr   = (np.array(x,dtype=np.int8).reshape((n,m)) for x in combo_itr)

sub_shapes = map(list,(itertools.combinations(range(m), int(rowstochoose))))
required_rank = int(min(n,rowstochoose))

memo = {}

no_found = 0
for A in matrix_itr:
    check = True
    for s in sub_shapes:
        view  = A[s].view(np.int8)
        h    = hashlib.sha1(view).hexdigest()

        if h not in memo: 
            memo[h] =  np.linalg.matrix_rank(view)

        if memo[h] != required_rank:
            check = False
            break
    if check: no_found+=1   

print no_found, 2**(m*n)

这使4x4的速度提高了近10倍-如果您愿意等待足够长的时间，您将看到更大矩阵的实质性改进。对于较大的矩阵，秩的成本按比例更昂贵，您可以在哈希运算中提前对矩阵排序：

^{pr2}$

对于4x4的情况，这会使情况稍差，但我希望5x5的情况会反过来。在