Sparse LU obstruction conjecture

A matrix is sparse when its relevant rows and columns have uniformly boundedly many nonzero entries. A sparse LU decomposition is a factorization

$$\partial=PLUQ$$

where $P$ and $Q$ are permutation matrices and $L$ and $U$ are sparse lower- and upper-triangular matrices. Sparse LU obstruction conjecture. There exist sparse matrices with no sparse LU decomposition. Moreover, with high probability, a uniformly random sparse matrix has no sparse LU decomposition. Such a decomposition would give a sparse lift with determinant $1$ and hence avoid torsion in the corresponding full-rank one-complex; the existence of sparse LU decompositions is left open.