我想计算有多少个元素为 1 或 -1 的 m×n 矩阵具有其所有 floor(m/2)+1×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)

是否有更好/更快的方法来做到这一点？我想对不超过 20 的 n 和 m 进行此计算，但任何重大改进都会很棒。

上下文。 我有兴趣获得 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 。

最佳答案

(现在是 n = m//2+1 的部分解决方案，以及请求的代码。)

令 k := m//2+1

这有点等同于问:“有多少个 {-1,1} 的 m 个 n 维向量集合没有大小为 min(k,n) 的线性相关集？”

对于那些矩阵，我们知道或可以假设:

• 每个向量的第一个条目是 1(如果不是，则将整数乘以 -1)。这会将计数减少 2**m。
• 列表中的所有向量都是不同的(如果不同，则具有两个相同向量的任何子矩阵都不是满秩)。这消除了很多。有 choose(2**m,n) 个不同向量的矩阵。
• 向量列表按字典顺序排序(排名不受排列的影响)。所以我们真的在考虑向量集而不是列表。这将计数减少了 m 倍! (因为我们需要独特性)。

有了这个，我们就有了 n=4，m=8 的解。只有八个不同的向量具有第一个条目为正的属性。来自 8 个不同向量的 8 个不同向量只有一种组合(排序列表)。

array([[ 1,  1,  1,  1],
       [ 1,  1,  1, -1],
       [ 1,  1, -1,  1],
       [ 1,  1, -1, -1],
       [ 1, -1,  1,  1],
       [ 1, -1,  1, -1],
       [ 1, -1, -1,  1],
       [ 1, -1, -1, -1]], dtype=int8)

此列表中的 100 个大小为 4 的组合的秩为 3。因此有 0 个矩阵具有该属性。

对于更通用的解决方案:

请注意，第一个坐标为 -1 的 2**(n-1) 向量，以及 choose(2**(n-1),m)要检查的矩阵。对于 n=8 和 m=8，有 128 个向量和 1.4297027e+12 个矩阵。这可能有助于回答“对于 i=1,...,k，有多少组合具有等级 i？”

或者，“哪种矩阵(在上述假设下)的秩低于满秩？” 我认为答案是准确的， 充分条件是“两列是彼此的倍数”。 我觉得这是真的，我对所有 4x4、5x5 和 6x6 矩阵都进行了测试。(一定搞砸了测试)因为第一列被选为齐次，并且由于所有齐次向量都是彼此的倍数，因此任何大小为 k 且具有除第一列以外的齐次列的子矩阵的秩都将小于 k。

但这不是必要条件。以下矩阵是奇异矩阵(第一加第四等于第三加第二)。

array([[ 1,  1,  1,  1,  1],
       [ 1,  1,  1,  1, -1],
       [ 1,  1, -1, -1,  1],
       [ 1,  1, -1, -1, -1],
       [ 1, -1,  1, -1,  1]], dtype=int8)

因为只有两个可能的值(-1 和 1)，所以所有 mxn 矩阵中 m>2, k := m//2+1, n = k 并且第一列 - 1 在每列中有多数成员(即至少 k 个成员相同)。所以对于 n=k，答案是 0。

对于 n<>

from numpy import unpackbits, arange, uint8, int8

#all distinct n-length vectors from -1,1 with first entry -1
def nvectors(n):
    if n > 8:
        raise ValueError #is that the right error?
    return -1 + 2 * (
        #explode binary numbers to arrays of 8 zeroes and ones
        unpackbits(arange(2**(n-1),dtype=uint8)) #unpackbits only takes uint
            .reshape((-1,8)) #unpackbits flattens, so we need to shape it to 8 bits
            [:,-n:] #only take the last n bytes
            .view(int8) #need signed
    )

矩阵生成器:

#generate all length-m matrices that are combinations of distinct n-vectors
def matrix_g(n,m):
    return (array(mat) for mat in combinations(nvectors(n),m))

以下是一个函数，用于检查长度为 maxrank 的所有子矩阵是否具有满秩。如果任何组合小于 maxrank，它就会停止，而不是检查所有组合。

rankof = np.linalg.matrix_rank
#all submatrices of at least half size have maxrank
#(we only need to check the maxrank-sized matrices)
def halfrank(matrix,maxrank):
return all(rankof(submatr) == maxrank for submatr in combinations(matrix,maxrank))

生成所有具有满秩的半矩阵的矩阵 def nicematrices(m，n): maxrank = min(m//2+1,n) 返回(matrix_g(n，m)中的matr if halfrank(matr，maxrank))

综合起来:

import numpy as np
from numpy import unpackbits, arange, uint8, int8, array
from itertools import combinations

#all distinct n-length vectors from -1,1 with first entry -1
def nvectors(n):
    if n > 8:
        raise ValueError #is that the right error?
    if n==0:
        return array([])
    return -1 + 2 * (
        #explode binary numbers to arrays of 8 zeroes and ones
        unpackbits(arange(2**(n-1),dtype=uint8)) #unpackbits only takes uint
            .reshape((-1,8)) #unpackbits flattens, so we need to shape it to 8 bits
            [:,-n:] #only take the last n bytes
            .view(int8) #need signed
    )

#generate all length-m matrices that are combinations of distinct n-vectors
def matrix_g(n,m):
    return (array(mat) for mat in combinations(nvectors(n),m))

rankof = np.linalg.matrix_rank
#all submatrices of at least half size have maxrank
#(we only need to check the maxrank-sized matrices)
def halfrank(matrix,maxrank):
    return all(rankof(submatr) == maxrank for submatr in combinations(matrix,maxrank))

#generate all matrices that have all half-matrices with full rank
def nicematrices(m,n):
    maxrank = min(m//2+1,n)
    return (matr for matr in matrix_g(n,m) if halfrank(matr,maxrank))

#returns (number of nice matrices, number of all matrices)
def count_nicematrices(m,n):
    from math import factorial
    return (len(list(nicematrices(m,n)))*factorial(m)*2**m, 2**(m*n))

for i in range(0,6):
    print (i, count_nicematrices(i,i))

count_nicematrices(5,5) 对我来说大约需要 15 秒，其中绝大部分时间由 matrix_rank 函数占用。

关于python - 计算所有子矩阵有多少矩阵具有满秩，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21280820/