# Linear system with Non-square LU factors

Consider the following linear system of equations: $$\textbf{A}\textbf{x} = \textbf{b}$$ Where $$\textbf{x}, \textbf{b} \in \mathbb{R}^{n}$$ and $$\textbf{A} \in \mathbb{R}^{n \times n}$$. We also have that $$\textbf{A}=\textbf{L}\textbf{U}$$ where $$\textbf{L} \in \mathbb{R}^{n \times m}$$ and $$\textbf{U} \in \mathbb{R}^{m \times n}$$ are non-square matrices ($$m > n$$). $$\textbf{L}$$ is constructed from a square lower triangular matrix $$\textbf{L}_0 \in \mathbb{R}^{m \times m}$$ by removing some of its rows, and $$\textbf{U}$$ is constructed from a square upper triangular matrix $$\textbf{U}_0 \in \mathbb{R}^{m \times m}$$ by removing some of its columns. The indices of the removed rows and columns are the same.

My questions are the following:

• If $$\textbf{A}$$ is full rank, how can I use $$\textbf{L}$$ and $$\textbf{U}$$ to solve the linear system in $$\mathcal{O}(n^2)$$?

• If $$\textbf{A}$$ is NOT full rank, how can I use $$\textbf{L}$$ and $$\textbf{U}$$ to find the least squares soluton of the system in $$\mathcal{O}(n^2)$$?

EDIT: Complexity $$\mathcal{O}(m^2)$$ is also acceptable in both cases.

• Can't you extend L and U back to square form and use standard results for LU? Btw, it looks like in L you can only drop columns (not rows as you mention) – VorKir Dec 17 '18 at 6:13