Problem 1051. Exact binary matrix factorization

Created by Paul Peeling

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 a binary-valued (only ones and zeroes) MxN matrix C, and K (where K&lt;M and K&lt;N) find a binary-valued MxK matrix A and a binary-valued KxN matrix B such that A*B equals C. e.g. for K = 2, and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[C =\n\n       1     1     1     0\n       0     0     0     0\n       0     1     0     1]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then one possible solution is</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[A =\n\n     0     1\n     0     0\n     1     0\n\nB =\n\n       0     1     0     1\n       1     1     1     0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For this problem, assume that at least one solution exists.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note that you cannot do matrix multiplication with two logical matrices in MATLAB.</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>"}]}

Solve

Solution Stats

40 Solutions
11 Solvers

Last Solution submitted on Dec 31, 2018

Last 200 Solutions

Problem Comments

3 Comments

3 Comments

@bmtran (Bryant Tran) on 24 Nov 2012

you should probably add an assert statement that checks the size of the output matrices

Khaled Hamed on 24 Nov 2012

I second @bmtran. lu wins!

Paul Peeling on 24 Nov 2012

thanks, I added the extra asserts as you suggest. the other solutions submitted so far look interesting, thanks for them!

Solution Comments

Solution 167731

1 Comment

1 Comment

Khaled Hamed on 25 Nov 2012

it's lu, again...

Solution 167480

1 Comment

1 Comment

Paul Peeling on 24 Nov 2012

very interesting observation that lu returns binary values factors for
these inputs. i must think about this further!

Problem Recent Solvers11

Problem Tags

matrix factorization

Problem 1051. Exact binary matrix factorization

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers11

Suggested Problems

More from this Author5

Problem Tags

Problem 1051. Exact binary matrix factorization

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers11

Suggested Problems

More from this Author5

Problem Tags

Players