4
$\begingroup$

I want to create all symmetric binary matrix with order up to 7. Can anybody help in creating this?

I want to obtain the subset of all symmetric matrices, with all diagonal entries being zero.

$\endgroup$
5
$\begingroup$

The following code does it for $n=3$; I'll leave it to you to ponder if doing it for $n=7$ is feasible for you.

With[{n = 3}, 
     Composition[Transpose[#] + # &, 
                 PadRight[PadLeft[TakeList[#, Range[n - 1, 1, -1]],
                                  {n - 1, n}], {n, n}] &] /@
     Tuples[{0, 1}, Binomial[n, 2]]]

results

For $n=6$, there are $32768$ such matrices, and for $n=7$ there are $2097152$. In general, there will be $2^\binom{n}{2}=2^\frac{n(n-1)}{2}$ such matrices.

$\endgroup$
  • $\begingroup$ Thank you, But it generates all binary matrix. Is there an way for obtaining symmetric matrices only with all diagonal entries zeroes? $\endgroup$ – SPJ Sep 26 at 6:41
  • $\begingroup$ Is it possible to have a direct code for this, instead of performing J.M.'s code first and then the second code, to reduce the computational time and space for larger n. $\endgroup$ – SPJ Sep 26 at 7:28
  • 1
    $\begingroup$ @chris, I appreciate it, but the OP should not have neglected to put in important conditions in the question, like the zero trace requirement. (Also the matrices are symmetric by construction, so the double Select[] was unnecessary.) $\endgroup$ – J. M.'s discontentment Sep 26 at 9:52
  • $\begingroup$ @JM your pre computation of the number of terms is better for the planet. My brute force approach was costly! $\endgroup$ – chris Sep 26 at 10:42
4
$\begingroup$

For a $n_0^2$ symmetric binary matrix with diagonal==0 there are $n=(n_0^2-n_0)/2$ independent elements. Therefore, we need to create all binary vectors of length n. Then we need to arrange them into Matrixform:

n0 = 3;
n = (n0^2 - n0)/2;
vecs = Tuples [{0, 1}, {n}];
m0 = Table[0, n0, n0];
mats = (k = 0; m = m0;
     Do[m[[i, j]] = m[[j, i]] = #[[++k]], {i, 1, n0}, {j, i + 1, n0}];
      m) & /@ vecs;
MatrixForm /@ mats

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Timing: For n0=6 it takes 0.84 sec on my machine and for n0=7 it takes already : 71.5 sec. $\endgroup$ – Daniel Huber Sep 26 at 8:58
2
$\begingroup$

This way uses FindInstance which isn't the most efficient method, but allows you to plug in constraints without too much thinking about how to generate the matrices. Increase the number of solutions (currently max 100) to get more results if you're trying $n > 3$:

matrices = With[{mtx = Array[a, {3, 3}]},
   mtx /. FindInstance[
     (And @@ 
        Map[#[[{2, 1}]] == #[[{1, 2}]] && 0 <= # <= 1 &, 
         Flatten[mtx]]) &&
      (And @@ (# == 0 & /@ Diagonal[mtx])),
     Variables[mtx],
     Integers,
     100
     ]
   ];

MatrixForm /@ matrices
| improve this answer | |
$\endgroup$
2
$\begingroup$

You could make use of an internal, undocumented function to do this.

Statistics`Library`VectorToSymmetricMatrix[#, 0, 7]& /@ Tuples[{0, 1}, 21]; // AbsoluteTiming

{3.4017, Null}

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.