The QR decomposition of a matrix
- Basic idea
- The case when the matrix has linearly independent columns
- General case
- Full QR decomposition
Basic idea
The basic goal of the QR decomposition is to factor a matrix as a product of two matrices (traditionally called , hence the name of this factorization). Each matrix has a simple structure that can be further exploited in dealing with, say, linear equations.
The QR decomposition is nothing else than the Gram-Schmidt procedure applied to the columns of the matrix and with the result expressed in matrix form. Consider a matrix
, with each
a column of
.
Case when
is full column rank
Assume first that the ‘s (the columns of
) are linearly independent. Each step of the G-S procedure can be written as

We write this as

where and
.
Since the ‘s are unit-length and normalized, the matrix
satisfies
. The QR decomposition of a
matrix
thus allows writing the matrix in factored form:

where is a
matrix with
, and
is
, upper-triangular.
>> [Q,R] = qr(A,0); % A is a mxn matrix, Q is mxn orthogonal, R is nxn upper triangular
Example: QR decomposition of a 4×6 matrix.
Case when the columns are not independent
When the columns of are not independent, at some step of the G-S procedure we encounter a zero vector
, which means
is a linear combination of
. The modified Gram-Schmidt procedure then simply skips to the next vector and continues.
In matrix form, we obtain , with
, and
has an upper staircase form, for example:

(This is simply an upper triangular matrix with some rows deleted. It is still upper triangular.)
We can permute the columns of to bring forward the first non-zero elements in each row:

where is a permutation matrix (that is, its columns are the unit vectors in some order), whose effect is to permute columns. (Since
is orthogonal,
.) Now,
is square, upper triangular, and invertible, since none of its diagonal elements is zero.
The QR decomposition can be written

where
is the
of
;
is
upper triangular, invertible matrix;
is a
matrix;
is a
permutation matrix.
>> [Q,R,inds] = qr(A,0); % here inds is a permutation vector such that A(:,inds) = Q*R
Full QR decomposition
The full QR decomposition allows to write where
is square and orthogonal (
). In other words, the columns of
are an orthonormal basis for the whole output space
, not just for the range of
.
We obtain the full decomposition by appending an identity matrix to the columns of
:
. The QR decomposition of the augmented matrix allows to write

where the columns of the matrix
are orthogonal and
is upper triangular and invertible. (As before,
is a permutation matrix.) In the G-S procedure, the columns of
are obtained from those of
, while the columns of
come from the extra columns added to
.
The full QR decomposition reveals the rank of : we simply look at the elements on the diagonal of
that are not zero, that is, the size of
.
>> [Q,R] = qr(A); % A is a mxn matrix, Q is mxm orthogonal, R is mxn upper triangular
Example: QR decomposition of a 4×6 matrix.