I have been trying to develop a program to solve a system Ax=b for a square matrix A using LU-Decomposition. However, I realized that this decomposition does not always exist (one way to tell is if a row exchange operation is not required, then exists). However, I see from many sources that this is an excellent method in computing the solutions to Ax=b.

My question is: how often is it that one comes across a matrix that does not have an LU-decomposition? If one does encounter such a matrix, how should he handle it? Should he create a separate method such as Gaussian Elimination just in case?

Please provide me with some insight on this. Thanks in advance.

Note: I am trying to use this information to solve A^TAx=A^Tb, i.e. finding a mathematical model using least squares.