What is the difference between Gram-Smith QR decomposition procedure and qr.m function in Matlab?

Hi everyone!

I want to know what is the differnce between the Gram-Smith procedure and qr.m function in matlab. Why there is a fourth coulmn resulting from using qr.m function? The photo is attached for the Gram-Smith procedure .Any help will be so appreciated.

The code is

A=[1 -2 -1; 2 0 1; 2 -4 2;4 0 0];
[Q,R] = qr(A)

The result is
Q =

   -0.2000    0.4000    0.8000   -0.4000
   -0.4000   -0.2000   -0.4000   -0.8000
   -0.4000    0.8000   -0.4000    0.2000
   -0.8000   -0.4000    0.2000    0.4000


R =

   -5.0000    2.0000   -1.0000
         0   -4.0000    1.0000
         0         0   -2.0000
         0         0         0
         

Answer 1

[Christine Tobler]

MATLAB's QR decomposition is computed using Householder transformations, which is generally more numerically advantageous.

[Osama Al-Shalali]

Thank you!

Is there a way to do the decomposition using a pen for a matrix containing symbols not numbers?

My goal is to evaluate the detrimainant of a rectangular matrix.

[Christine Tobler]

Yes, you can follow the algorithm described on that wiki page by hand. However, this is probably not worth the effort: Using Householder transformations reduces the impact of round-off errors that happen during computations in floating-point arithmetic - this doesn't happen if you're doing symbolic calculations by hand, so it makes more sense to do the simpler Gram-Schmidt algorithm there.

I don't have experience of how determinant of a rectangular matrix would be defined. Let me just say that the determinant is usually not reliable outside of exact arithmetic (in numerical, floating-point computations like MATLAB does), because a small round-off error can easily change the determinant completely. In these computations, the condition number should be used instead.

[Osama Al-Shalali]

The determinant of any square matrix is equal to det(Q)*prod(diag(R)), where Q and R are the matrices of the QR decomposition. I need Q to be a square matrix, so to evaluate the determinant. How can I make Q a square Matrix by using the Gram-Schmidt algorithm, even if the Matrix I want to decompose is a rectangular Matrix?

[Christine Tobler]

If you have a rectangular (tall) matrix Q of size m-by-n with orthonormal columns, and a triangular square matrix R of size n-by-n, this can always be transformed into a system like you're looking for:

Qsquare = [Q orthogonalComplementOfQ]
Rrect = [R; zeros(m-n, n)];
Q*R == Qsquare * Rrect

This is because the additional columns in Q are multiplied with the new all-zero entries. Of course, here the triangular matrix R is not square - it's impossible to write a rectangular matrix as a matrix product of all square matrices.

[Osama Al-Shalali]

Thanks. You make it clear for me.

I want to know if there is a way to find the orthogonal complementary coulmns? And is there a code in Matlab to do so?

[Christine Tobler]

In MATLAB you can use

Id = eye(m); % Identity matrix m-by-m
Qorth = orth(Id - Q*Q'); % Q is a m-by-n matrix with orthonormal columns

But for the DET workflow you mentioned, the only thing relevant is that the orthogonal complement exists, and that the complete Q will is orthogonal and therefore has determinant 1 - there's no need to compute it explicitly.

[Osama Al-Shalali]

Thanks a lot!

[f]

Just a tiny detail: Matlab's qr does not ensure that det(Q)=1. The determinant of Q may be 1 or -1; it is data-dependent, since it is (-1)^(number_of_nontrivial_reflectors_used). So it cannot be used in a straightforward way to determine the sign of det(A).

[Christine Tobler]

Good point, det(R) will only tell you the absolute value of the original matrix, otherwise you would have to construct the complete Q matrix to compute the sign of its determinant.