It's a well known fact that $\det(P)=(-1)^t$, where $t$ is the number of row exchanges in the $PA=LU$ decomposition. Can somebody point me to a (semi) formal proof as why it is so?
[Math] determinant of permutation matrix
determinantmatrices
Related Solutions
Here's an explanation for three dimensional space ($3 \times 3$ matrices). That's the space I live in, so it's the one in which my intuition works best :-).
Suppose we have a $3 \times 3$ matrix $\mathbf{M}$. Let's think about the mapping $\mathbf{y} = f(\mathbf{x}) = \mathbf{M}\mathbf{x}$. The matrix $\mathbf{M}$ is invertible iff this mapping is invertible. In that case, given $\mathbf{y}$, we can compute the corresponding $\mathbf{x}$ as $\mathbf{x} = \mathbf{M}^{-1}\mathbf{y}$.
Let $\mathbf{u}$, $\mathbf{v}$, $\mathbf{w}$ be 3D vectors that form the columns of $\mathbf{M}$. We know that $\det{\mathbf{M}} = \mathbf{u} \cdot (\mathbf{v} \times \mathbf{w})$, which is the volume of the parallelipiped having $\mathbf{u}$, $\mathbf{v}$, $\mathbf{w}$ as its edges.
Now let's consider the effect of the mapping $f$ on the "basic cube" whose edges are the three axis vectors $\mathbf{i}$, $\mathbf{j}$, $\mathbf{k}$. You can check that $f(\mathbf{i}) = \mathbf{u}$, $f(\mathbf{j}) = \mathbf{v}$, and $f(\mathbf{k}) = \mathbf{w}$. So the mapping $f$ deforms (shears, scales) the basic cube, turning it into the parallelipiped with sides $\mathbf{u}$, $\mathbf{v}$, $\mathbf{w}$.
Since the determinant of $\mathbf{M}$ gives the volume of this parallelipiped, it measures the "volume scaling" effect of the mapping $f$. In particular, if $\det{\mathbf{M}} = 0$, this means that the mapping $f$ squashes the basic cube into something flat, with zero volume, like a planar shape, or maybe even a line. A "squash-to-flat" deformation like this can't possibly be invertible because it's not one-to-one --- several points of the cube will get "squashed" onto the same point of the deformed shape. So, the mapping $f$ (or the matrix $\mathbf{M}$) is invertible if and only if it has no squash-to-flat effect, which is the case if and only if the determinant is non-zero.
Let $$A=\pmatrix{2&3\cr4&5\cr}$$ (for example – almost any example should do). You could divide the first row by 2; subtract 4 times the first row from the second; divide the second row by the appropriate number (to get a 1 in the lower right corner); subtract the appropriate multiple of the second row from the first.
Or, you could divide the second row by 5; subtract 3 times the second row from the first; divide the first row by the appropriate number; subtract the appropriate multiple of the first row from the second.
Either way, you get (efficiently) a factorization into four elementary matrices, but they are different factorizations, even if reordering the matrices is allowed.
EDIT: More simply, one could just note that $$\pmatrix{a&0\cr0&1\cr}\pmatrix{1&b\cr0&1\cr}=\pmatrix{1&ab\cr0&1\cr}\pmatrix{a&0\cr0&1\cr}$$
Best Answer
Perhaps you can elaborate on what exactly is confusing to you.
An elementary row switch matrix has determinant $-1$. A permutation matrix is just a product of such elementary matrices, so every row switch introduces a factor of $-1$. If you have $t$ row switches, then $$P = E_t\cdots E_2E_1 \implies \det(P) = \prod^t_{i=1}\det(E_i)=(-1)^t$$