如何用恒定的行和列总和创建1和0的对称矩阵 [英] How to create a symmetric matrix of 1's and 0's with constant row and column sum

问题描述

• 我试图找到一个优雅的算法来创建1和0的N×N矩阵。每行和每列必须总和为Q（可自由选择）
  
• 对角线必须为0
  
• 矩阵必须是对称的。

矩阵不是随机的（然而随机和非随机解都很有趣），所以对于Q甚至简单地使每一行成为向量的循环移位。

[0 1 1 0 ... 0 0 0 ... 0 1 1]（对于Q = 4）

是一个有效的解决方案。

然而，如何为Q奇做这个？或者甚至如何为Q做到这一点，但以随机的方式？

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

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

解决方案

重新尝试构造的图像更加规范地称为无向d-正则图（其中d = Q）。通过握手定理，N和Q不能都是奇数。如果Q是偶数，则在{-Q / 2，-Q / 2 + 1，...，-1,1，...，Q / 2-1中将顶点v连接到v + k模N， Q / 2}。如果Q是奇数，那么N是偶数。像前面一样构造一个（Q-1） - 正则图，然后添加从v到v + N / 2模N的连接。链的极限分布在d-正则图上是均匀的。你从任何d-正则图开始。反复随机选取顶点v，w，x，y。每当诱导子图看起来像

  v ---- w 
 
 x ---- y ，
  

翻转至

  vw 
 | | 
 x y。 
  

I'm trying to find an elegant algorithm for creating an N x N matrix of 1's and 0's, under the restrictions:

• each row and each column must sum to Q (to be picked freely)
• the diagonal must be 0's
• the matrix must be symmetrical.

It is not strictly necessary for the matrix to be random (both random and non-random solutions are interesting, however), so for Q even, simply making each row a circular shift of the vector

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

is a valid solution.

However, how to do this for Q odd? Or how to do it for Q even, but in a random fashion?

For those curious, I'm trying to test some phenomena on abstract networks.

I apologize if this has already been answered before, but none of the questions I could find had the symmetric restriction, which seems to make it much more complicated. I don't have a proof that such a matrix always exists, but I do assume so.

解决方案

The object that you're trying to construct is known more canonically as an undirected d-regular graph (where d = Q). By the handshaking theorem, N and Q cannot both be odd. If Q is even, then connect vertex v to v + k modulo N for k in {-Q/2, -Q/2 + 1, ..., -1, 1, ..., Q/2 - 1, Q/2}. If Q is odd, then N is even. Construct a (Q - 1)-regular graph as before and then add connections from v to v + N/2 modulo N.

If you want randomness, there's a Markov chain whose limiting distribution is uniform on d-regular graphs. You start with any d-regular graph. Repeatedly pick vertices v, w, x, y at random. Whenever the induced subgraph looks like

v----w

x----y ,

flip it to

v    w
|    |
x    y .

这篇关于如何用恒定的行和列总和创建1和0的对称矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！