Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

Is it possible to represent a binary( 0 and 1) matrix $A$ of size $ m \times n$ as a product of two martices $B$ of size $m \times k$ and $C$ of size $k \times n$. Various cases can also be considered here

  1. only $B$ is binary
  2. only $C$ is binary
  3. Both $B$ and $C$ is binary.

If no such $B$ and $C$ matrix exist, is there any way to find the close approximate to matrix $A$

share|improve this question
If ${\rm rank}(A) = r,$ then perform $A = LU$ decomposition, and set $B = L[1..m, 1..r], C = U[1..r, 1..n],$ where the notation $M[1..r, 1..c]$ means the first $r\times c$ minor of the matrix $M.$ – user2468 Mar 13 '12 at 17:37
1  
Are there any constraints on the sizes? E.g. there are $2^{n*m}$ possible $A$ matrices, but only $2^{m*k+k*n}$ combinations of binary $B$s and $C$s -- if $k$ is small, then the answer is definitely no. On the other hand, if $m = n = 1$, then answer is pretty obvious too. – dtldarek Mar 13 '12 at 18:09
@dtldarek No constraint on the sizes – Learner Mar 13 '12 at 18:22
@J.D Can you please explain a bit what do u mean by first $r \times c $ minor of a matrix. The minor is a determinant obtained after deleting a row and column of a square matrix. – Learner Mar 13 '12 at 18:23
@Learner Sorry I meant submatrix. The top upper left $r\times c$ submatrix. – user2468 Mar 13 '12 at 18:48
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.