# Show that partial pivoting leads to an $LU$ decomposition of $PA$.

Exercise: show that for every non-singular matrix $A$, partial pivoting leads to an $LU$ decomposition of $PA$ so: $PA = LU$.

I have the following theorems I can use:

Theorem 1: Assume that the coefficient matrix $A\in\mathbb{R}^{n\times n}$ of the linear system $Au = f$ is non-singular and that it can be brought to its upper triangular form $U$ using $n-1$ row operations without scaling and without interchanges in such a way that pivot elements $a_{k,k}^{(k-1)}$ for $k = 1,...,n-1$ are non-zero. Then the $n-1$ Gaussian transformation $M_k$ for $k=1, ..., n-1$ exist such that $$\begin{split} M_{n-1}M_{n-2}...M_1A = U\Leftrightarrow A &= (M_{n-1}...M_1)^{-1}U\\ \Leftrightarrow A &= LU \end{split}$$

and

Theorem 2: If Gaussian elimination with partial pivoting is used to compute the upper triangularization $$M_{n-1}P_{n-1}...M_1P_1A = U,$$ then $$PA = LU,$$ where $P = P_{n-1}...P_1$ and $L$ is a unit lower triangular matrix with $\left|l_{ij}\right| \leq1$.

What I think I should do: From Theorem 2 I know that if the $LU$ decomposition exists, Gaussian elimination with partial pivoting will lead to an $LU$ decomposition of $PA$. So I need to show that every non-singular matrix $A$ has a $LU$ decomposition.
Theorem 1 states that if a non-singular matrix $A$ can be brought to its upper triangular form $U$ then an $LU$ decomposition exists. So I think that I need to show that every non-singular matrix A can be brought to its upper triangular form $U$.

Question: How do I solve this exercise? Am I on the right track?