RQ decomposition

$\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$$