As @Julien pointed out, every square matrix admits a $PLU$ decomposition, where $P$ is a permutation matrix. We have: $A = P \cdot L \cdot U$, such that:
$A=\begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 0\\0 & 0 & 1 & 0\\0 & 0 & 0 & 1\\0 & 1 & 0 & 0 \end{bmatrix} \cdot \begin{bmatrix} 1 & 0 & 0 & 0\\1 & 1 & 0 & 0\\2 & 1 & 1 & 0\\5 & \dfrac{4}{3} & \dfrac{5}{3} & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 & 4\\0 & -3 & -1 & -1\\0 & 0 & -4 & -5\\0 & 0 & 0 & -\dfrac{7}{3} \end{bmatrix}$
You could try manually cranking this one to find its $LU$ factorization. We want:
$L \cdot U = \begin{bmatrix} 1 & 0 & 0 & 0\\l_{21} & 1 & 0 & 0\\l_{31} & l_{32} & 1 & 0\\l_{41} & l_{42} & l_{43} & 1 \end{bmatrix} \cdot \begin{bmatrix} u_{11} & u_{12} & u_{13} & u_{14}\\0 & u_{22} &u_{23} & u_{24}\\0 & 0 & u_{33} & u_{34}\\0 & 0 & 0 & u_{44} \end{bmatrix} = \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}$
We start off by solving the first row, so we get:
$$u_{11} = 1, u_{12} = 2, u_{13} = 3, u_{14} = 4$$
The portion of the multiplication that determines the remaining entries in the first column of $A$ yields:
$$l_{21}u_{11} = 5 \rightarrow l_{21} = 5$$
$$l_{31}u_{11} = 1 \rightarrow l_{31} = 1$$
$$l_{11}u_{11} = 2 \rightarrow l_{41} = 2$$
At this point rewrite all the variables you solved for and then continue the process and see if you can solve the remaining variables. Of course it is easy to check the result if you can solve all of the equations.
So, we currently have:
$L \cdot U = \begin{bmatrix} 1 & 0 & 0 & 0\\5 & 1 & 0 & 0\\1 & l_{32} & 1 & 0\\2 & l_{42} & l_{43} & 1 \end{bmatrix} \cdot \begin{bmatrix} 1 & 2 & 3 & 4\\0 & u_{22} &u_{23} & u_{24}\\0 & 0 & u_{33} & u_{34}\\0 & 0 & 0 & u_{44} \end{bmatrix} = \begin{bmatrix}1 & 2 & 3 & 4 \\5 & 6 & 7 & 8\\1 & -1 & 2 & 3 \\2 & 1 & 1 &2 \end{bmatrix}$
Try solving for $u_{22},u_{23}, u_{24}$, and then $l_{32}, l_{42}$ and continue this process.
Best Answer
The answer to your question is yes. A permutation matrix is in fact a product of permutation matrices associated to transpositions, which means a matrix obtained from the identity matrix by interchanging two rows. Reduce the problem to this case and notice that this case can be easily deduced from the case of the $2\times 2$ matrix $$\left(\begin{array}10 & 1 \\ 1 & 0\end{array}\right).$$ This matrix can be transformed into the identity matrix by using the following elementary transformations (which correspond to triangular matrices): add the second row to the first, substract the first column from the second, substract the first row from the second, and last multiply the second row by $-1$.
Moreover, in the paper of Nagarajan et al., Products of three triangular matrices, Linear Algebra and its Applications, 292(1999), 61-71 it is proved that any matrix $n\times n$ over a field is a product of at most three triangular matrices.