How to keep a specific value in binary matrix with column constraint?

Hello!

i have a binary matrix A(10*10) , i want to return '1' to '0' to get a single one in each row. I'm wondering how I can do this, knowing that I can keep a '1' in different columns except the last column, i.e. the last column cannot contain a '1'.

A [1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1

0 1 1 1 1 1 1 1 1 1

0 1 1 1 1 1 1 1 1 0

0 0 1 1 1 1 1 1 1 1

0 0 0 1 1 1 1 1 1 1]

Answer 1

[Fangjun Jiang]

N=10;
A=eye(N);
B=A(:,randperm(N));% shuffle the Identity matrix randomly
RandCol=randi(N-1);
B(:,RandCol)=B(:,RandCol)+B(:,end);% move the 1 in last column randomly to the left 
B(:,end)=0

B = 10×10

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

% To verify
sum(B)

ans = 1×10

1 1 2 1 1 1 1 1 1 0

sum(B,2)

ans = 10×1

1 1 1 1 1 1 1 1 1 1

[Maria]

@Fangjun Jiang the matrix has been totally changed, i want to start from an existing matrix which is A, so no need to put eye(N), all what i need is to keep just a single '1' in each row at any position except the last column.

[Fangjun Jiang]

There are many "1"s in each row in your A matrix. How do you "keep just a single 1 in each row"? If the final matrix has just a single 1 in each row, would that effectively be the eye() matrix being shuffled? Of course, the last column is all zeros.

[Maria]

if you see matrix B above ,for example the last row there is a '1' in the first column but in the initial matrix A, i don't have it. that's why the matrix is changed

[Fangjun Jiang]

That is true. I thought it was not critical.

Okay then, any logic how to change "1" to "0" in each row?

It will be very easy to set the last column to be all zero first. Then, just randomly pick only one 1 in each row and set all others to be zero?

[Maria]

@Fangjun Jiang exactly, do you know how can i do this ?

[Fangjun Jiang]

This code should work. I changed A for the purpose of setting special cases, assume there must have at lease one 1 in the first 9 columns in each row.

%%
A =[1     0     0     0     0     0     0     0     0    1
    1     1     0     0     0     0     0     0     0     1
    1     1     1     0     0     0     0     0    0     1
    1     1     1     1     1     1     1     1     1     1
    1     1     1     1     1     1     1     1     1     1
    1     1     1     1     1     1     1     1     1     1
    0     1     1     1     1     1     1     1     1     1
    0     1     1     1     1     1     1     1     1     0
    0     0     1     1     1     1     1     1     1     1
    0     0     0     1     1     1     1     1     1     1];
B=zeros(size(A));
for k=1:size(A,1)
    index=find(A(k,1:end-1));
    select=randperm(length(index),1);
    B(k,index(select))=1;
end
sum(B)

ans = 1×10

3 1 2 1 0 1 0 0 2 0

sum(B,2)

ans = 10×1

1 1 1 1 1 1 1 1 1 1

[Maria]

@Fangjun Jiang

i get this error : Error using randperm

K must be less than or equal to N.

Error in Test1 (line 338)

select=randperm(length(index),1);

i don't use N in my code

[Fangjun Jiang]

That is when you have a row where column 1 to 9 are all zeros.

I guess that is still valid. You need to change 1 to 0. If all zero, then do nothing. update below

B=zeros(size(A));
for k=1:size(A,1)
    index=find(A(k,1:end-1));
    if isempty(index),continue;end
    select=randperm(length(index),1);
    B(k,index(select))=1;
end

[Maria]

it's okay, it works now, thank you very much!

[Torsten]

So the number of 1's in each column can be arbitrary ?

A =[1     1     1     1     1     1     1     1     1    1
     1     1     1     1     1     1     1     1     1     1
     1     1     1     1     1     1     1     1     1     1
     1     1     1     1     1     1     1     1     1     1
     1     1     1     1     1     1     1     1     1     1
     1     1     1     1     1     1     1     1     1     1
     0     1     1     1     1     1     1     1     1     1
     0     1     1     1     1     1     1     1     1     0
     0     0     1     1     1     1     1     1     1     1
     0     0     0     1     1     1     1     1     1     1];
B=zeros(size(A));
for k=1:size(A,1)
    index=find(A(k,1:end-1));
    select=randperm(length(index),1);
    B(k,index(select))=1;
end
B

B = 10×10

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

[Maria]

