specified matrix query

Question

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.

Answer 1

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]

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

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

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]

Answer 2

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.