如何使用恒定的行和列总和创建1和0的对称矩阵

Question

我试图在限制条件下找到一个优雅的算法来创建1和0的N×N矩阵:

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

矩阵不是严格必要的随机(随机和非随机解决方案都很有趣),因此对于Q均匀,只需使每一行成为矢量的循环移位

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

是一个有效的解决方案

但是,如何为Q奇做这个？或者如何为Q偶然做,但是以随机方式？

对于那些好奇的人,我试图在抽象网络上测试一些现象.

如果以前已经回答过这个问题我很抱歉,但我找不到任何问题都有对称限制,这似乎使它变得更加复杂.我没有证明这样的矩阵总是存在,但我确实这样认为.

Answer 1

您尝试构造的对象更典型地称为无向d-正则图(其中d = Q).通过握手定理,N和Q不能都是奇数.如果Q是偶数,则在{-Q/2,-Q/2 + 1,..., - 1,1,...,Q/2 - 1中将顶点v连接到v + k模N的k, Q/2}.如果Q是奇数,那么N是偶数.像以前一样构造一个(Q - 1) - 正规图,然后添加从v到v + N/2模N的连接.

如果你想要随机性,那么马尔可夫链的极限分布在d-正则图上是均匀的.您可以从任何d-regular图开始.随机重复选择顶点v,w,x,y.每当诱导子图看起来像

v----w

x----y ,

把它翻到

v    w
|    |
x    y .