Let $A,Q_1 \in \mathbb{R}^{m_1 \times n}$, $B \in \mathbb{R}^{m_2 \times n}$ $Q_2 \in \mathbb{R}^{(m_1+m_2) \times n}$, and $Q_3 \in \mathbb{R}^{ (n+m_2) \times n }$ with $Q_i$ having orthonormal columns for $i=1,2,3$. Let $R_1,R_2,R_3 \in \mathbb{R}^{n \times n}$ be upper triangular. Assume

\begin{equation*} A = Q_1R_1 \\ \begin{bmatrix} B \\ A \end{bmatrix} = Q_2R_2 \\ \begin{bmatrix} B \\ R_1 \end{bmatrix} = Q_3R_3 \end{equation*}

Under certain conditions, $R_2 = R_3$. What are these conditions? As a side note, the problem is sort of saying that the "upper-triangular factor obtained in $QR$ factorization when augmenting the matrix B is invariant under the unitary transformation $Q_1^{T}$."

Note that it is implicit that $m_1,m_2 \geq n$ given that $Q_i$ have orthonormal columns. The only thing I can think to try is to multiply the equations by $Q_2^{T},Q_3^{T}$ respectively and see under what constraints that makes $R_2 = R_3$. I tried expanding $Q_i$ as block matrix...this didn't lead me anywhere (but might work). I'm unsure how to exploit that $R_i$ are upper triangular.

  • $\begingroup$ What are the dimensions of $B$? $\endgroup$ – artificial_moonlet Aug 14 '18 at 14:42
  • $\begingroup$ Sorry about that, I've edited it...$B \in \mathbb{R}^{m_2 \times n}$ and also there was a mistake...$Q_2 \in \mathbb{R}^{(m_1+m_2) \times n}$. $\endgroup$ – TylerMasthay Aug 14 '18 at 16:08

Let $I$ be the $m_2 \times m_2$ identity. Then the matrix $$ Q_0:= \begin{bmatrix} I & 0 \\ 0 & Q_1 \end{bmatrix} \in \mathbb{R}^{(m_1 + m_2) \times (m_2 \times n)} $$ has orthonormal columns. (For why, think about $Q_0$ in terms of its indiviual columns and how the 2-norm is calculated.)

Furthermore, $$ Q_0 Q_3 R_3 = Q_0 \begin{bmatrix} B \\ R_1 \end{bmatrix} = \begin{bmatrix} B \\ Q_1 R_1 \end{bmatrix} = \begin{bmatrix} B \\ A \end{bmatrix} = Q_2 R_2 $$ Since each $Q_i$ has full rank ($Q_0$ by construction; the others by assumption), then $R_3 = R_2$ follows from requring that $Q_0 Q_3 = Q_2$.

  • $\begingroup$ Great answer. Is there more going in the construction of $Q_0$ other than "it's just a trick with the block matrices" or is that essentially all? Also, the dimensions of $Q_0$ are $\mathbb{R}^{(m_1+m_2) \times (n+m_2)}$, correct? $\endgroup$ – TylerMasthay Aug 14 '18 at 16:12
  • $\begingroup$ Fixed the dimensions on $Q_0$. Note that this is not an "if and only if" statement-- you asked for some conditions that imply that $R_2 = R_3$. But I think these conditions are quite natural. You're concatenating $B$ with $A$ and again with a piece of $A$ and then asking how they are related. They must of course be related by the other piece of $A$-- $Q_1$-- and the trick with the block matrices gives you precisely that. It may also help to consider why $Q_0$ is orthonormal in the first place. ;) $\endgroup$ – artificial_moonlet Aug 15 '18 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.