# Solving Linear Systems with LU Decomposition and complete pivoting; stupid question

Given a matrix A and vector B, solve

$Ax=B$

Using LU Decomposition with full Pivoting;

$PAQ=LU$

where P and Q are row and column permutation vectors (correct me if I'm wrong)

What I don't understand is what to do with the permutation matrices to finish the solution. I know in partial pivoting, its simple

$Lz=PB$

$Ux=z$

But what do I do with Q?

PS If anyone is a C head, you're help would be appreciated in the implementation

• Remember that permutation matrices are orthogonal... – J. M. isn't a mathematician Apr 17 '11 at 15:42
• And since Q is the column permutation, and B is a single column, it can effectively be thrown away? – Andrew Bolster Apr 17 '11 at 15:45
• No; remember that in partial pivoting, the row permutation is "undone" by first permuting the right hand side. Undoing a column permutation corresponds to permuting the result after multiplying the RHS vector with the inverses of the triangular matrices. – J. M. isn't a mathematician Apr 17 '11 at 16:00

Recall that permutation matrices have the property that $P^{-1} = P^T$, so we can re-arrange the factorization to write $A$ in the form $A = P^TLUQ^T$. After that, it is straightforward to solve:
\begin{align} Lz &= Pb \\ Uy &= z \\ x &= Qy \\ \end{align}
Note that $Q$ can't be just "ignored" because it is a "column permutation". It is a column permutation by virtue of how it is used (right-multiplication), not by virtue of the structure of the matrix, and it does have an effect when applied to a column vector with left-multiplication.