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>

Given two numbers *|n|* and *|s|*, build an |n-by-n| logical matrix (of only zeros and ones), such that both the row sums and the column sums are all equal to |s|. Additionally, the main diagonal must be all zeros.

You can assume that: |0 < s < n|

&nbsp;

*Example:*

Take |n=10| and |s=3|, here is a possible solution

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

Note that the following conditions are all true:

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

&nbsp;

*Unscored bonus:*

Visualize the result as a graph where |M| represents the adjacency matrix:

% 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

Solve

Solution Stats

1219 Solutions
290 Solvers

Last Solution submitted on Jun 04, 2023

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

Show comments

Problem Recent Solvers290

Problem Tags

Community Treasure Hunt

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

Start Hunting!