@Torsten thank you !

@Fangjun Jiang @Torsten can i add a new condition to the code above in order to select arbitrary '1' except the last '1' in each row because it's may the last "1" doesn't exist in the last column.

[Fangjun Jiang]

B=zeros(size(A));
for k=1:size(A,1)
    index=find(A(k,:));
    if isempty(index),continue;end
    select=randperm(length(index),1);
    B(k,index(select))=1;
end

[Fangjun Jiang]

It follows a similar technique as above. Here you go:

%%
A=ones(50,10); % just an example data

%%
B=zeros(size(A));
% First phase, loop through each row, find all existing 1s, randomly pick
% one, set all others to zero
for k=1:size(A,1)
    index=find(A(k,:));
    if isempty(index),continue;end
    select=randperm(length(index),1);
    B(k,index(select))=1;
end
sum(B)

ans = 1×10

3 8 4 5 8 6 3 3 5 5

%sum(B,2)

%%
C=zeros(size(B));
% Second phase, loop through each column, find all existing 1s, 
% If less than or equal to 5, do nothing
% If more than 5, randomly pick five, set all others to zero
for k=1:size(B,2)
    index=find(B(:,k));
    if length(index)<=5
        C(:,k)=B(:,k);
        continue;
    end
    select=randperm(length(index),5);
    C(index(select),k)=1;
end
sum(C)

ans = 1×10

3 5 4 5 5 5 3 3 5 5

%sum(C,2)
%sum(C,2)

[Torsten]

@Fangjun Jiang

You might delete '1's in the second phase such that some rows become zero rows, don't you ?

[Maria]

@Fangjun Jiang thank you for your help! but as @Torsten mentioned i get zero in some rows

[Fangjun Jiang]

Yes. Thinking of this ...

1. Make sure each row is all zeros, or has at most one 1 in the entire row. That is easy to do.
2. Based on the result above, apparently, some columns have more then five ones, so you want to change some of them into 0.
3. Then some rows will become all-zero, even if previously there was no all-zero rows.
4. It is possible that in above step 1, instead of randomly pick one 1, there is an algorithm to pick them so the distribution of 1s is evenly distributed between columns.
5. That algorithm is not provided.
6. For a matrix that has more rows than columns, the all-zero rows have to happen, depending on the number of rows and the threshold value (5 in the example above).
7. For a square matrix, this is very unlikely to happen if the threshold value is 5.
8. For a square matrix, it is possible during the phase one (loop through rows), that all the previously used index numbers are removed. In that case, if A starts to be ones(10), then the end result C would be a shuffled eye(10).

[Maria]

each row should contain only one '1'.

the distribution of '1's is arbitrary, I don't have an algorithm to follow, I want to choose such a '1' in each row but the condition is in each column there are at most five "1".

i'm wondering how to do that , if there is an algorithm of selecting '1' you can suggest me

[Torsten]

And the procedure should be the same as before:

You have a binary matrix. For each row, you determine the last column with '1' as entry.

Then for each row, you find the columns < the last column with '1' as entry, choose arbitrarily one such column and write a '1' at this position of a matrix N which was initialized as 0-matrix.

Finally, the matrix N should not contain more than a predefined number of '1''s in each column.

?

[Fangjun Jiang]

Please don't delete your comments. Otherwise, the thread doesn't make sense.

What is the size of your matrix A? Is it always square?

[Maria]

@Torsten yes the same procedure .

@Fangjun Jiang no above is an example of square matrix but i have the case of (100*60)

[Torsten]

Say A is an (mxn) binary matrix.

First remove the rows of A that contain only one '1' (they will become zero rows in B).

For the resulting matrix A, switch the last '1' in each row to a '0'.

Then solve the following optimization problem using "intlinprog" with the elements of B being the unknowns:

