I'm looking into QR-factorisation using Givens-rotations and I want to transform matrices into their upper triangular matrices. I know how to do this for matrix $ B \in \mathbb{R}^{m\times m}$ but how do you do this for a matrix $ A \in \mathbb{R}^{m\times n}$?
My problem is that the Givens-rotation matrix is by definition a $ m \times m $ matrix and that I think I have to do something special to matrix $A$ or to the Givens-rotation matrix.
So how do we find for example $G^{(1)^{T}}_{34}A$ if
$$
A = \begin{bmatrix}
1 & -2 & 3 \\
1 & -3 & 5 \\
2 & 3 & 1 \\
-3 & 4 & 2\\
\end{bmatrix}
$$
The solution should be
$$
G^{(1)^{T}}_{34}A =
\begin{bmatrix}
1 & -2 & 3 \\
1 & -3 & 5 \\
3.6056 & -1.6641 & -1.1094 \\
0 & 4.7150 & 1.9415\\
\end{bmatrix}
$$ but I don't know how to calculate this.
Can someone tell me where I go wrong in the following calculation?
Step 1:
$$
G^{(1)}_{34} =
\begin{bmatrix}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & c & -s \\
0 & 0 & s & c\\
\end{bmatrix}
$$
Step 2:
We add a zero-vector to $A$ because $ A \in \mathbb{R}^{m\times n}$ and the matrix A must have form $m \times m$ to use Givens-rotations. We create
$$
A' =
\begin{bmatrix}
1 & -2 & 3 & 0\\
1 & -3 & 5 & 0\\
2 & 3 & 1 & 0\\
-3 & 4 & 2 & 0\\
\end{bmatrix}
$$
Step 3:
We calculate c and s.
$$
c = 1 / (\sqrt{1^2 + 2^2})
$$
$$
s = 2 / (\sqrt{1^2 + 2^2})
$$
Step 4:
We fill in the values $c$ and $s$ in matrix $G^{(1)}_{34}$ and calculate the transpose $G^{(1)^{T}}_{34}$.
Step 5:
We multiply $G^{(1)^{T}}_{34}$ and $A'$.
It doesn't return a matrix with $A_{1,4} = 0$ when I use the previous steps so where do I go wrong?
Best Answer
Why would a non-squareness of $A$ pose a problem? If $A\in\mathbb{R}^{m\times n}$, $A_0=A$, you first compute $A_1=Q_1A_0$, where $Q_1$ is a product of Givens rotations annihilating the elements $2,\ldots,m$ of the first row. Similarly, given $A_{k-1}$ having zeroed out the "lower trapezoid" in the first $k-1$ rows, you compute $A_k=Q_kA_{k-1}$, where $Q_k$ are again Givens rotations annihilating the rows $k+1,\ldots,m$ of the column $k$ of $A_{k-1}$. You repeat the steps until $k=\min\{m,n\}$.
If $A$ has full rank and, say, $m\geq n$, this way you get a decomposition $A=QR$, where $Q\in\mathbb{R}^{m\times m}$ is orthogonal and $R\in\mathbb{R}^{m\times n}$ has the structure $$ R=\begin{bmatrix}\tilde{R} \\ 0\end{bmatrix}, $$ where $\tilde{R}\in\mathbb{R}^{n\times n}$ is upper triangular.
Note that if $Q=[\tilde{Q},\hat{Q}]$, where $\tilde{Q}\in\mathbb{R}^{m\times n}$, then $$ A = QR = [\tilde{Q},\hat{Q}]\begin{bmatrix}\tilde{R} \\ 0\end{bmatrix} = \tilde{Q}\tilde{R}, $$ so if you want to get the "economy" factors, simply take the first $n$ columns of $Q$ and first $n$ rows of $R$.
It's is useful to think of Givens rotations in $\mathbb{R}^2$ "plane". To make zeros in a 2-vector $[\alpha,\beta]^T$ by a rotation $$ \begin{bmatrix}c & -s \\ s & c\end{bmatrix}\begin{bmatrix}\alpha\\\beta\end{bmatrix}=\begin{bmatrix}r \\ 0\end{bmatrix}, $$ you take $c=\alpha/r$ and $s=-\beta/r$, where $r=\sqrt{\alpha^2+\beta^2}$. So in your example with $$ A = \begin{bmatrix} 1 & -2 & 3 \\ 1 & -3 & 5 \\ 2 & 3 & 1 \\ -3 & 4 & 2\\ \end{bmatrix}, $$ it is useful to think about annihilating the bottom-left element using the third row as if you want to do the above thing on the vector [2,-3]^T. Hence the proper choice of $c$ and $s$ is $$ c = 2 / r, \quad s = 3 / r, \quad r = \sqrt{2^2+(-3)^2} = \sqrt{13}. $$