## `linalg::factorQR` -- QR-decomposition of a matrix

#### Introduction

`linalg::factorQR``(A)` computes an QR-decomposition of an m x n matrix A, i.e., a decomposition of A into an n x n unitary matrix Q and an n x m upper triangular matrix R such that Q*R = A.

#### Call(s)

`linalg::factorQR(A)`

#### Parameters

`A` | - | a matrix of a domain of category `Cat::Matrix`

#### Returns

a list `[Q, R]` of the two matrices Q and R (of the same domain type as `A`), or the value `FAIL`.

#### Related Functions

`linalg::factorLU`, `linalg::factorCholesky`, `lllint`, `numeric::factorQR`

#### Details

- `linalg::factorQR` uses Gram-Schmidt orthonormalization to compute the decomposition.
- For a singular or non-square matrix `A` the QR-decomposition of `A` is not unique.
- The columns of Q form an orthonormal basis with respect to the scalar product of two vectors, defined by `linalg::scalarProduct`, and the 2-norm of two vectors (see the method `"norm"` of the domain constructor `Dom::Matrix`).
- If the component ring of `A` does not define the method `"conjugate"`, then the factor Q is orthogonal instead of unitary.
- If the columns of `A` cannot be orthonormalized then `FAIL` is returned.
- If `A` is a matrix over the domain `Dom::Float` and the computations are based on the standard scalar product, then the use of the corresponding function from the numeric library (`numeric::factorQR`) is recommended.
- Even if `A` is defined over the real or the complex numbers the call of `numeric::factorQR` with the option `Symbolic` is recommended for better efficiency.
- The component ring of the matrix `A` must be a field, i.e., a domain of category `Cat::Field`.

#### Example 1

We compute the QR-decomposition of a real matrix:

    >> A := Dom::Matrix(Dom::Real)(
         [[2, -3, -1], [1, 1, -1], [0, 1, -1]]
       )

                                  +-           -+
                                  |  2, -3, -1  |
                                  |             |
                                  |  1,  1, -1  |
                                  |             |
                                  |  0,  1, -1  |
                                  +-           -+

    >> QR := linalg::factorQR(A)

          -- +-                              -+
          |  |     1/2     1/2     1/2   1/2  |
          |  |  2 5       6       8    15     |
          |  |  ------, - ----, - ----------  |
          |  |    5        6          60      |
          |  |                                |
          |  |    1/2     1/2     1/2   1/2   |
          |  |   5       6       8    15      |
          |  |   ----,   ----,   ----------   |,
          |  |    5       3          30       |
          |  |                                |
          |  |            1/2      1/2   1/2  |
          |  |           6        8    15     |
          |  |     0,    ----,  - ----------  |
          |  |            6           12      |
          -- +-                              -+

             +-                          -+ --
             |                      1/2   |  |
             |   1/2     1/2     3 5      |  |
             |  5   , - 5   ,  - ------   |  |
             |                     5      |  |
             |                            |  |
             |                     1/2    |  |
             |          1/2       6       |  |
             |    0,   6   ,    - ----    |  |
             |                     3      |  |
             |                            |  |
             |                 1/2   1/2  |  |
             |                8    15     |  |
             |    0,     0,   ----------  |  |
             |                    15      |  |
             +-                          -+ --

The orthogonal matrix Q is the first element und the upper triangular matrix R is the second element of the list `QR`. The product of these two matrices is equal to the input matrix `A`:

    >> QR[1] * QR[2]

                                  +-           -+
                                  |  2, -3, -1  |
                                  |             |
                                  |  1,  1, -1  |
                                  |             |
                                  |  0,  1, -1  |
                                  +-           -+

#### Example 2

The QR-decomposition of the 3 x 2 matrix:

    >> B := Dom::Matrix(Dom::Real)(
         [[2, -3], [1, 2], [2, 3]]
       )

                                    +-       -+
                                    |  2, -3  |
                                    |         |
                                    |  1,  2  |
                                    |         |
                                    |  2,  3  |
                                    +-       -+

yields a 3 x 3 orthogonal matrix and a 3 x 2 upper triangular matrix:

    >> QR := linalg::factorQR(B)

             -- +-                              -+                  --
             |  |               1/2       1/2    |                   |
             |  |         31 194       194       |                   |
             |  |  2/3, - ---------,   ------    |  +-           -+  |
             |  |            582        194      |  |  3,   2/3   |  |
             |  |                                |  |             |  |
             |  |              1/2         1/2   |  |        1/2  |  |
             |  |         8 194       6 194      |  |     194     |  |
             |  |  1/3,   --------,   --------   |, |  0, ------  |  |
             |  |           291          97      |  |       3     |  |
             |  |                                |  |             |  |
             |  |              1/2          1/2  |  |  0,    0    |  |
             |  |        23 194        7 194     |  +-           -+  |
             |  |  2/3,  ---------,  - --------  |                   |
             |  |           582          194     |                   |
             -- +-                              -+                  --

    >> QR[1] * QR[2]

                                    +-       -+
                                    |  2, -3  |
                                    |         |
                                    |  1,  2  |
                                    |         |
                                    |  2,  3  |
                                    +-       -+

For this example we may call `numeric::factorQR(B, Symbolic)` instead, which in general is faster than `linalg::factorQR`:

    >> QR := numeric::factorQR(B, Symbolic)

             -- +-                              -+                  --
             |  |               1/2       1/2    |                   |
             |  |         31 194       194       |                   |
             |  |  2/3, - ---------,   ------    |  +-           -+  |
             |  |            582        194      |  |  3,   2/3   |  |
             |  |                                |  |             |  |
             |  |              1/2         1/2   |  |        1/2  |  |
             |  |         8 194       6 194      |  |     194     |  |
             |  |  1/3,   --------,   --------   |, |  0, ------  |  |
             |  |           291          97      |  |       3     |  |
             |  |                                |  |             |  |
             |  |              1/2          1/2  |  |  0,    0    |  |
             |  |        23 194        7 194     |  +-           -+  |
             |  |  2/3,  ---------,  - --------  |                   |
             |  |           582          194     |                   |
             -- +-                              -+                  --

#### Background

- The QR-decomposition can be used to generate a least square solution to an overdetermined system of linear equations. If A*x = b, then R*x = transpose(Q)*b can be solved via backward substitution.

#### Changes

- `linalg::factorQR` was extended to handle singular as well as non-square matrices.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000