QR decomposition and Gram Schmidt process

Let $A\in M_n(\mathbb{R})$, invertible matrix. I need to decompose $A=QR$ where $Q$ is an orthogonal matrix and $R$ is an upper triangular.

Now, if $A=[a_1,\ldots a_n]$ and we apply Gram Schmidt process on it's columns, we get:

$u_1 = a_1 \\ u_2 = a_2 - \frac{\langle u_1,a_2 \rangle }{\|u_1\|^2}u_1 \\ u_k = a_k - \sum_{j=1}^{k-1} \frac{\langle u_j, a_k \rangle }{\|u_j\|^2}u_j$

Rearranging the terms:

$a_1 = u_1 \\ a_2 = u_2 + \frac{\langle u_1,a_2 \rangle }{\|u_1\|^2}u_1 \\ a_k = u_k + \sum_{j=1}^{k-1} \frac{\langle u_j, a_k \rangle }{\|u_j\|^2}u_j$

Now, before moving into a matrix multipication form, I need to do something with the $\{u_1,\ldots, u_n\}$, representing them in a similar form to the other terms.

How?

• How is it not in similar form? – BCLC Jan 10 '15 at 18:18
• You are subtracting scalars from vectors – David Peterson Jan 10 '15 at 18:18
• I've fixed the repeating typo. – AlonAlon Jan 10 '15 at 18:22
• are you making sure that all your $u's$ are of length one? – abel Jan 10 '15 at 18:28

I'm not sure I understand. The $u_i$ form the columns of the matrix $Q$. The coefficient on $u_j$ in the equation for $a_i$ is $r_{ij}$.
• What would be $r_{11}$? – AlonAlon Jan 10 '15 at 18:24
• $r_{11}$ is the coefficient on $u_1$ in the equation for $a_1$, which is $1$. (Actually, you usually want $Q$ to have orthonormal columns, in which case $u_1=a_1/\| a_1 \|$ and $r_{11}=\| a_1 \|$.) – Ian Jan 10 '15 at 18:24
• @AlonAlon Sorry, I made some seemingly contradictory remarks. They don't actually contradict each other, but they involve different conventions. If you take $Q$, as usual, to have orthonormal columns, then $r_{11}=\langle e_1,a_1 \rangle=\frac{\langle u_1,a_1 \rangle}{\| u_1 \|^2}$. If you don't normalize the columns of $Q$, you can take $r_{11}=1$. – Ian Jan 10 '15 at 18:39
• @AlonAlon I made another typo between negotiating my way through the two conventions. Non-orthonormal columns: $u_1=a_1$, $r_{11}=1$. Orthonormal columns: $e_1=a_1/\| a_1 \|$, $r_{11}=\langle e_1,a_1 \rangle$. Then $a_1 = r_{11} e_1$ because $\langle e_1,a_1 \rangle e_1 = \langle \frac{a_1}{\| a_1 \|},a_1 \rangle \frac{a_1}{\| a_1 \|} = a_1 \frac{\| a_1 \|^2}{\| a_1 \|^2} = a_1$. – Ian Jan 10 '15 at 18:49
• You can view matrix multiplication like this: $C=AB$ if $c_i = \sum_{j=1}^n a_j b_{ji}$ for $i=1,\dots,n$. In other words, $c_i$ is the linear combination of the columns of $a$ given by the coefficients in the $i$th column of $B$. So when $u_1=a_1$, you want $r_{11}=1$ and $r_{j1}=0$ for $j=2,\dots,n$. Going over a column, we have $a_2=u_2+...$, so $r_{22}=1$ and $r_{21}$ is the "...". And so forth; with non-normalized columns we end up with $1$s on the diagonal of $R$. – Ian Jan 10 '15 at 20:15