Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Symmetrical binary matrices: a help from an expert

Subject: Symmetrical binary matrices: a help from an expert

From: Paulo Guimaraes

Date: 27 Jan, 2011 21:27:04

Message: 1 of 16

Hi guys,

I have a silly problem i think matlab specialists will solve easily: how can I generate a symmetric binary matrix in which all rows have exactly the same number of ones? This matrix must have r(i,i)=0;

Example:

r= [0 1 1 0; 1 0 0 1; 1 0 0 1; 0 1 1 0]

Someone could help me out?

Thank so much

P.

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 27 Jan, 2011 22:42:04

Message: 2 of 16

Try this:

n = 10; % size of r
m = 6; % number of 1 by row/column


r = 1-eye(n);
p = n-m-1;
if n > 2*(m+1)
    error('cannot achieve')
end

for k=1:p
    i = 1:n;
    j = mod(2*k-i,n)+1;
    i = n*(i-1) + j;
    r(i) = 0;
end
disp(r)

% Bruno

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 27 Jan, 2011 23:30:10

Message: 3 of 16

My previous code only works for n even. I'll think more about other cases.

Bruno

Subject: Symmetrical binary matrices: a help from an expert

From: Paulo Silva

Date: 28 Jan, 2011 00:55:05

Message: 4 of 16

Here's one of the ways, it works fine for odd and even rows, just keep n small

a=[]; %initialize the output matrix
n=5; %number of rows
n1=randi([1 n-1]); %ones per rows
o=ones(1,n1); %vector with the ones
z=zeros(1,n-n1); %vector with the zeros
p=perms([o z]); %join ones and zeros in the same vector and permute them
for x=1:n
b=p(p(:,x)==0,:);%find the permuted lines with zero at the diagonal
bx=randi([1 numel(b(:,1))]); %select a random column of b
a(x,:)=b(bx,:); %save the random column to the output
end
p=[]; %p might be very big, this line saves memory big discard the saved values
a %same number of zeros per column and with zeros at the diagonal

Subject: Symmetrical binary matrices: a help from an expert

From: Paulo Silva

Date: 28 Jan, 2011 01:10:05

Message: 5 of 16

Just a few corrections

a=[]; %clear the output matrix
n=5; %number of rows
n1=randi([1 n-1]); %ones per rows
o=ones(1,n1); %vector with the ones
z=zeros(1,n-n1); %vector with the zeros
p=perms([o z]); %join ones and zeros in the same vector and permute them
for x=1:n
b=p(p(:,x)==0,:);%find the permuted lines with zero at the diagonal
bx=randi([1 numel(b(:,1))]); %select a random rows of b
a(x,:)=b(bx,:); %save the random rows to the output
end
p=[]; %clear some memory, specially useful when n is big (lots of permutations)
a %Random matrix with the same number of ones per rows and diag=0

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 28 Jan, 2011 06:21:03

Message: 6 of 16

"Paulo Silva" wrote in message <iht51d$evh$1@fred.mathworks.com>...
> Just a few corrections

It does not seem to work to me:

>
a=[]; %clear the output matrix
n=10; %number of rows
n1=5; %ones per rows

o=ones(1,n1); %vector with the ones
z=zeros(1,n-n1); %vector with the zeros
p=perms([o z]); %join ones and zeros in the same vector and permute them
for x=1:n
b=p(p(:,x)==0,:);%find the permuted lines with zero at the diagonal
bx=randi([1 numel(b(:,1))]); %select a random rows of b
a(x,:)=b(bx,:); %save the random rows to the output
end
p=[]; %clear some memory, specially useful when n is big (lots of permutations)
a %Random matrix with the same number of ones per rows and diag=0

 sum(a)

ans =

     7 7 4 5 4 6 2 7 4 4

Bruno

Subject: Symmetrical binary matrices: a help from an expert

From: Paulo Silva

Date: 28 Jan, 2011 07:04:04

Message: 7 of 16

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ihtn8f$n7j$1@fred.mathworks.com>...
> "Paulo Silva" wrote in message <iht51d$evh$1@fred.mathworks.com>...
> > Just a few corrections
>
> It does not seem to work to me:
>
> >
> a=[]; %clear the output matrix
> n=10; %number of rows
> n1=5; %ones per rows
>
> o=ones(1,n1); %vector with the ones
> z=zeros(1,n-n1); %vector with the zeros
> p=perms([o z]); %join ones and zeros in the same vector and permute them
> for x=1:n
> b=p(p(:,x)==0,:);%find the permuted lines with zero at the diagonal
> bx=randi([1 numel(b(:,1))]); %select a random rows of b
> a(x,:)=b(bx,:); %save the random rows to the output
> end
> p=[]; %clear some memory, specially useful when n is big (lots of permutations)
> a %Random matrix with the same number of ones per rows and diag=0
>
> sum(a)
>
> ans =
>
> 7 7 4 5 4 6 2 7 4 4
>
> Bruno

You are doing the sum of columns instead of rows

sum(a,2)

ans =
     5
     5
     5
     5
     5
     5
     5
     5
     5
     5

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 28 Jan, 2011 07:13:04

Message: 8 of 16


>
> You are doing the sum of columns instead of rows
>

OP requires a *symmetric* matrix.

Bruno

Subject: Symmetrical binary matrices: a help from an expert

From: Paulo Silva

Date: 28 Jan, 2011 07:30:12

Message: 9 of 16

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <ihtq9v$7m7$1@fred.mathworks.com>...
>
> >
> > You are doing the sum of columns instead of rows
> >
>
> OP requires a *symmetric* matrix.
>
> Bruno

yes he does and I forgot that requirement, only after your last message I discovered what was missing, thanks for the heads up, trying this

