Come creare una matrice simmetrica di 1 e 0 con costante riga e somma colonna

Question

Sto cercando di trovare un algoritmo elegante per la creazione di una matrice x N N di 1 e 0, con le restrizioni:

• ogni riga e ogni colonna devono sommarsi a Q (da selezionare liberamente)
• la diagonale deve essere 0
• la matrice deve essere simmetrica.

non è strettamente necessario per la matrice sia casuale (entrambe le soluzioni casuali e non casuali sono interessanti, però), quindi per Q, anche, semplicemente facendo ogni riga uno spostamento circolare del vettore

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

è una soluzione valida.

Tuttavia, come fare questo per Q strano? O come farlo anche per Q, ma in modo casuale?

Per chi fosse curioso, sto cercando di testare alcuni fenomeni su reti astratti.

mi scuso se questo è già stato risposto prima, ma nessuna delle domande che ho trovato avuto la restrizione simmetrica, che sembra rendere molto più complicato. Non ho una prova che una tale matrice esiste sempre, ma io presumo così.

Answer 1

L'oggetto che si sta tentando di costruire è noto più canonicamente come un grafico d-regolare non orientato (dove d = Q). Per il teorema di handshake, N e Q non possono essere entrambi dispari. Se Q è pari, quindi connetti vertice v a v + k modulo N per k in {-Q/2, -Q/2 + 1, ..., -1, 1, ..., Q/2 - 1, Q/2}. Se Q è dispari, allora N è pari. Costruisci un grafico (Q - 1) -regolare come prima e aggiungi le connessioni da v a v + N/2 modulo N.

Se vuoi casualità, c'è una catena di Markov la cui distribuzione limitante è uniforme su grafici d-regolari . Inizi con qualsiasi grafico d-regolare. Seleziona a caso i vertici v, w, x, y. Ogni volta che il sottografo indotto sembra

v----w 

x----y , 

Flip è di

v w 
| | 
x y . 

Answer 2

Si può forse sempre seguire il tuo algoritmo di spostamento circolare, quando possibile.

L'unica condizione che è necessario seguire mentre si utilizza l'algoritmo di spostamento circolare è di mantenere la natura simmetrica nella prima riga.

ie mantenendo Q 1 nella prima riga in modo che Q [0,1] a Q [0, N-1] {Assumendo 0 righe e colonne indicizzate, Q [0,0] è 0.} è simmetrico, un semplice esempio che è 110010011.

Quindi, N = 10, Q = 5, è possibile ottenere molteplici possibilità compositive quali:

0 1 0 0 1 1 1 0 0 1 
1 0 1 0 0 1 1 1 0 0 
0 1 0 1 0 0 1 1 1 0 
0 0 1 0 1 0 0 1 1 1 
1 0 0 1 0 1 0 0 1 1 
1 1 0 0 1 0 1 0 0 1 
1 1 1 0 0 1 0 1 0 0 
0 1 1 1 0 0 1 0 1 0 
0 0 1 1 1 0 0 1 0 1 
1 0 0 1 1 1 0 0 1 0 

o

0 1 1 0 0 1 0 0 1 1 
1 0 1 1 0 0 1 0 0 1 
1 1 0 1 1 0 0 1 0 0 
0 1 1 0 1 1 0 0 1 0 
0 0 1 1 0 1 1 0 0 1 
1 0 0 1 1 0 1 1 0 0 
0 1 0 0 1 1 0 1 1 0 
0 0 1 0 0 1 1 0 1 1 
1 0 0 1 0 0 1 1 0 1 
1 1 0 0 1 0 0 1 1 0 

Ma come si può vedere per N dispari (che significa anche N-1) e dispari Q ci c non ci sarà nessuna distribuzione simmetrica.. Spero che abbia aiutato.