2
$\begingroup$

can you tell me a way (best?) to get a matrix with i=N,j=N dimensions (quadratic) according to the following rules:

variables: N , M, n

  1. the diagonal must contain zeros
  2. it must contain exactly M values
  3. the values must be integers between 1 and "n" (I guess RealInteger[{1,n}] is the best)
  4. if (i,j) cell has a non-zero value, then (j,i) must be zero

I would like to run it with N = 9 so the given answer freezes every time. Can anybody give a working solution with N = 9 with more detailed description? thank you.

$\endgroup$
4
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – user9660 Jan 6 '15 at 4:13
  • $\begingroup$ Does "the diagonal must contain zeros" mean EVERY diagonal element must be 0? Does "it must contain exactly M values" do you mean that exactly M elements in the matrix must be non-zero, or instead that M distinct values can appear in more than M elements of the matrix? When you state that "the values must be integers between 1 and 'n'" how does this relate to the different variable N? When you state "if (i,j) cell has non-zero value..." will you allow a lower-triangular matrix filled with positive values in the lower triangle? You have vaguely and incompletely stated your question. $\endgroup$ – David G. Stork Jan 6 '15 at 4:37
  • $\begingroup$ Yes, every diagonal element must be 0. And yes, the matrix should contain M non-zero element. The little 'n' alters from the 'N'. Thank you $\endgroup$ – pnz Jan 6 '15 at 8:24
  • 1
    $\begingroup$ Seems closely related to (dupe of?): mathematica.stackexchange.com/q/65088/131 $\endgroup$ – Yves Klett Jan 6 '15 at 9:18
2
$\begingroup$

The following is a brute force approach to generate all matrices with the required structure. It is not recommended for use with "large" n.

