http://www.mathworks.com/matlabcentral/newsreader/view_thread/310637
MATLAB Central Newsreader  special matrix construction
Feed for thread: special matrix construction
enus
©19942015 by MathWorks, Inc.
webmaster@mathworks.com
MATLAB Central Newsreader
http://blogs.law.harvard.edu/tech/rss
60
MathWorks
http://www.mathworks.com/images/membrane_icon.gif

Tue, 19 Jul 2011 15:22:09 +0000
special matrix construction
http://www.mathworks.com/matlabcentral/newsreader/view_thread/310637#845920
saeed kamelian
Dear all<br>
<br>
I want to construct a matrix with some special properties. i call this matrix G so the G matrix has the following properties<br>
1the G matrix's element are all 1 or 0<br>
2the G matrix always have bigger number of rows than columns or at least equal to the number of columns (#rows>=#columns)<br>
3sum of all of elements of G(sum of all 1's) is equal to number of rows<br>
4sum of all elements in each row of G is equal to 1<br>
5there is at least one 1 in each column of G matrix.<br>
I want to have and list all of the possible case of G matrix with that stated properties.<br>
for example if we have 4 rows and 2 columns the all possible G matrix are like below:<br>
0 1 1 0 1 0 1 0<br>
1 0 0 1 1 0 1 0<br>
1 0 1 0 0 1 1 0 <br>
1 0 1 0 1 0 0 1<br>
(1) (2) (3) (4)<br>
0 1 0 1 0 1 1 0 1 0 1 0<br>
0 1 1 0 1 0 0 1 0 1 1 0<br>
1 0 0 1 1 0 0 1 1 0 0 1<br>
1 0 1 0 0 1 1 0 0 1 0 1<br>
(5) (6) (7) (8) (9) (10)<br>
<br>
0 1 0 1 0 1 1 0 <br>
0 1 0 1 1 0 0 1<br>
0 1 1 0 0 1 0 1<br>
1 0 0 1 0 1 0 1<br>
(11) (12) (13) (14)<br>
<br>
these are all 14 possible case when number of rows is 4 and number of column is 2<br>
how can i write a code for arbitrary number of rows and columns.<br>
<br>
i think total number of possible case can be calculated from the following formula<br>
m= number of rows<br>
n= number of columns<br>
<br>
n^m  ( n * (n1)^m )<br>
<br>
m=4<br>
n=2<br>
2^4  (2*(21)^4))=14<br>
<br>
regards

Tue, 19 Jul 2011 19:51:08 +0000
Re: special matrix construction
http://www.mathworks.com/matlabcentral/newsreader/view_thread/310637#845956
Roger Stafford
"saeed kamelian" <kamelian.20@gmail.com> wrote in message <j047f1$lpi$1@newscl01ah.mathworks.com>...<br>
> ........<br>
> I want to construct a matrix with some special properties. i call this matrix G so the G matrix has the following properties<br>
> 1the G matrix's element are all 1 or 0<br>
> 2the G matrix always have bigger number of rows than columns or at least equal to the number of columns (#rows>=#columns)<br>
> 3sum of all of elements of G(sum of all 1's) is equal to number of rows<br>
> 4sum of all elements in each row of G is equal to 1<br>
> 5there is at least one 1 in each column of G matrix.<br>
> I want to have and list all of the possible case of G matrix with that stated properties.<br>
> .........<br>
         <br>
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:<br>
<br>
c(m,n) = n^m  n/1*c(m,n1)  n*(n1)/(1*2)*c(m,n2) ...<br>
 n*(n1)*(n2)/(1*2*3)*c(m,n3)  ...  n*c(m,1)<br>
<br>
where c(m,1) = 1. The coefficients of the cvalues are the binomial coefficients in (a + b)^n. This can be applied recursively to find any c(m,n).<br>
<br>
For example applying this formula recursively for m = 5 gives:<br>
<br>
c(5,1) = 1<br>
c(5,2) = 30<br>
c(5,3) = 150<br>
c(5,4) = 240<br>
c(5,5) = 120<br>
<br>
You will find that as m becomes large, these counts attain extremely large values. For example, c(15,11) = 59,056,027,430,400.<br>
<br>
Roger Stafford

Wed, 20 Jul 2011 04:21:09 +0000
Re: special matrix construction
http://www.mathworks.com/matlabcentral/newsreader/view_thread/310637#845982
saeed kamelian
"Roger Stafford" wrote in message <j04n7c$bh2$1@newscl01ah.mathworks.com>...<br>
> "saeed kamelian" <kamelian.20@gmail.com> wrote in message <j047f1$lpi$1@newscl01ah.mathworks.com>...<br>
> > ........<br>
> > I want to construct a matrix with some special properties. i call this matrix G so the G matrix has the following properties<br>
> > 1the G matrix's element are all 1 or 0<br>
> > 2the G matrix always have bigger number of rows than columns or at least equal to the number of columns (#rows>=#columns)<br>
> > 3sum of all of elements of G(sum of all 1's) is equal to number of rows<br>
> > 4sum of all elements in each row of G is equal to 1<br>
> > 5there is at least one 1 in each column of G matrix.<br>
> > I want to have and list all of the possible case of G matrix with that stated properties.<br>
> > .........<br>
>          <br>
> 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:<br>
> <br>
> c(m,n) = n^m  n/1*c(m,n1)  n*(n1)/(1*2)*c(m,n2) ...<br>
>  n*(n1)*(n2)/(1*2*3)*c(m,n3)  ...  n*c(m,1)<br>
> <br>
> where c(m,1) = 1. The coefficients of the cvalues are the binomial coefficients in (a + b)^n. This can be applied recursively to find any c(m,n).<br>
> <br>
> For example applying this formula recursively for m = 5 gives:<br>
> <br>
> c(5,1) = 1<br>
> c(5,2) = 30<br>
> c(5,3) = 150<br>
> c(5,4) = 240<br>
> c(5,5) = 120<br>
> <br>
> You will find that as m becomes large, these counts attain extremely large values. For example, c(15,11) = 59,056,027,430,400.<br>
> <br>
> Roger Stafford<br>
Dear Roger<br>
thanks a lot for correcting the formula for total number of count it's itself valuable alot.<br>
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?<br>
<br>
Regards

Wed, 20 Jul 2011 07:15:09 +0000
Re: special matrix construction
http://www.mathworks.com/matlabcentral/newsreader/view_thread/310637#845992
Roger Stafford
"saeed kamelian" <kamelian.20@gmail.com> wrote in message <j05l3l$ql1$1@newscl01ah.mathworks.com>...<br>
> thanks a lot for correcting the formula for total number of count it's itself valuable alot.<br>
> 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?<br>
         <br>
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.<br>
<br>
The first section of the code generates all possible n^m cases. The next section eliminates those with allzero 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:<br>
<br>
[3;1;2;3]<br>
<br>
which represents the matrix<br>
<br>
0 0 1<br>
1 0 0<br>
0 1 0<br>
0 0 1<br>
<br>
Each number in the column gives the column position for the single 1 in the corresponding row.<br>
<br>
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.<br>
<br>
* * * * * * *<br>
% Define the size of the matrices with m >= n<br>
m = 4; n = 3;<br>
<br>
% Generate all n^m possibilities<br>
X = 1:n;<br>
for k = 2:m<br>
X = [reshape(repmat((1:n),n^(k1),1),1,n^k);repmat(X,1,n)];<br>
end<br>
<br>
% Eliminate cases with allzero columns<br>
T = [zeros(1,size(X,2));sort(X,1);(n+1)*ones(1,size(X,2))];<br>
p = all(diff(T,1,1)<=1,1);<br>
X = X(:,p);<br>
c = size(X,2); % This is the total remaining number, c(m,n)<br>
<br>
% Display each column of X as an m by n matrix of 1's and 0's<br>
for k = 1:c<br>
Y = zeros(m,n);<br>
Y((1:m).'+m*(X(:,k)1)) = 1;<br>
for j = 1:m<br>
fprintf(' %d',Y(j,:)), fprintf('\n')<br>
end<br>
fprintf('\n\n')<br>
end<br>
* * * * * * *<br>
<br>
Roger Stafford

Wed, 20 Jul 2011 19:47:08 +0000
Re: special matrix construction
http://www.mathworks.com/matlabcentral/newsreader/view_thread/310637#846103
Roger Stafford
"Roger Stafford" wrote in message <j05v9t$l0f$1@newscl01ah.mathworks.com>...<br>
> "saeed kamelian" <kamelian.20@gmail.com> wrote in message <j05l3l$ql1<br>
> 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.<br>
> ...........<br>
          <br>
An idea occurred to me overnight on how your onezero 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.<br>
<br>
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 <= rc+1. We can call on matlab's 'choosek' rc+1 times, once for each possible d, to find all such possibilities.<br>
<br>
For each of these column 1 possibilities, in column 2 we reset r = rd and c = c1, 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 <= rc+1 and again we can use 'choosek' rc+1 times to select all possible subsets of ones for column 2 from among those left unfilled in column 1.<br>
<br>
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.<br>
<br>
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:<br>
<br>
[3;1;2;3]<br>
<br>
can be considered the equivalent of the 4 by 3 matrix of ones and zeros:<br>
<br>
0 0 1<br>
1 0 0<br>
0 1 0<br>
0 0 1<br>
<br>
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.<br>
<br>
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.<br>
<br>
Roger Stafford

Thu, 21 Jul 2011 07:58:09 +0000
Re: special matrix construction
http://www.mathworks.com/matlabcentral/newsreader/view_thread/310637#846163
saeed kamelian
Dear Roger<br>
i am really appreciate for your kindly help. you invaluable guidance really help me.<br>
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.<br>
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.<br>
<br>
best regards<br>
S. Kamelian