Problem 885. Create logical matrix with a specific row and column sums

Created by Amro

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given two numbers</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t></w:t></w:r><w:r><w:rPr><w:b/><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>n</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t></w:t></w:r><w:r><w:rPr><w:b/><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>s</w:t></w:r><w:r><w:t>, build an</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>n-by-n</w:t></w:r><w:r><w:t> logical matrix (of only zeros and ones), such that both the row sums and the column sums are all equal to</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>s</w:t></w:r><w:r><w:t>. Additionally, the main diagonal must be all zeros.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You can assume that:</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>0 &lt; s &lt; n</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Take</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>n=10</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>s=3</w:t></w:r><w:r><w:t>, here is a possible solution</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[M =\n 0 1 0 0 1 1 0 0 0 0\n 0 0 1 0 1 1 0 0 0 0\n 0 0 0 0 1 1 0 0 1 0\n 0 0 0 0 0 0 1 1 0 1\n 1 0 0 0 0 0 1 0 1 0\n 0 1 1 0 0 0 0 1 0 0\n 1 0 0 1 0 0 0 0 0 1\n 0 0 0 1 0 0 0 0 1 1\n 1 1 0 0 0 0 0 1 0 0\n 0 0 1 1 0 0 1 0 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note that the following conditions are all true:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[all(sum(M,1)==3) % column sums equal to s\nall(sum(M,2)==3) % row sums equal to s\nall(diag(M)==0) % zeros on the diagonal\nislogical(M) % logical matrix\nndims(M)==2 % 2D matrix\nall(size(M)==n) % square matrix]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Unscored bonus:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Visualize the result as a graph where</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>M</w:t></w:r><w:r><w:t> represents the adjacency matrix:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[% circular layout\nt = linspace(0, 2*pi, n+1)';\nxy = [cos(t(1:end-1)) sin(t(1:end-1))];\nsubplot(121), spy(M)\nsubplot(122), gplot(M, xy, '*-'), axis image]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Given two numbers <tt>n</tt> and <tt>s</tt>, build an <tt>n-by-n</tt> logical matrix (of only zeros and ones), such that both the row sums and the column sums are all equal to <tt>s</tt>. Additionally, the main diagonal must be all zeros.You can assume that: <tt>0 &lt; s &lt; n</tt>&nbsp;Example:Take <tt>n=10</tt> and <tt>s=3</tt>, here is a possible solution<pre class="language-matlab">M =
 0 1 0 0 1 1 0 0 0 0
 0 0 1 0 1 1 0 0 0 0
 0 0 0 0 1 1 0 0 1 0
 0 0 0 0 0 0 1 1 0 1
 1 0 0 0 0 0 1 0 1 0
 0 1 1 0 0 0 0 1 0 0
 1 0 0 1 0 0 0 0 0 1
 0 0 0 1 0 0 0 0 1 1
 1 1 0 0 0 0 0 1 0 0
 0 0 1 1 0 0 1 0 0 0
</pre>Note that the following conditions are all true:<pre class="language-matlab">all(sum(M,1)==3) % column sums equal to s
all(sum(M,2)==3) % row sums equal to s
all(diag(M)==0) % zeros on the diagonal
islogical(M) % logical matrix
ndims(M)==2 % 2D matrix
all(size(M)==n) % square matrix
</pre>&nbsp;Unscored bonus:Visualize the result as a graph where <tt>M</tt> represents the adjacency matrix:<pre class="language-matlab">% circular layout
t = linspace(0, 2*pi, n+1)';
xy = [cos(t(1:end-1)) sin(t(1:end-1))];
subplot(121), spy(M)
subplot(122), gplot(M, xy, '*-'), axis image
</pre>

Solve

Solution Stats

609 Solutions
210 Solvers

Last Solution submitted on Sep 10, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Clément E. on 30 May 2018

Any clue? Does this problem require great mathematics abilities ?

Rafael S.T. Vieira on 23 Jul 2020

Not really, imagine in the simplest case that we could use the diagonals (ignoring this constraint), what the solution would look like? A chessboard pattern would solve it, wouldn't it? Now, how can we work around the constraint?

Solution Comments

Solution 2533683

1 Comment

1 Comment

Shukri Bin Abdul Jalil on 13 Jun 2020

test suite does not have function 'intlinprog' in directory? otherwise works for all case on my matlab

Solution 2533650

1 Comment

1 Comment

Shukri Bin Abdul Jalil on 13 Jun 2020

my code works on my matlab, why doesn't it pass the test suite?

Solution 131768

3 Comments

3 Comments

Informaton on 8 Jun 2017

I never knew about gallery. Thanks!

Payam Morsali on 20 Apr 2020

could you please let me know which one of the Gallery matrixes have you used?

Asif Newaz on 27 Apr 2020

@Payam Morsali
its the circulant matrix

Problem Recent Solvers210

Problem Tags

logical matrix sum