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

9 views (last 30 days)
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]

Accepted Answer

Fangjun Jiang
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
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
  27 Comments
Maria
Maria on 16 Sep 2022
@Torsten @Fangjun Jiang I really appreciate the effort and extra time you have contributed to help me. Thank you so much.

Sign in to comment.

More Answers (1)

Torsten
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
Maria
Maria on 21 Sep 2022
Edited: Maria on 21 Sep 2022
@Torsten I'm sorry for my late reply, the code you contributed works well, I really appreciate your efforts. Thank you very much.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!