max: sum(sum((A-B))
s.c.
sum_{j=1}^{j=n} b_ij = 1 for 1 <= i <= m
sum_{i=1}^{i=m} b_ij <= 5 (or whatever you chose as maximum number of 1's per column) for 1 <= j <= n
0 <= b_ij <= 1
b_ij integer

If the value of the objective function after optimization is nnz(A)-m, you succeeded and the problem was feasible. Else, no solution exists.

[Maria]

First remove the rows of A that contain only one '1'

but all rows contain more than "1" in A.

[Torsten]

You didn't write this anywhere - so I treated the case that there can be rows with only one '1'.

If this is not the case, skip the line

First remove the rows of A that contain only one '1' (they will become zero rows in B).

in my comment.

[Fangjun Jiang]

Okay, this is getting more and more into your actual work. I will provide this as the last answer.

%%
N_row=100;
N_col=60;
A=ones(N_row,N_col); % just an example data
%%
B=zeros(N_row,N_col);
ColSumMax=5;
% First phase, loop through each row, find all existing 1s, randomly pick
% one, set all others to zero
for k=1:size(A,1)
    index=find(A(k,:));
    if isempty(index),continue;end
    
    % comment out this part of the code to see the difference
    % check if the sum of any column already exceeds 5, if Yes, remove the
    % column number from the index so 1 won't be allocated to this column
    ColumnsMaxedOut=find(sum(B(1:k,:),1)>ColSumMax);
    if ~isempty(ColumnsMaxedOut)
        index=setdiff(index,ColumnsMaxedOut);
    end

    % need to do this check again
    if isempty(index),continue;end
    
    select=randperm(length(index),1);
    B(k,index(select))=1;
end
check=sum(B)
any(check>5)

[Maria]

My apologies! I can't figure it out since I don't know how to solve the optimization problems,

I write the code as you mentioned, errors are displayed and even I did not find the result

[Torsten]

This is not done within 5 minutes.

You will have to invest some time and see how to call "intlinprog" for the problem I wrote down.

I hope you understand that this is more than I'm willing to do for you.

[Maria]

@Torsten @Fangjun Jiang I really appreciate the effort and extra time you have contributed to help me. Thank you so much.

Answer 2

[Torsten]

@Maria

Your last question was quite interesting - so I invested some time ...

If A becomes larger, you will have to work with sparse inputs to intlinprog.

%rng('default')
% n = 100;  % number of rows of A
% m = 60;   % number of columns of A
n = 200;   % number of rows of A
m = 120;    % number of columns of A
bound_ones = 5;   % bound for column sums of B
A = randi([0 1],n,m);    % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
  display('Matrix A inappropriate.');
  return
end
s = nnz(A);
%
% Objective function
% max: sum_ij cij = sum_ij (aij - bij) 
% is equivalent to
% min: -sum_ij cij = -sum_ij (aij - bij)
f = [zeros(n*m,1);-ones(n*m,1)];
%f = zeros(2*n*m,1);
%
% Equality constraints
% cij = aij - bij
Aeq1 = zeros(n*m,2*n*m);
beq1 = zeros(n*m,1);
counter = 0;
for i = 1:n
    for j = 1:m
        counter = counter + 1;
        Aeq1(counter,counter) = 1.0;
        Aeq1(counter,counter+n*m) = 1.0;
        beq1(counter) = A(i,j);
    end
end 
%sum_j bij = 1 (1 <= i <= n)
Aeq2 = zeros(n,2*n*m);
beq2 = zeros(n,1);
for i = 1:n
    Aeq2(i,(i-1)*m+1:i*m) = 1.0;
    beq2(i) = 1.0;
end
%Concatenate equality constraints
Aeq = [Aeq1;Aeq2];
beq = [beq1;beq2];
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
Aineq = zeros(m,2*n*m);
bineq = zeros(m,1);
for j = 1:m
    Aineq(j,j:m:(n-1)*m+j) = 1.0;
    bineq(j) = bound_ones;
end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= bij <= 1 and cij = aij - bij >= 0
lb = zeros(2*n*m,1);
ub = [ones(n*m,1);Inf*ones(n*m,1)];
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);

LP:                Optimal objective value is -11707.000000.                                        


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).

%
% s + fval should equal n if x is a solution
n

n = 200

s + fval

ans = 200

if exitflag == 1
  B = x(1:n*m);
  B = reshape(B,m,n).';
  C = x(n*m+1:2*n*m);
  C = reshape(C,m,n).';
  % Check constraints
  any(C~=A-B,'All')
  any(C<0,'All')
  any((0>B)|(B>1),'All')
  any(sum(B,2)~=1)
  any(sum(B,1)>bound_ones)  
else
  display('Matrix B does not exist')
end

ans = logical
   0

ans = logical
   0

ans = logical
   0

ans = logical
   0

ans = logical
   0

B

B = 200×120

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

[Maria]

@Torsten i'm trying to install new version of MATLAB to get optimization toolbox. Thank you so much for your effort,many thanks.

[Torsten]

Here is an easier version with less optimization variables:

