Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a matrix A and vector B, solve


Using LU Decomposition with full Pivoting;


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



But what do I do with Q?

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

share|cite|improve this question
Remember that permutation matrices are orthogonal... – J. M. 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. Apr 17 '11 at 16:00
up vote 2 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.