QR Decomposition Calculator

What is the QR decomposition?

Decomposition (or factorization) of a matrix is the process of representing this matrix as a product of two or more matrices that have various special properties. The idea is that various matrix operations become simpler thanks to the special properties of constituent matrices. There are lots of different types of matrix decompositions; among the most popular types there is the QR decomposition, which is the topic of this page, and the LU decomposition, which you can read about here.

In the QR decomposition, we factor a real square matrix A of size n x n into the product of two matrices:

A = QR

where,

• Q is an n x n orthogonal matrix (i.e., a matrix whose columns form an orthonormal basis for Rⁿ; in other words, these columns are orthogonal vectors of unit length); and
• R is an n x n upper triangular matrix (i.e., all the elements below the diagonal are zero).

The QR decomposition can be extended to rectangular matrices of size m x n, where m ≥ n. In such a case, we have A = QR where Q is of size m x n and its n columns are orthogonal vectors of unit length, and R is an upper triangular matrix of size n x n.

How to find the QR decomposition?

There are several methods for performing the QR decomposition of a given matrix A. The simplest one, which we want to explain here, is via the Gram-Schmidt orthogonalization.

First, we take the columns of A and subject them to the process of Gram-Schmidt orthogonalization. This results in a collection of orthonormal vectors: e1, e2, ..., en. Form a matrix with these vectors as columns and call this matrix Q:

Well done - you have just found the orthogonal matrix Q from the QR factorization! It remains to find the upper-triangular matrix R. This we can do with the help of the following formula:

By ⟨v, w⟩ we denote the standard inner (dot) product of vectors v and w.

Equivalently, you can determine R by left-multiplying the original matrix A by the transpose of our newly-found matrix Q as follows:

Applications of the QR decomposition

The QR decomposition has multiple applications. The one we want to discuss here is solving systems of linear equations. Another important field where QR decomposition is often used is in calculating the eigenvalues and eigenvectors of a matrix. This method is known as the QR algorithm or QR iteration.

As you most likely well know, there are several methods of solving systems of linear equations, among them

• Substitution method; and
• Elimination method.

Now we'll see how the QR factorization procedure can facilitate the task of solving a system of linear equations. Suppose we have to solve the system:

where,

• a11, a12, ..., amn are the coefficients of the system;
• b1, b2, ..., bm are the constant terms; and
• x1, x2, ..., xn are the unknowns.

Our system can be rewritten as:

Ax = b,

where,

So now we have to determine the vector x given the matrix A and the vector b.

Assume that m ≥ n and that we have the QR decomposition of A, i.e., we know the orthogonal matrix Q and the upper-triangular matrix R such that A = QR. This means we have to solve the equation:

QRx = b

Let's multiply both sides of the above equation by Qᵀ:

QᵀQRx = Qᵀb

Why have we done that, you may (and should) ask? Now it is more complicated than before, isn't it? At first sight, yes, but recall what we learned about orthogonal matrices back in the first section: they satisfy the property that QᵀQ = Id. In consequence, the left-hand side simplifies as follows:

QᵀQRx = Rx

and the whole equation now looks like:

Rx = Qᵀb

Since there is a triangular matrix on the left-hand side, this equation is straightforward to solve. An example best shows it, so in the next section, we solve a system of linear equations via the QR factorization.