QR decomposition with the output of a permutation vector

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.

Answer 1

[Christine Tobler]

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).