a1=triu(a);
a2=triu(a)';
a=a1+a2;

but now there might not be the same number of ones per row, will try to do better tomorrow.

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 28 Jan, 2011 08:14:04

Message: 10 of 16

Here is a solution for the number of one (m) even

n=9
m = 6 % m even

r = zeros(n);
for k=1:m/2
    i = 1:n;
    j = mod(i+k,n)+1;
    i1 = n*(i-1) + j;
    i2 = n*(j-1) + i;
    r(i1) = 1;
    r(i2) = 1;
end

% Bruno

The remaining case I still have to solve is m, and n are both odds.

Bruno

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 28 Jan, 2011 08:27:03

Message: 11 of 16


> The remaining case I still have to solve is m, and n are both odds.

There is no solution for odd/odd, since the total number of 1 is m*n is odd. However the symmetric requires the number to be even. SO it's impossible.

So I'm done (well almost, the case n even can be extended, but I let the extension to OP).

Bruno

Subject: Symmetrical binary matrices: a help from an expert

From: Paulo Silva

Date: 28 Jan, 2011 08:29:04

Message: 12 of 16

Here's a brute force way to find solutions

clear;clc
at=0;
nmaxat=10000;
while(1)
at=at+1
a=[]; %clear the output matrix
n=5; %number of rows
n1=2; %ones per rows
o=ones(1,n1); %vector with the ones
z=zeros(1,n-n1); %vector with the zeros
p=perms([o z]); %join ones and zeros in the same vector and permute them
for x=1:n
b=p(p(:,x)==0,:);%find the permuted lines with zero at the diagonal
bx=randi([1 numel(b(:,1))]); %select a random rows of b
a(x,:)=b(bx,:); %save the random rows to the output
end
p=[]; %clear some memory, specially useful when n is big (lots of permutations)
s1=sum(a,1);s2=sum(a,2)';
s1f=find(s1==n1)
s2f=find(s2==n1)
if(((numel(s1f)==n) & isequal(a,a') & (numel(s2f)==n)) | (at>=nmaxat))
break
else
end
end
isequal(a,a')
sum(a,1)
sum(a,2)

Subject: Symmetrical binary matrices: a help from an expert

From: Paulo Silva

Date: 28 Jan, 2011 08:42:03

Message: 13 of 16

nice code and conclusion Bruno, I leave here my brute force code with speed improvements so people can confirm your conclusions :)

clear;clc
at=0;
nmaxat=10000;
n=4; %number of rows
n1=2; %ones per rows
o=ones(1,n1); %vector with the ones
z=zeros(1,n-n1); %vector with the zeros
p=perms([o z]); %join ones and zeros in the same vector and permute them
while(1)
at=at+1;
a=[]; %clear the output matrix
for x=1:n
b=p(p(:,x)==0,:);%find the permuted lines with zero at the diagonal
bx=randi([1 numel(b(:,1))]); %select a random rows of b
a(x,:)=b(bx,:); %save the random rows to the output
end
s1=sum(a,1);
s1f=find(s1==n1);
if(((numel(s1f)==n) & isequal(a,a')) | (at>=nmaxat))
break
else
end
end
p=[]; %clear some memory, specially useful when n is big (lots of permutations)
isequal(a,a')
sum(a,1)
sum(a,2)

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 28 Jan, 2011 22:00:07

Message: 14 of 16

Here is the algorithm put together:

% Data
n = 10 % size of r
m = 5 % number of 1 by row/column

% Engine
i = 1:n;
if mod(m,2)==0 % m even
    r = zeros(n);
    for k=1:m/2
        j = mod(i+k,n)+1;
        r(n*(i-1) + j) = 1;
        r(n*(j-1) + i) = 1;
    end
elseif mod(n,2)==0 % n even
    if n <= 2*m
        r = 1-eye(n);
        % turn off existing 1
        for k=1:n-m-1
            j = mod(2*k-i,n)+1;
            r(n*(i-1) + j) = 0;
        end
    else
        r = zeros(n);
        % turn on existing 0
        for k=1:m
            j = mod(2*k-i,n)+1;
            r(n*(i-1) + j) = 1;
        end
    end
else
    error('cannot achieve')
end

disp(r)
disp(sum(r))

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 28 Jan, 2011 22:45:06

Message: 15 of 16

Just a note that if randomize matrix is needed, then add these commands at the end:

p = randperm(n);
r = r(p,p);

Bruno

Subject: Symmetrical binary matrices: a help from an expert

From: Bruno Luong

Date: 29 Jan, 2011 08:13:03

Message: 16 of 16

Here is a full vectorized code:

n = 10; % size of r
m = 5; % number of 1 by row/column

i = (1:n)';
if mod(m,2)==0 % m even
    r = zeros(n);
    k = 1:m/2;
    j = mod(bsxfun(@plus,i,k),n) + 1;
    r(bsxfun(@plus,(i-1)*n,j)) = 1;
    r(bsxfun(@plus,(j-1)*n,i)) = 1;
elseif mod(n,2)==0 % n even
    if n <= 2*m
        r = 1-eye(n);
        % turn off existing 1
        k = 1:n-m-1;
        j = mod(bsxfun(@minus,2*k,i),n) + 1;
        r(bsxfun(@plus,(i-1)*n,j)) = 0;
    else
        r = zeros(n);
        % turn on existing 0
        k = 1:m;
        j = mod(bsxfun(@minus,2*k,i),n) + 1;
        r(bsxfun(@plus,(i-1)*n,j)) = 1;
    end
else
    error('cannot achieve')
end

p = randperm(n);
r = r(p,p);

disp(r);
disp(sum(r));

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us