# qqre¶

## Purpose¶

Computes the orthogonal-triangular (QR) decomposition of a matrix x, such that: $$X[\; .,\; E\; ] = Q_1R$$

## Format¶

{ q1, r, e } = qqre(x)
Parameters

x (NxP matrix) – data

Returns
• q1 (NxK matrix) – unitary matrix, $$K = min(N, P)$$.

• r (KxP matrix) – upper triangular matrix

• e (Px1 vector) – permutation vector

## Remarks¶

Given $$X[\;.,\; E\;]$$, where $$E$$ is a permutation vector that permutes the columns of $$X$$, there is an orthogonal matrix $$Q$$ such that $$Q'X[\; .,\; E\; ]$$ is zero below its diagonal, i.e.,

$\begin{split}Q′R[\; .,\; E\; ] = \begin{bmatrix} R \\ 0 \end{bmatrix}\end{split}$

where $$R$$ is upper triangular. If we partition

$Q⁢ = \begin{bmatrix} Q_1 & Q_2 \end{bmatrix}$

where $$Q_1$$ has $$P$$ columns, then

$X[\; .,\; E\; ] = Q_1R$

is the QR decomposition of $$X[\; .,\; E\; ]$$.

If you want only the $$R$$ matrix, see qre(). Not computing $$Q_1$$ can produce significant improvements in computing time and memory usage.

If $$X$$ has rank $$P$$, then the columns of $$X$$ will not be permuted. If $$X$$ has rank $$M < P$$, then the $$M$$ linearly independent columns are permuted to the front of $$X$$ by $$E$$. Partition the permuted $$X$$ in the following way:

$X[\; .,\; E\; ] = \begin{bmatrix} X_1 & X_2 \end{bmatrix}$

where $$X$$ is NxM and $$X_2$$ is $$N \times (P-M)$$. Further partition $$R$$ in the following way:

$\begin{split}R = \begin{bmatrix} R_{11} & R_{12} \\ 0 & 0 \end{bmatrix}\end{split}$

where $$R_{11}$$ is MxM and $$R_{12}$$ is Mx(P-M). Then

$A = R_{11}^{-1}R_{12}$

and

$X_2 = X_1A$

that is, $$A$$ is an $$M \times (P-N)$$ matrix defining the linear combinations of $$X_2$$ with respect to $$X_1$$.

If $$N < P$$, the factorization assumes the form:

$Q'X = \begin{bmatrix} R_1 & R_2 \end{bmatrix}$

where $$R_1$$ is a PxP upper triangular matrix and $$R_2$$ is Px(N-P). Thus $$Q$$ is a PxP matrix and $$R$$ is a PxN matrix containing $$R_1$$ and $$R_2$$. This type of factorization is useful for the solution of underdetermined systems. For the solution of

$X[\; .,\; E\; ]b = Y$

it can be shown that

b = qrsol(Q'Y, R1)|zeros(N-P, 1);


The explicit formation here of $$Q$$, which can be a very large matrix, can be avoided by using the function qtyre().

For further discussion of QR factorizations see the remarks under qqr().

qqr.src