MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

Hi, I'm attempting to implement a QR factorization with column pivoting so that the returned R matrix has decreasing diagonal elements (that is, $r_{i,i} \leq r_{i-1,i-1}$ for all $i\geq 2$). Mathematically, it would involve finding the matrix $P$ so that $AP=QR$, or $A=QRP^T$. I'm using Gram-Schmidt to compute QR.

One source I found was this:

Quote from the answer: "During the iteration #k, it is easy to show that if we pick among the set of remaining vectors (i.e., not yet included in the span) the vector that has the largest orthogonal component to the current subspace (generated by k first vectors), then the diagonal of R must decrease."

Sounds simple enough, but HOW do I determine which vector of the remaining ones that have the largest orthogonal component to the subspace that's already been found?

Thanks a lot in advance for any help on this matter!

Best regards Hallgeir

share|cite|improve this question
Is there any reason why you prefer Gram-Schmidt (you're using the modified version I hope, classical Gram-schmidt has piss-poor numerical stability) over using Householder reflections? – J. M. Oct 25 '10 at 4:28
Seconded. Also, check if you can link to the relevant LAPACK subroutine ( instead of coding it from scratch. – Federico Poloni Oct 25 '10 at 9:19
Hi, these are reasonable points of course, but the whole point was to learn how to actually implement it. And I do indeed use the modified version. :) I learn better by doing, and as such I find that implementing the algorithm is a useful way of achieving that. – Hallgeir Oct 26 '10 at 5:31
up vote 0 down vote accepted

At each step $k$, choose the column of the "reduced" working matrix $A(k:n,k:n)$ with largest Euclidean norm and bring it in front with a permutation. Notice that $r_{11}$ is the Euclidean norm of the first column...

share|cite|improve this answer
A little late reply from me (seems the email notification came quite late), but thank you very much! :) Seems to work perfectly! – Hallgeir Oct 26 '10 at 5:34

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.