# LU factorization of a 0-1 matrix

I have a rather naive question on LU factorization which probably should be easy to answer. Say I have a matrix with entries only from $\{0,1\}$. When can we expect to get an LU factorization of such a matrix(whenever it exists) with entries $(a)$ from integers? $(b)$ from $\{-1,0,+1\}$?

• In the current form, I don't think the question is on-topic, i.e. about theoretical computer science. – Kristoffer Arnsfelt Hansen Apr 8 '11 at 16:11
• Actually it is related to a problem for getting capacity of 1-d constrained channels! – T.... Apr 8 '11 at 18:45

Here's a 5-by-5 matrix with a non-integer LU-decomposition.

A

A =

1     1     0     1     0
1     1     1     0     0
1     0     1     1     0
1     0     0     1     1
0     1     0     1     1

[L U] = lu(A)

L =

1.0000         0         0         0         0
1.0000         0    1.0000         0         0
1.0000    1.0000         0         0         0
1.0000    1.0000   -1.0000   -0.5000    1.0000
0   -1.0000    1.0000    1.0000         0

U =

1.0000    1.0000         0    1.0000         0
0   -1.0000    1.0000         0         0
0         0    1.0000   -1.0000         0
0         0         0    2.0000    1.0000
0         0         0         0    1.5000

Your questions seems related to unimodular and totally unimodular matrices.

No. Consider the 4-by-4 matrix below.

0     1     1     1
1     0     1     1
0     0     0     1
1     1     0     1
• Indeed, as can be verified here. But is there only one LU decomposition of this matrix (apologies if this is a silly question)? – Anthony Labarre Apr 7 '11 at 14:30
• comment: Hi this actually produces integral LU matrices. LU Decomposition: L: 1.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 1.000 1.000 1.000 0.000 0.000 0.000 0.000 1.000 U: 1.000 0.000 1.000 1.000 0.000 1.000 1.000 1.000 0.000 0.000 -2.000 -1.000 0.000 0.000 0.000 1.000 Permutation matrix: 0.000 1.000 0.000 0.000 1.000 0.000 0.000 0.000 0.000 0.000 0.000 1.000 0.000 0.000 1.000 0.000 – T.... Apr 7 '11 at 16:49