%rng('default')
% n = 100;  % number of rows of A
% m = 60;   % number of columns of A
n = 1000;   % number of rows of A
m = 1000;    % number of columns of A
bound_ones = 5;   % bound for column sums of B
A = randi([0 1],n,m);    % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
    display('Matrix A inappropriate.');
    return
end
%
% Objective function
% min: sum_ij bij 
f = ones(n*m,1);
% Alternatively: 
% Only search for feasible point where objective doesn't matter
%f = zeros(n*m,1);
%
% Equality constraints
%sum_j bij = 1 (1 <= i <= n)
Aeq = zeros(n,n*m);
beq = zeros(n,1);
for i = 1:n
    Aeq(i,(i-1)*m+1:i*m) = 1.0;
    beq(i) = 1.0;
end
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
Aineq = zeros(m,n*m);
bineq = zeros(m,1);
for j = 1:m
    Aineq(j,j:m:(n-1)*m+j) = 1.0;
    bineq(j) = bound_ones;
end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= b_ij <= a_ij 
lb = zeros(n*m,1);
ub = reshape(A.',[],1);
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);

LP:                Optimal objective value is 1000.000000.                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).

%
% fval should equal n if x is a solution
n

n = 1000

fval

fval = 1000

if exitflag == 1
    B = reshape(x,m,n).';
    % Check constraints
    any(B>A,'All')
    any((B<0)|(B>1),'All')
    any(sum(B,2)~=1)
    any(sum(B,1)>bound_ones)  
else
    display('Matrix B does not exist')
end

ans = logical
   0

ans = logical
   0

ans = logical
   0

ans = logical
   0

B

B = 1000×1000

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[Torsten]

%rng('default')
% n = 100;  % number of rows of A
% m = 60;   % number of columns of A
n = 1500;   % number of rows of A
m = 1000;    % number of columns of A
bound_ones = 5;   % bound for column sums of B
A = randi([0 1],n,m);    % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
    display('Matrix A inappropriate.');
    return
end
%
% Objective function
% min: sum_ij bij 
f = ones(n*m,1);
% Alternatively: 
% Only search for feasible point (objective doesn't matter)
%f = zeros(n*m,1);
%
% Equality constraints
%sum_j bij = 1 (1 <= i <= n)
ir = zeros(n*m,1);
ic = zeros(n*m,1);
v = zeros(n*m,1);
for i = 1:n
  ir((i-1)*m+1:i*m) = i;
  ic((i-1)*m+1:i*m) = (i-1)*m+1:i*m;
  v((i-1)*m+1:i*m) = 1.0;
end
Aeq = sparse(ir,ic,v,n,n*m);
beq = ones(n,1);
%Aeq = zeros(n,n*m);
%beq = zeros(n,1);
%for i = 1:n
%    Aeq(i,(i-1)*m+1:i*m) = 1.0;
%    beq(i) = 1.0;
%end
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
ir = zeros(n*m,1);
ic = zeros(n*m,1);
v = zeros(n*m,1);
for j = 1:m
  ir(j:m:(n-1)*m+j) = j;
  ic(j:m:(n-1)*m+j) = j:m:(n-1)*m+j;
  v(j:m:(n-1)*m+j) = 1.0;
end
Aineq = sparse(ir,ic,v,m,n*m);
bineq = bound_ones*ones(m,1);
%Aineq = zeros(m,n*m);
%bineq = zeros(m,1);
%for j = 1:m
%    Aineq(j,j:m:(n-1)*m+j) = 1.0;
%    bineq(j) = bound_ones;
%end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= b_ij <= a_ij 
lb = zeros(n*m,1);
ub = reshape(A.',[],1);
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);

LP:                Optimal objective value is 1500.000000.                                          


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer
within tolerance, options.IntegerTolerance = 1e-05 (the default value).

%
% fval should equal n if x is a solution
n

n = 1500

fval

fval = 1500

if exitflag == 1
    B = reshape(x,m,n).';
    % Check constraints
    any(B>A,'All')
    any((B<0)|(B>1),'All')
    any(sum(B,2)~=1)
    any(sum(B,1)>bound_ones)  
else
    display('Matrix B does not exist')
end

ans = logical
   0

ans = logical
   0

ans = logical
   0

ans = logical
   0

B

B = 1500×1000

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[Maria]

@Torsten I'm sorry for my late reply, the code you contributed works well, I really appreciate your efforts. Thank you very much.