Thread Subject:

special matrix construction

Dear all

I want to construct a matrix with some special properties. i call this matrix G so the G matrix has the following properties
1-the G matrix's element are all 1 or 0
2-the G matrix always have bigger number of rows than columns or at least equal to the number of columns (#rows>=#columns)
3-sum of all of elements of G(sum of all 1's) is equal to number of rows
4-sum of all elements in each row of G is equal to 1
5-there is at least one 1 in each column of G matrix.
I want to have and list all of the possible case of G matrix with that stated properties.
for example if we have 4 rows and 2 columns the all possible G matrix are like below:
0 1 1 0 1 0 1 0
1 0 0 1 1 0 1 0
1 0 1 0 0 1 1 0
1 0 1 0 1 0 0 1
(1) (2) (3) (4)
0 1 0 1 0 1 1 0 1 0 1 0
0 1 1 0 1 0 0 1 0 1 1 0
1 0 0 1 1 0 0 1 1 0 0 1
1 0 1 0 0 1 1 0 0 1 0 1
(5) (6) (7) (8) (9) (10)

0 1 0 1 0 1 1 0
0 1 0 1 1 0 0 1
0 1 1 0 0 1 0 1
1 0 0 1 0 1 0 1
(11) (12) (13) (14)

these are all 14 possible case when number of rows is 4 and number of column is 2
how can i write a code for arbitrary number of rows and columns.

i think total number of possible case can be calculated from the following formula
m= number of rows
n= number of columns

n^m - ( n * (n-1)^m )

m=4
n=2
2^4 - (2*(2-1)^4))=14

regards

"saeed kamelian" <kamelian.20@gmail.com> wrote in message <j047f1$lpi$1@newscl01ah.mathworks.com>...
> ........
> I want to construct a matrix with some special properties. i call this matrix G so the G matrix has the following properties
> 1-the G matrix's element are all 1 or 0
> 2-the G matrix always have bigger number of rows than columns or at least equal to the number of columns (#rows>=#columns)
> 3-sum of all of elements of G(sum of all 1's) is equal to number of rows
> 4-sum of all elements in each row of G is equal to 1
> 5-there is at least one 1 in each column of G matrix.
> I want to have and list all of the possible case of G matrix with that stated properties.
> .........
- - - - - - - - - -
  I haven't figured out a general way to construct your matrix (except for a brute force method that would generate all n^m possibilities and then remove the numerous invalid ones.) However I have determined that your formula for the total count of possibilities only holds valid for two columns. Here is a general formula for finding the count. Let c(m,n) be the count for m rows and n columns. Then this must hold:

 c(m,n) = n^m - n/1*c(m,n-1) - n*(n-1)/(1*2)*c(m,n-2) ...
          - n*(n-1)*(n-2)/(1*2*3)*c(m,n-3) - ... - n*c(m,1)

where c(m,1) = 1. The coefficients of the c-values are the binomial coefficients in (a + b)^n. This can be applied recursively to find any c(m,n).

  For example applying this formula recursively for m = 5 gives:

 c(5,1) = 1
 c(5,2) = 30
 c(5,3) = 150
 c(5,4) = 240
 c(5,5) = 120

  You will find that as m becomes large, these counts attain extremely large values. For example, c(15,11) = 59,056,027,430,400.

Roger Stafford

"Roger Stafford" wrote in message <j04n7c$bh2$1@newscl01ah.mathworks.com>...
> "saeed kamelian" <kamelian.20@gmail.com> wrote in message <j047f1$lpi$1@newscl01ah.mathworks.com>...
> > ........
> > I want to construct a matrix with some special properties. i call this matrix G so the G matrix has the following properties
> > 1-the G matrix's element are all 1 or 0
> > 2-the G matrix always have bigger number of rows than columns or at least equal to the number of columns (#rows>=#columns)
> > 3-sum of all of elements of G(sum of all 1's) is equal to number of rows
> > 4-sum of all elements in each row of G is equal to 1
> > 5-there is at least one 1 in each column of G matrix.
> > I want to have and list all of the possible case of G matrix with that stated properties.
> > .........
> - - - - - - - - - -
> I haven't figured out a general way to construct your matrix (except for a brute force method that would generate all n^m possibilities and then remove the numerous invalid ones.) However I have determined that your formula for the total count of possibilities only holds valid for two columns. Here is a general formula for finding the count. Let c(m,n) be the count for m rows and n columns. Then this must hold:
>
> c(m,n) = n^m - n/1*c(m,n-1) - n*(n-1)/(1*2)*c(m,n-2) ...
> - n*(n-1)*(n-2)/(1*2*3)*c(m,n-3) - ... - n*c(m,1)
>
> where c(m,1) = 1. The coefficients of the c-values are the binomial coefficients in (a + b)^n. This can be applied recursively to find any c(m,n).
>
> For example applying this formula recursively for m = 5 gives:
>
> c(5,1) = 1
> c(5,2) = 30
> c(5,3) = 150
> c(5,4) = 240
> c(5,5) = 120
>
> You will find that as m becomes large, these counts attain extremely large values. For example, c(15,11) = 59,056,027,430,400.
>
> Roger Stafford
Dear Roger
thanks a lot for correcting the formula for total number of count it's itself valuable alot.
but one more question is that how i could construct the all n^m possible choise. i have some ideas but they are not generel for constructing all n^m possible choise for arbitry m and n. is there any general way?

Regards

"saeed kamelian" <kamelian.20@gmail.com> wrote in message <j05l3l$ql1$1@newscl01ah.mathworks.com>...
> thanks a lot for correcting the formula for total number of count it's itself valuable alot.
> but one more question is that how i could construct the all n^m possible choise. i have some ideas but they are not generel for constructing all n^m possible choise for arbitry m and n. is there any general way?
- - - - - - - - - -
  I was unable to think of a good way of generating your matrices, other than the brute force method I mentioned earlier. I give the brute force method in the code below.

  The first section of the code generates all possible n^m cases. The next section eliminates those with all-zero columns, which unfortunately will generally be in the majority. However, instead of creating different m by n matrices, a single array X is generated in which each column represents one of the possible m by n matrices. For example with m = 4 and n = 3, one of the columns of X will be:

 [3;1;2;3]

which represents the matrix

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

Each number in the column gives the column position for the single 1 in the corresponding row.

  The last section (which I am sure you will want to change for your own purposes) converts each of the columns of X into the corresponding m by n matrix in Y and displays it as a matrix.

* * * * * * *
% Define the size of the matrices with m >= n
m = 4; n = 3;

% Generate all n^m possibilities
X = 1:n;
for k = 2:m
 X = [reshape(repmat((1:n),n^(k-1),1),1,n^k);repmat(X,1,n)];
end

% Eliminate cases with all-zero columns
T = [zeros(1,size(X,2));sort(X,1);(n+1)*ones(1,size(X,2))];
p = all(diff(T,1,1)<=1,1);
X = X(:,p);
c = size(X,2); % This is the total remaining number, c(m,n)

% Display each column of X as an m by n matrix of 1's and 0's
for k = 1:c
 Y = zeros(m,n);
 Y((1:m).'+m*(X(:,k)-1)) = 1;
 for j = 1:m
  fprintf(' %d',Y(j,:)), fprintf('\n')
 end
 fprintf('\n\n')
end
* * * * * * *

Roger Stafford

"Roger Stafford" wrote in message <j05v9t$l0f$1@newscl01ah.mathworks.com>...
> "saeed kamelian" <kamelian.20@gmail.com> wrote in message <j05l3l$ql1
> I was unable to think of a good way of generating your matrices, other than the brute force method I mentioned earlier. I give the brute force method in the code below.
> ...........
- - - - - - - - - - -
  An idea occurred to me overnight on how your one-zero matrices can be generated without the necessity of creating too many and having to discard some. I have neither the time nor the energy - I claim old age as an alibi - to work out the implementation for this algorithm, so I will give only a very brief description of it here. Hopefully you (or someone else) can translate it to code if the idea seems worthwhile.

  Given m and n, we start at column 1 of the m by n matrix. Call r = m and c = n. Column 1 can have any subset of d ones where 1 <= d <= r-c+1. We can call on matlab's 'choosek' r-c+1 times, once for each possible d, to find all such possibilities.

  For each of these column 1 possibilities, in column 2 we reset r = r-d and c = c-1, since these are now the number of rows and columns left to be dealt with. Again, for the next d we must have 1 <= d <= r-c+1 and again we can use 'choosek' r-c+1 times to select all possible subsets of ones for column 2 from among those left unfilled in column 1.

  I envision a recursive process which continues with this procedure until reaching c = 1 at which point there remains only one choice available, namely that all remaining empty rows in the last column must be filled with ones.

  It should be noted that all the above computation could actually be carried out with respect to equivalent single columns of column numbers rather than m by n matrices of ones and zeros. For example, as I explained earlier, for m = 4 and c = 3, the column vector:

  [3;1;2;3]

can be considered the equivalent of the 4 by 3 matrix of ones and zeros:

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

  The above is certainly a bare bones description, but this method would indeed choose every possible solution given the constraints you have placed on the matrices, and with no extraneous matrices having to be subsequently rejected.

  It is likely that recursive execution of such an algorithm might be comparatively slow because of its complexity, but it does have the advantage that the memory used would be kept at a minimum and that no time be wasted on creating matrices which must eventually be discarded. That might be important if you had values of m and n in mind where n^m becomes exceedingly large and where the vast majority must be discarded.

Roger Stafford

Dear Roger
i am really appreciate for your kindly help. you invaluable guidance really help me.
i test the Brute Force algorithm in my functional code the result is not satisfiable. in such a code with lots of optimization loop time saving is really important.
but your new Idea maybe a lot useful. i schedule to construct he code of this algorithms. i hope i can use your steerage in future too.

best regards
S. Kamelian