# Binary matrix as a product of two matrices

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$

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