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

5 views (last 30 days)
Maria on 9 Sep 2022
Edited: Maria on 21 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]

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
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.

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
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.