Thread Subject:

random block permutation matrix

Hi,

I just want to know if there is an easy way in matlab to randomly permute by block a matrix N of size n ? What I can think of is to create a random permutation matrix M of size m with m smaller than n. Then, create p identity Pi blocks of size pi such that sum_i pi = n/m (assuming that this n/m is an integer) and finally build the full permutation matrix through kronecker products between N and the Pis. Do you agree with this? Thanks

"pluton schmidt" wrote in message <j6j6e6$1ck$1@newscl01ah.mathworks.com>...
> Hi,
>
> Do you agree with this?

No, I can't see how Kronecker can help here.

Help RANDPERM if you don't know where to start

Bruno

> No, I can't see how Kronecker can help here.

well, it will build the blocks for the permutation (but I may be wrong there)
 
> Help RANDPERM if you don't know where to start

Thanks, I'll have a look.

"pluton schmidt" wrote in message <j6j6e6$1ck$1@newscl01ah.mathworks.com>...
> Hi,
>
> I just want to know if there is an easy way in matlab to randomly permute by block a matrix N of size n ? What I can think of is to create a random permutation matrix M of size m with m smaller than n. Then, create p identity Pi blocks of size pi such that sum_i pi = n/m (assuming that this n/m is an integer) and finally build the full permutation matrix through kronecker products between N and the Pis. Do you agree with this? Thanks

I may not understand your problem completely, but perhaps my RANDBLOCK function on the FEX is what you're looking for:

http://www.mathworks.nl/matlabcentral/fileexchange/17981-randblock

R = RANDBLOCK(M,S) randomizes the matrix M by dividing M into non-overlapping blocks of the size specified by S, and shuffling these blocks. M can be a N-D matrix.

hth
~ Jos

> I may not understand your problem completely, but perhaps my RANDBLOCK function on the FEX is what you're looking for:
>
> http://www.mathworks.nl/matlabcentral/fileexchange/17981-randblock
>
> R = RANDBLOCK(M,S) randomizes the matrix M by dividing M into non-overlapping blocks of the size specified by S, and shuffling these blocks. M can be a N-D matrix.


it sounds promising but in my mind, I would like to have blocks of random size and not prescribed size. I'll try it anyway. Thanks

"pluton schmidt" wrote in message <j6kkcm$nhk$1@newscl01ah.mathworks.com>...
> > I may not understand your problem completely, but perhaps my RANDBLOCK function on the FEX is what you're looking for:
> >
> > http://www.mathworks.nl/matlabcentral/fileexchange/17981-randblock
> >
> > R = RANDBLOCK(M,S) randomizes the matrix M by dividing M into non-overlapping blocks of the size specified by S, and shuffling these blocks. M can be a N-D matrix.
>
>
> it sounds promising but in my mind, I would like to have blocks of random size and not prescribed size. I'll try it anyway. Thanks

random sized blocks?
Can you give a small (e.g., 6x4) example?

Jos

> random sized blocks?
> Can you give a small (e.g., 6x4) example?

let's say I have a 9*9 matrix that needs permutation. First random quantity : the number of blocks that will be permuted, let's say 3. Second random quantity : the size of each block : let's say 1, 4 and 4.

The first permutation matrix will be :
[0 1 0
 0 0 1
 1 0 0];

then respective identity matrices for each block will be:
[1],
[1 0 0 0
 0 1 0 0
 0 0 1 0]
and
[1 0 0 0
 0 1 0 0
 0 0 1 0]

Finally the full permutation matrix obtained by the kronecker product of the initial permutation matrix and the respective block will yield:

[0 0 0 0 1 0 0 0 0
 0 0 0 0 0 1 0 0 0
 0 0 0 0 0 0 1 0 0
 0 0 0 0 0 0 0 1 0
 0 0 0 0 0 0 0 0 1
 1 0 0 0 0 0 0 0 0
 0 1 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 0 0
 0 0 0 1 0 0 0 0 0]

sorry, each identity matrix of size 4*4 will be:

[1 0 0 0
 0 1 0 0
 0 0 1 0
 0 0 0 1]

Also, the initial permutation matrix is also built in a random manner with the constraint that it has to be a permutation matrix.

Try this

s = [1 4 4], ; % size of each block, as in your example
p = randperm(length(s));

b = mat2cell(eye(sum(s)),s,s);
A = cell2mat(b(:,p))

% Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
>
> b = mat2cell(eye(sum(s)),s,s);

More generic random blocks can be obtained with:

c=arrayfun(@(x) rand(x,x), s, 'uniform', 0)
b = blkdiag(c{:})

% Bruno

> s = [1 4 4], ; % size of each block, as in your example
> p = randperm(length(s));
> b = mat2cell(eye(sum(s)),s,s);
> A = cell2mat(b(:,p))

looks good thanks. Except the fact that s should be random as well

"pluton schmidt" wrote in message <j6uoh3$s0o$1@newscl01ah.mathworks.com>...
> > s = [1 4 4], ; % size of each block, as in your example
> > p = randperm(length(s));
> > b = mat2cell(eye(sum(s)),s,s);
> > A = cell2mat(b(:,p))
>
> looks good thanks. Except the fact that s should be random as well

To generate random s, you could do the following

m = 9; % target sum(s)
n = 3; % number of blocks
s = diff([0 sort(floor((m-n+1)*rand(1,n-1))) m-n])+1

% Bruno

> To generate random s, you could do the following
> m = 9; % target sum(s)
> n = 3; % number of blocks
> s = diff([0 sort(floor((m-n+1)*rand(1,n-1))) m-n])+1


very good, many thanks !

by the way, how about a sparse version of the code so that full matrices
b = mat2cell(eye(sum(s)),s,s) and A = cell2mat(b(:,p)) are never built but their sparse version instead? Thanks

"pluton schmidt" wrote in message <j8krp5$npr$1@newscl01ah.mathworks.com>...
> by the way, how about a sparse version of the code so that full matrices
> b = mat2cell(eye(sum(s)),s,s) and A = cell2mat(b(:,p)) are never built but their sparse version instead? Thanks


the speye command instead of eye is already much better. Next, what would be interesting is to avoid the full mat2cell command

ok, that's what I have now and it goes much faster than before obviously.

Na=1000; % size of the vector (matrix) to be permuted
x=(1:1:Na)';
z=ones(Na,1);
n = 10; % number of blocks to be permuted
s = diff([0 sort(floor((Na-n+1)*rand(1,n-1))) Na-n])+1;
p = randperm(length(s));
b=mat2cell(x,s);
xp=cell2mat(b(p));
B = sparse(xp,x,z); % permutation matrix

% permutation of vector w
wp=B*w;
% permutation of matrix A
Ap=B*A*B';