<p>Here's a 5-by-5 matrix with a non-integer LU-decomposition.</p>

<blockquote>
  <blockquote>
    <p>A    </p>
  </blockquote>
</blockquote>

<p>A =</p>

<pre><code> 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
</code></pre>

<blockquote>
  <blockquote>
    <p>[L U] = lu(A)</p>
  </blockquote>
</blockquote>

<p>L =</p>

<pre><code>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
</code></pre>

<p>U =</p>

<pre><code>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
</code></pre>

<p>Your questions seems related to unimodular and totally unimodular matrices.</p>

CC BY-SA 2.5
2011-04-07T17:13:45.653Z
2011-04-07T17:13:45.653Z
Anonymous
<p>No. Consider the 4-by-4 matrix below.</p>

<pre><code> 0     1     1     1
 1     0     1     1
 0     0     0     1
 1     1     0     1
</code></pre>

CC BY-SA 2.5
2011-04-07T14:30:17.397Z
Indeed, as can be verified [here](http://www.bluebit.gr/matrix-calculator/). But is there only one LU decomposition of this matrix (apologies if this is a silly question)?
Anthony Labarre
CC BY-SA 2.5
2011-04-07T16:49:11.150Z
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
Turbo
CC BY-SA 2.5
2011-04-07T12:34:16.330Z
2011-04-07T12:34:16.330Z
Anonymous
<p>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\}$?</p>

CC BY-SA 3.0
2011-04-08T16:11:15.527Z
In the current form, I don't think the question is on-topic, i.e. about theoretical computer science.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2011-04-08T18:45:11.857Z
Actually it is related to a problem for getting capacity of 1-d constrained channels!
Turbo
<linear-algebra><matrices><na.numerical-analysis>
LU factorization of a 0-1 matrix
Turbo
# LU factorization of a 0-1 matrix

(Asked by: username_0 on 2011-04-07)

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\}$?

**Tags:** linear-algebra, matrices, na.numerical-analysis
> **Comments:**
> **username_1**: In the current form, I don't think the question is on-topic, i.e. about theoretical computer science.  
> **username_0**: Actually it is related to a problem for getting capacity of 1-d constrained channels!  

---

## 2 answers

### Answer by username_2 on 2011-04-07. Score: 2 | Accepted answer

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.


---

### Answer by username_2 on 2011-04-07. Score: 3

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

> **Comments:**
> **username_3**: Indeed, as can be verified [here](http://www.bluebit.gr/matrix-calculator/). But is there only one LU decomposition of this matrix (apologies if this is a silly question)?  
> **username_0**: 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  

---