ClearAll[mF]; 
mF = With[{n = #, values = Join @@ Permutations /@ Subsets[Range[#2], {#3}], 
     positions = Join @@ (Tuples /@ 
         Subsets[{#, Reverse@#} & /@ Subsets[Range[#], {2}], {#3}])}, 
    SparseArray[#, {n, n}] & /@ (Rule @@@ Tuples[{positions, values}])] &;

Example 1: Changing your N to n, M to q, and m to m, all matrices for n=3, q=3, m=3:

 Grid@Partition[MatrixForm /@ Normal /@ mF2[3, 3, 3], 10]

enter image description here

Example 3: Five random matrices for n=5, q=4, m=3

Row[MatrixForm /@ Normal /@ RandomChoice[mF2[5, 4, 3], 5]]

enter image description here

How it works: using n=3; q=3; m=2 for illustration

Potential non-zero positions of the matrix are obtained using the following steps:

Get indices of above-diagonal positions:

Subsets[Range[n], {2}]
(* {{1, 2}, {1, 3}, {2, 3}} *)

Pair each position with its below-diagonal counterpart:

{#, Reverse@#} & /@ % 
(*  {{{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}, {{2, 3}, {3, 2}}} *)

Get all m subsets of these potential positions:

Subsets[%, {2}]
(*  {{{{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}},
     {{{1, 2}, {2, 1}}, {{2, 3}, {3, 2}}},
     {{{1, 3}, {3, 1}}, {{2, 3}, {3, 2}}}} *)

For each of the subsets above, form all tuples (picking one element from each sublist)

Tuples /@ %
(* {{{{1, 2}, {1, 3}}, {{1, 2}, {3, 1}}, {{2, 1}, {1, 3}}, {{2, 1}, {3, 1}}},
    {{{1, 2}, {2, 3}}, {{1, 2}, {3, 2}}, {{2, 1}, {2, 3}}, {{2, 1}, {3, 2}}}, 
    {{{1, 3}, {2, 3}}, {{1, 3}, {3, 2}}, {{3, 1}, {2, 3}}, {{3, 1}, {3, 2}}}} *)

Remove one level of nesting to get all potential non-zero positions:

positions =Join @@ %
(* {{{1, 2}, {1, 3}}, {{1, 2}, {3, 1}}, {{2, 1}, {1, 3}}, {{2, 1}, {3, 1}}, 
    {{1, 2}, {2, 3}}, {{1, 2}, {3, 2}}, {{2, 1}, {2, 3}}, {{2, 1}, {3, 2}},
    {{1, 3}, {2, 3}}, {{1, 3}, {3, 2}}, {{3, 1}, {2, 3}}, {{3, 1}, {3, 2}}} *)

To get the non-zero values to fill these non-zero positions, first find all m-subsets of the set of integers Range[q]:

Subsets[Range[q], {m}]
(* {{1, 2}, {1, 3}, {2, 3}} *)

Each set s in the previous list can fill the m positions Permutations[s] ways:

Permutations /@ %
(* {{{1, 2}, {2, 1}}, {{1, 3}, {3, 1}}, {{2, 3}, {3, 2}}} *) 

Remove one level of nesting to get all possible sets of non-zero values:

values = Join@@%
(* {{1, 2}, {2, 1}, {1, 3}, {3, 1}, {2, 3}, {3, 2}} *)

Form all pairs getting a set of non-zero positions from positions and a set of non-zero values from values:

Tuples[{positions, values}] 
(*  {{{{1,2},{1,3}},{1,2}},{{{1,2},{1,3}},{2,1}},{{{1,2},{1,3}},{1,3}},
      ... ,{{{3,1},{3,2}},{2,3}},{{{3,1},{3,2}},{3,2}}} *)

Associate the non-zero position set with non-zero value set using Rule for each the sublists above:

 Rule @@@ % 
 (* {{{1,2},{1,3}}->{1,2}, {{1,2},{1,3}}->{2,1}, {{1,2}, {1,3}}->{1,3},
      ... ,{{3,1},{3,2}}->{3,1}, {{3,1},{3,2}}->{2,3}, {{3,1},{3,2}}->{3,2}}  *)

Use each element of the above list as the first argument of SparseArray to form a matrix

 SparseArray[#, {n, n}] & /@ %
 (*  {SparseArray[<2>,{3,3}],SparseArray[<2>,{3,3}], ..., 
      SparseArray[<2>,{3,3}],SparseArray[<2>,{3,3}]} *)  

Organize for display using Normal, MatrixForm, Grid:

 Grid@Partition[MatrixForm /@ Normal /@ %, 10]

enter image description here

$\endgroup$
4
  • $\begingroup$ Thanks, I thought about this. By the way it seems complicated I have to study it. $\endgroup$ – pnz Jan 6 '15 at 10:38
  • $\begingroup$ Do you know any good and available literature to understand the behave of the mentioned functions? $\endgroup$ – pnz Jan 6 '15 at 11:47
  • $\begingroup$ Can you divide the written code to smaller parts to ease it's understanding? $\endgroup$ – pnz Jan 6 '15 at 13:44
  • $\begingroup$ @pnz1337, please see the updated version. $\endgroup$ – kglr Jan 7 '15 at 1:38
0
$\begingroup$

The size of the matrix which you mention, N=9, is small enough to use brute force by picking random elements in a procedural fashion.

size = 9;
numberOfElements = 35;
range = 40;
numberOfPlacedElements = 0;
matrix = ConstantArray[0, {size, size}];
While[
 numberOfPlacedElements < numberOfElements,
 pos = RandomInteger[{1, size}, 2];
 If[Equal @@ pos, Continue[]];
 If[matrix[[Sequence @@ pos]] != 0 || 
   matrix[[Sequence @@ Reverse@pos]] != 0, Continue[]];
 matrix[[Sequence @@ pos]] = RandomInteger[range];
 numberOfPlacedElements++;
 ]
matrix // MatrixForm

It can be compiled:

bruteForce = 
  Compile[{{size, _Integer}, {numberOfElements, _Integer}, {range, \
_Integer}},
   Module[{numberOfPlacedElements, 
     matrix = Table[0, {i, size}, {j, size}], pos},
    numberOfPlacedElements = 0;
    While[
     numberOfPlacedElements < numberOfElements,
     pos = RandomInteger[{1, size}, 2];
     If[First@pos == Last@pos, Continue[]];
     If[matrix[[First@pos, Last@pos]] != 0 || 
       matrix[[Last@pos, First@pos]] != 0, Continue[]];
     matrix[[First@pos, Last@pos]] = RandomInteger[range];
     numberOfPlacedElements++;
     ];
    matrix
    ]
   ];

bruteForce[9, 35, range] // MatrixForm

This method is not good for large matrices, at least not when a large percentage of the elements are supposed to be nonzero. But for matrices as small as 9x9 it might be the most straightforward way.

There are further optimizations that could be done which would make it scale better. We could keep an index of all the available positions (generated like kguler generates them) and then randomly pick positions from this list. It would then be a mix between the approach to select elements randomly and generating all possible combinations. It loses the capabilities of kguler's answer to list all solutions, but will be faster if you just want to generate one solution.

$\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.