# The QR Decomposition

The QR decomposition or QR factorization of a matrix expresses the matrix as the product of an orthogonal matrix and an upper triangular matrix. The matrix can be of any type, and of any shape. The QR decomposition is usually written as

*A* = *QR*,

where *Q* is a square, orthogonal matrix (or a unitary matrix
if *A* is complex),
and *R* is an upper-triangular matrix.
The QR algorithm uses orthogonal (or unitary) transformations.
This gives the QR decomposition much better numerical stability than
the LU decomposition, even though the computation takes twice as long.
When the matrix is ill-conditioned, or high accuracy is required,
the longer running time is justified.

## Working with QR Decompositions

The QR decomposition is implemented by the QRDecomposition<T> class. It has no constructors. Instead, it is created by calling the GetQRDecomposition method on the matrix. This method has two overloads. The first overload has no arguments. The second overload takes a Boolean value that specifies whether the contents of the matrix may be overwritten by the QR decomposition. The default is false.

```
var A = Matrix.CreateFromArray(5, 3, new double[] {
2.0, 2.0, 1.6, 2.0, 1.2,
2.5, 2.5,-0.4,-0.5,-0.3,
2.5, 2.5, 2.8, 0.5,-2.9
}, MatrixElementOrder.ColumnMajor);
var qr = A.GetQRDecomposition();
```

The Decompose method performs the actual decomposition. This method copies the matrix if necessary. It then calls the appropriate LAPACK routine to perform the actual decomposition. This method is called by other methods as needed. You will rarely need to call it explicitly.

Once the decomposition is computed, a number of operations can be performed in much less time. You can repeatedly solve a system of simultaneous linear equations with different right-hand sides. If the system is overdetermined, you can use the LeastSquaresSolve method to obtain a least squares solution to an over-determined system. If the matrix is square, you can also calculate the determinant and the inverse of the base matrix:

```
var b = Vector.Create(1.1, 0.9, 0.6, 0.0, -0.8);
var x = qr.LeastSquaresSolve(b);
```

The OrthogonalFactor
property returns orthogonal matrix, *Q*, of the decomposition.
The UpperTriangularFactor
property returns a TriangularMatrix<T>
containing the upper triangular matrix, *R*:

```
var Q = qr.OrthogonalFactor;
var R = qr.UpperTriangularFactor;
var R2 = qr.TrimmedUpperTriangularFactor;
```

The matrix *Q* is kept in a compact format. Although it is possible
to convert it to a regular dense matrix, the calculation is fairly expensive.
Fortunately, this is hardly ever necessary. Operations like transposition,
multiplication, and solving (which is equivalent to multiplying by the transpose
for an orthogonal matrix) avoid the conversion:

```
var Qx = Q * x;
var QTx = Q.Transpose() * x;
var QTx2 = Q.Solve(x);
```

When the number of rows of the matrix *A* is greater than
the number of columns, the triangular matrix *R* will
contain rows of zeros below the diagonal. The columns of *Q*
that are multiplied by these rows in the product *QR*
do not contribute to the product. In this scenario, two
further properties may be useful.
The TrimmedUpperTriangularFactor
property returns the square part of the matrix *R*, with the zero rows removed.
The ThinOrthogonalFactor
property returns the orthogonal matrix with the columns that don't contribute
to the product removed.

## The RQ, QL, and LQ Decompositions

There are several matrix decompositions that are closely related
to the QR decomposition. The *RQ decomposition*
factors a matrix into a product *RQ*, where R is an upper
triangular matrix and *Q* is an orthogonal matrix.
The *QL decomposition*
factors a matrix into a product *QL*, where L is a lower
triangular matrix, and the *LQ decomposition*
factors matrix into a product *LQ*.

These decompositions are implemented by the RQDecomposition<T>, QLDecomposition<T>, and LQDecomposition<T> classes, respectively. They work in exactly the same way as the QR decomposition. There are GetRQDecompositionGetQLDecompositionGetLQDecomposition methods that return the decomposition for a specific matrix. The properties are analogous, including the trimmed and thin versions.