When does a Square Matrix have an LU Decomposition?
Necessary and Sufficient conditions in terms of rank inequalities are given in:
http://arxiv.org/pdf/math/0506382v1.pdf
Even though it has been a while, I hope it helps!
Main point from above mentioned article:
Matrix A (k-by-k) has LU factorization if: $$\mathsf Rank(A_{11})+k\geq Rank(\begin{bmatrix} A_{11} & A_{12} \end{bmatrix}) +Rank(\begin{bmatrix} A_{11} \\ A_{21} \end{bmatrix})$$