algorithm - 如何创建具有常量行列总和的 1's and 0' 的对称矩阵

Question

我正在尝试寻找一种优雅的算法来创建一个由 1 和 0 组成的 N x N 矩阵，但要遵守以下限制:

• 每一行和每一列的总和必须为 Q(可自由选择)
• 对角线必须为0
• 矩阵必须是对称的。

矩阵不一定是随机的(然而，随机和非随机解都很有趣)，所以对于 Q even，只需让每一行成为向量的循环移位

[0 1 1 0 ... 0 0 0 ... 0 1 1](对于 Q=4)

是一个有效的解决方案。

但是，Q odd怎么办呢？或者如何以随机方式甚至为 Q 做到这一点？

对于那些好奇的人，我正在尝试在抽象网络上测试一些现象。

如果之前已经回答过这个问题，我深表歉意，但我能找到的所有问题都没有对称限制，这似乎使它变得更加复杂。我没有证据证明这样的矩阵总是存在，但我确实假设如此。

Answer 1

您尝试构建的对象更规范地称为无向 d-正则图(其中 d = Q)。根据握手定理，N 和 Q 不能都是奇数。如果 Q 是偶数，则将顶点 v 连接到 v + k modulo N for k in {-Q/2, -Q/2 + 1, ..., -1, 1, ..., Q/2 - 1, Q/2}。如果 Q 是奇数，则 N 是偶数。像以前一样构建一个 (Q - 1)-正则图，然后添加从 v 到 v + N/2 modulo N 的连接。

如果你想要随机性，有一个马尔可夫链，它的极限分布在 d 正则图上是均匀的。您可以从任何 d 正则图开始。重复随机选取顶点 v、w、x、y。每当诱导子图看起来像

v----w

x----y ,

将它翻转到

v    w
|    |
x    y .