# qre¶

## Purpose¶

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

## Format¶

{ r, e } = qre(x)
Parameters

x (NxP matrix) – data

Returns
• r (KxP upper triangular matrix) – $$K = min(N,P)$$.

• e (Px1 vector) – permutation vector

## Remarks¶

qre() is the same as qqre() but doesn’t return the $$Q_1$$ matrix. If $$Q_1$$ is not wanted, qre() will save a significant amount of time and memory usage, especially for large problems.

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′X[.,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]$$.

qre() does not return the $$Q_1$$ matrix because in most cases it is not required and can be very large. If you need the $$Q_1$$ matrix, see the function qqre(). If you need the entire $$Q$$ matrix, call qyre() with $$Y$$ set to a conformable identity matrix. For most problems $$Q'Y$$, $$Q_1'Y$$, or $$QY$$, $$Q_1\ Y$$, for some y, are required. For these cases see qtyre() and qyre().

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_1$$ is NxM and $$X_2$$ is Nx(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 Mx(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().

qr.src