# RQ decomposition

Can someone explain me how we can compute RQ decomposition for a given matrix (say, $3 \times 4$). I know how to compute QR decomposition.

I know the function in MATLAB which computes this RQ decomposition. But, I want to know how we can do that on paper.

PS: The practical use of RQ decomposition is in extracting the intrinsic and extrinsic parameters of the camera when the camera matrix $P(3 \times 4$) is given

thanks!

$\newcommand\iddots{\mathinner{ \kern1mu\raise1pt{.} \kern2mu\raise4pt{.} \kern2mu\raise7pt{\Rule{0pt}{7pt}{0pt}.} \kern1mu }}$

This concerns $RQ$ decompositions of square matrices.

Suppose you have a $n \times n$ matrix $A$ and want to compute the RQ decomposition. If you know how to compute QR decompositions, you will just need a few transpositions / row-column permutations.

Note that given the matrix $P := \begin{bmatrix} & & 1\\ & \iddots & \\ 1 & & \\ \end{bmatrix}$ (this is different to the camera matrix mentioned in the question), we get that $AP$ reverses the order of columns of $A$ and $PA$ reverses the order of rows. Also note that $P^T = P$ and $PP = E_n$, so $P^{-1} = P = P^T$, in particular $P$ is orthogonal.

Consider the following algorithm:

i.) Compute $\tilde A := PA$ (i.e. reverse rows of $A$)

ii.) Compute decomposition of $\tilde A ^T = \tilde Q \tilde R$

iii.) Set $Q := P \tilde Q^T$ (i.e. reverse rows of $\tilde Q^T$, note that $Q$ is orthogonal)

iv.) Set $R := P \tilde R^T P$

In step iv.) the following happens: $\tilde R$ is an upper triangular matrix. By transposing it, it becomes a lower triangular matrix. So we reverse rows and columns and obtain again an upper triangular matrix $R$. See sketch (start with lower triangular, reverse rows, then revere columns).

$$\begin{bmatrix} * & \cdot & \cdot \\ * & * & \cdot \\ * & * & * \end{bmatrix} \to \begin{bmatrix} * & * & * \\ * & * & \cdot \\ * & \cdot & \cdot \end{bmatrix} \to \begin{bmatrix} * & * & * \\ \cdot & * & * \\ \cdot & \cdot & * \\ \end{bmatrix}$$

Altogether $R$ and $Q$ yields our decomposition:

$$RQ = (P \tilde R^T P)(P \tilde Q^T) = P \tilde R^T \tilde Q^T = P(\tilde Q \tilde R)^T = P(\tilde A ^T)^T = P \tilde A = PPA = A$$

• Copied as Comment by @NicholasCasale: From this link, and working through a RQ decomposition for an image projection, it seems that the accepted answer needs a left-to-right flip on R for it to be upper triangular. (MATLAB's fliplr(.)) Feb 11, 2017 at 6:04
• You seem to be saying that $r(\tilde{R}^T)$ is upper triangular when $\tilde{R}$ is upper triangular. But although $\tilde{R}^T$ is surely lower triangular in this case, reversing the rows (which amounts to premultiplying by a particular permutation matrix $P$) does not produce an upper triangular matrix: $$\begin{bmatrix} * & \cdot & \cdot \\ * & * & \cdot \\ * & * & * \end{bmatrix} \to \begin{bmatrix} * & * & * \\ * & * & \cdot \\ * & \cdot & \cdot \end{bmatrix}$$ Feb 11, 2017 at 16:22
• @hardmath Thanks, I refactored my post. It should be okay now. If you don't mind, please have a look and tell me if you see any more mistakes! Feb 11, 2017 at 21:00
• At a glance you fixed it exactly as I would have. It might worth a caution that your permutation matrix $P$ differs from the "camera matrix" $P$ briefly mentioned in the Question. Feb 11, 2017 at 21:08
• Ah, yes, didn't recognize there is also a $P$ in the question. Thanks again for all the effort! Feb 11, 2017 at 21:14

The solution by @jonnycrab is good when you have a QR-factorizer in hand. Here is the RQ Decomposition algorithm for a $$3 \times 3$$ matrix $$A$$ from Appendix A4.1.1 in Multiple view Geometry in Computer Vision 2nd ed. by Richard Hartley and Andrew Zisserman.

The rotation matrices for the $$x,$$ $$y,$$ and $$z$$ axes are:

$$Q_x = \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & c & -s \\ 0 & s & c \end{array}\right],\ \ Q_y = \left[\begin{array}{ccc} c & 0 & s \\ 0 & 1 & 0 \\ -s & 0 & c \end{array}\right],\ \ Q_z = \left[\begin{array}{ccc} c & -s & 0 \\ s & c & 0 \\ 0 & 0 & 1 \end{array}\right]$$

where $$c = \cos\theta,$$ and $$s = \sin\theta$$ for some angle $$\theta.$$

1. $$R \leftarrow A$$
2. Multiply $$R \leftarrow R Q_x$$ so that $$R_{32}$$ becomes zero (see below).
3. Multiple $$R \leftarrow R Q_y$$ so that $$R_{31}$$ is zero. This does not change the second column so $$R_{32}$$ remains zero.
4. Multiple $$R \leftarrow R Q_z$$ so that $$R_{21}$$ is zero. The first two columns are replaced by linear combinations of themselves so $$R_{31}$$ and $$R_{32}$$ remain zero.
5. $$Q = (Q_x Q_y Q_z)^T$$

• The second step yields the equation $$R_{32}\cdot c + R_{33}\cdot s = 0.$$ A solution that satisfies the constraint $$s^2 + c^2 = 1$$ is $$c = \frac{R_{33}}{\sqrt{R_{32}^2 + R_{33}^2}}$$ and $$s = \frac{-R_{32}}{\sqrt{R_{32}^2 + R_{33}^2}}.$$ Note that we had two choices for the sign of $$s;$$ our choice forces $$R_{33}$$ to be positive.

• For the third step we have $$R_{31} \cdot c - R_{33} \cdot s = 0.$$ The solution is $$c = \frac{R_{33}}{\sqrt{R_{31}^2 + R_{33}^2}}$$ and $$s = \frac{R_{31}}{\sqrt{R_{31}^2 + R_{33}^2}}.$$ Again, we could have chosen both $$s$$ and $$c$$ to be negative, but our choice yields a positive value for $$R_{33}.$$

• For the fourth step we have $$R_{21}\cdot c + R_{22}\cdot s = 0$$. The solution is $$c = \frac{R_{22}}{\sqrt{R_{21}^2 + R_{22}^2}}$$ and $$s = \frac{-R_{21}}{\sqrt{R_{21}^2 + R_{22}^2}}$$ which forces $$R_{22}$$ to be positive.