**You are now following this question**

- You will see updates in your followed content feed.
- You may receive emails, depending on your communication preferences.

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

9 views (last 30 days)

Show older comments

Maria
on 9 Sep 2022

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]

##### 0 Comments

### Accepted Answer

Fangjun Jiang
on 9 Sep 2022

Edited: Fangjun Jiang
on 9 Sep 2022

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

% To verify

sum(B)

sum(B,2)

##### 27 Comments

Maria
on 9 Sep 2022

Fangjun Jiang
on 9 Sep 2022

Fangjun Jiang
on 9 Sep 2022

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?

Fangjun Jiang
on 9 Sep 2022

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
on 9 Sep 2022

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
on 9 Sep 2022

Edited: Fangjun Jiang
on 9 Sep 2022

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

Torsten
on 9 Sep 2022

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
on 10 Sep 2022

@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
on 12 Sep 2022

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
on 16 Sep 2022

Edited: Fangjun Jiang
on 16 Sep 2022

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
on 16 Sep 2022

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

Fangjun Jiang
on 16 Sep 2022

Yes. Thinking of this ...

- Make sure each row is all zeros, or has at most one 1 in the entire row. That is easy to do.
- Based on the result above, apparently, some columns have more then five ones, so you want to change some of them into 0.
- Then some rows will become all-zero, even if previously there was no all-zero rows.
- 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.
- That algorithm is not provided.
- 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).
- For a square matrix, this is very unlikely to happen if the threshold value is 5.
- 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
on 16 Sep 2022

Edited: Maria
on 16 Sep 2022

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
on 16 Sep 2022

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
on 16 Sep 2022

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
on 16 Sep 2022

@Torsten yes the same procedure .

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

Torsten
on 16 Sep 2022

Edited: Torsten
on 16 Sep 2022

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
on 16 Sep 2022

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

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

Torsten
on 16 Sep 2022

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
on 16 Sep 2022

Edited: Torsten
on 16 Sep 2022

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
on 16 Sep 2022

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

Maria
on 16 Sep 2022

### More Answers (1)

Torsten
on 17 Sep 2022

Edited: Torsten
on 17 Sep 2022

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

##### 4 Comments

Torsten
on 18 Sep 2022

Edited: Torsten
on 18 Sep 2022

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
on 18 Sep 2022

Edited: Torsten
on 18 Sep 2022

%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

### See Also

### Categories

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!**An Error Occurred**

Unable to complete the action because of changes made to the page. Reload the page to see its updated state.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

You can also select a web site from the following list:

## How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

### Americas

- América Latina (Español)
- Canada (English)
- United States (English)

### Europe

- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)

- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)

### Asia Pacific

- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本Japanese (日本語)
- 한국Korean (한국어)