1
$\begingroup$

Let $A \in \mathbb R^{m×n}, m > n,$ and denote the columns of $A$ by $a_1, a_2, . . . , a_n \in \mathbb R^m$. Let $Q \in \mathbb R^{m×n}$ be a matrix with orthonormal columns, and let $q_1, q_2, · · · , q_n \in \mathbb R^m$ denote the columns of $Q$. Let $R \in \mathbb R^{n×n}$ be upper triangular, and $A = QR$. This is called an economy size $QR$ decomposition. The matrix $Q$ is not square, and therefore does not count as an orthogonal matrix, but it does have n orthonormal columns. Then: $r_{11} = ±\|a_1\|_2, q_1 = a_1/r_{11}, r_{12} = q_1^T > a_2, r_{22} = ±\|a_2 − r_{12}q_1\|_2, q_2 = (a_2 − r_{12}q_1)/r_{22}$ and so on (This is Gram-Schmidt procedure). One thing that’s really not so nice about the Gram-Schmidt procedure described is the possibility of dividing by zero in a few places. Let’s say for instance that $r_{33}$ came out to be zero. Then define: $$q_3=\frac{u-(q_1^Tu)q_1-(q_2^Tu)q_2}{\|u-(q_1^Tu)q_1-(q_2^Tu)q_2\|}.$$ Explain why $q_3$ is well-defined unless u lies in the span of $q_1$ and $q_2$.

My attempt: I can show one way that if $u = c_1q_1+c_2q_2$, then $u-(q_1^Tu)q_1-(q_2^Tu)q_2=u-(q_1^T(c_1q_1+c_2q_2))q_1-(q_2^T(c_1q_1+c_2q_2))q_2=u-c_1q_1-c_2q_2=0$ How to show that this is the only case when $\|u-(q_1^Tu)q_1-(q_2^Tu)q_2\|$ is $0$?

$\endgroup$
1
$\begingroup$

Yes, since $q_1,q_2$ are orthogonal, $(q_1'u)q_1+(q_2'u)q_2$ is precisely the projection of $u$ on the space spanned by $q_1$ and $q_2$. Note that if $v$ is any non-zero vector then the projection of a vector $u$ onto column space of $v$ is given by $(vv')u/v'v=v(v'u)/v'v=(v'u/v'v)v$. Here $q_1,q_2$ being orthonormal, $q_1'q_1=q_2'q_2=1$.

So the undefinedness happens precisely when the denominator of your expression is zero, and that happens precisely when $u=Pu$ where $P$ is the projection matrix onto the space spanned by $q_1,q_2$ that is, $P=q_1q_1'+q_2q_2'$, that is precisely when $u$ belongs to the linear span of $q_1,q_2$.

$\endgroup$

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.