如何从二进制矩阵中筛选出两两内积满足指定条件的列？

方法1：图论建模转化为独立集问题 #

• 把矩阵的每一列抽象为一个节点
• 若两列的内积为104（即需要排除的配对），则在对应的两个节点之间连一条边
• 问题转化为在这个图中寻找独立集：独立集中的任意两个节点之间没有边，也就意味着对应的任意两列内积不为104，恰好满足要求
• 实现细节：
  • 用邻接表存储图结构，遍历所有列对，判断内积是否为104后构建边
  • 针对69495个节点的大规模图，精确求解最大独立集属于NP难问题，可采用启发式算法（比如贪心独立集算法：每次选择度数最小的节点加入集合，再移除该节点及其所有邻居），或基于社区检测的方法快速筛选符合条件的子集

方法2：基于内积相似性的分组策略 #

• 利用内积的三个固定取值，任选一列作为基准列，计算其余所有列与它的内积，将列分为三类：
  • 类型X：与基准列内积为104的列
  • 类型Y：与基准列内积为112的列
  • 类型Z：与基准列内积为120的列
• 检查类型Y和Z内部的列对：若某类中任意两列的内积都不为104，该类本身就是符合要求的子集；若存在内积为104的列对，则对该类递归执行上述分组，直到得到满足约束的子组
• 优势：利用了矩阵列的相似性结构，计算量远小于全图遍历，适合大规模矩阵场景

方法3：贪心迭代筛选法 #

• 初始化空的结果集合S
• 遍历矩阵的每一列c：
  • 检查c与S中所有已存在列的内积，若所有内积都属于{112,120}，则将c加入S
  • 若c与S中某一列内积为104，则跳过该列
• 遍历结束后，S即为满足要求的列子集
• 优化点：可先按某一行的取值对列排序，减少重复计算；或并行检查列与S中已有列的内积，提升处理效率

方法4：基于线性代数的结构挖掘 #

• 二进制列向量的内积等价于两个列支撑集（即1的位置集合）的交集大小：设列向量为v_i、v_j，则v_i·v_j = |supp(v_i) ∩ supp(v_j)|
• 已知每个列的支撑集大小为240，结合容斥原理可推导：内积为104时交集大小为104，内积112时为112，内积120时为120
• 可将支撑集转化为511位的二进制位向量，通过位运算快速计算交集大小（即内积），大幅提升筛选速度
• 若矩阵具备组合设计（如部分平衡不完全区组设计PBIBD）的结构，可直接利用其分组规则提取符合条件的子集

内容的提问来源于stack exchange，提问作者Robin Kurtz