# QR decomposition with the output of a permutation vector

18 views (last 30 days)
Yuzhen Lu on 10 May 2020
Edited: Christine Tobler on 11 May 2020
It is noted that the Matlab syntax for qr decomposition (https://www.mathworks.com/help/symbolic/qr.html#d120e152496):
[Q,R,P] = qr(A) returns an upper triangular matrix R, a unitary matrix Q, and a permutation matrix P, such that A*P = Q*R. If all elements of A can be approximated by the floating-point numbers, then this syntax chooses the column permutation P so that abs(diag(R)) is decreasing.
For example: A = [12 -51 4; 6 167 -68; -4 24 -41]
Then, [Q,R, P] = qr(A)
Q =
-0.2894 -0.4682 -0.8349
0.9475 -0.0160 -0.3194
0.1362 -0.8835 0.4483
R =
176.2555 -71.1694 1.6680
0 35.4389 -2.1809
0 0 -13.7281
P =
2 3 1
What's the physcial meaning of the fact that the diagnoal elements of R matrix are decreasing in magnitude? Without the output P, the resulting Q and R occurs in a different order in its column vectors.
I am not clear of how these different demposition behaviors occur. What's the specific algorithm Matlab is using for qr? Householder reflections (https://blogs.mathworks.com/cleve/2016/10/03/householder-reflections-and-the-qr-decomposition/)? Any relevant resources are welcome.

Christine Tobler on 11 May 2020
Edited: Christine Tobler on 11 May 2020
The purpose of arranging all diagonal elements in descending order is to allow splitting R into two parts if A is low-rank or close to it. Here's an example:
>> A = [0 3 -2 1; 0 -6 4 -2; 0 2 -3 -1; 0 1 1 2];
>> [Q, R] = qr(A); R
R =
0 3.0000 -2.0000 1.0000
0 6.4031 -4.5290 1.8741
0 0 2.3426 2.3426
0 0 0 -0.0000
>> [Q, R, P] = qr(A); R
R =
-7.0711 -2.1213 4.9497 0
0 2.3452 2.3452 0
0 0 -0.0000 0
0 0 0 0
In the second case, it's easy to see from the diagonal of R that A is of rank 2 (accounting for some round-off error). Knowing this, One can use A*P = Q(:, 1:2)*R(1:2, :) as a decomposition of A that has this low rank. This would be much harder to do using Q and R from the two-output syntax of the qr function.
Here are some additional references: https://en.wikipedia.org/wiki/QR_decomposition#Column_pivoting and A BLAS-3 Version of the QR Factorization with Column Pivoting (this paper discusses details of efficiently implementing QR, but the introduction should provide more context about where column pivoting is used).