Different method for QR decomposition - is it possible

Question

This method could also possibly be applicable to matrices of higher dimension, but for the simplicity of my question i will only ask it for $2$x$2$matrices.

Suppose $A=\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22}\end{pmatrix}$. and we are given this matrix. meaning $a_{ij}$ are known to us.

We know from QR factorizations that there are matrices $Q,R$ such that $Q$ is orthonornal, and $R$ is upper triangular, such that

$QR=\begin{pmatrix} q_{11} & q_{12} \\ q_{21} & q_{22} \end{pmatrix} \begin{pmatrix} r_{11} & r_{12} \\ 0 & r_{22}\end{pmatrix}=\begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}=A$

From this we can infer

$q_{11}r_{11}=a_{11}$

$q_{11}r_{12}+q_{12}r_{22}=a_{12}$

$q_{21}r_{11}=a_{21}$

$q_{21}r_{12}+q_{22}r_{22}=a_{22}$

These are $4$ equations with $7$ variables.

From the orthonormality of $Q$, we can also infer the equations

$q_{11}^2+q_{21}^2=1$

$q_{12}^2+q_{22}^2=1$

$q_{11}q_{12}+q_{21}q_{22}=0$

Those are $3$ more equations. now we have a total of $7$ equations and $7$ variables.

But those are equations are non linear.

Is it possible to solve this non linear system? would it still be possible if I increase the dimensions of the matrix $A$?

Answer 1

I am sorry if this is not what you are looking for (I suppose I did not understand your question). There are several algorithmic procedures to solve your nonlinear system of equations. One of them is the Gram-Schmidt process:

In your case, letting $A = (\alpha_1\ \alpha_2)$, i.e. $$\alpha_1 = \left(\matrix{a_{11} \\ a_{21}}\right) \qquad \alpha_2 = \left(\matrix{a_{12} \\ a_{22}}\right)$$ And running the following algorithm $$u_1 = \alpha_1, \quad e_1 = \frac{u_1}{\|u_1\|}$$ $$u_2 = \alpha_2-(\alpha_2\cdot e_1)e_1, \quad e_2 = \frac{u_2}{\|u_2\|}$$

you obtain the desired solution by equating $$e_1 = \left(\matrix{q_{11} \\ q_{21}}\right) \qquad e_2 = \left(\matrix{q_{12} \\ q_{22}}\right)$$ and $r_{11} = \alpha_1\cdot e_1$, $r_{12} = \alpha_2\cdot e_1$, $r_{22} = \alpha_2\cdot e_2$.

Scaling (increasing the dimension of $A$) is straigthforward (see the short notes referenced above).

Answer 2

Solving the equations as nonlinear ones? We can certainly do it, and it may surprise you to learn that no nonlinear "tricks" are necessary. But let's start by simplifying things a little. We don't need to solve for the $r$ values alongside the $q$ ones, because all equations are linear in $r$. So let's start by noting that $$ \begin{align} \begin{pmatrix} q_{11} & q_{12} \\ q_{21} & q_{22} \end{pmatrix} \begin{pmatrix} r_{12} \\ r_{22}\end{pmatrix}&=\begin{pmatrix} a_{12} \\ a_{22} \end{pmatrix}\\ \begin{pmatrix}r_{12}\\r_{22}\end{pmatrix}&=\begin{pmatrix}q_{11}a_{12}+q_{21}a_{22}\\q_{12}a_{12}+q_{22}a_{22}\end{pmatrix} \end{align} $$ where I've used orthogonality to avoid inverses. We can also note that $r_{11}=a_{11}/q_{11}$, and so $q_{21}a_{11}=q_{11}a_{21}$. This allows us to write our remaining three equations as $$ q_{11}^2+\frac{a_{21}^2q_{11}^2}{a_{11}^2}=1\\ q_{12}^2+q_{22}^2=1\\ q_{11}q_{12}+\frac{a_{21}q_{11}q_{22}}{a_{11}}=0 $$ The first equation defines $q_{11}$ to be $$ q_{11}=\frac{\pm a_{11}}{\sqrt{a_{11}^2+a_{21}^2}} $$ If we assume $a_{11}\neq 0$, then we may divide the third equation by $q_{11}$ to get $$ q_{12}=-\frac{a_{21}q_{22}}{a_{11}} $$ From here, it should be obvious what is going to happen. All four $q$ variables take the same form. Taking the "positive" option (same sign as $a_{11}$) for $q_{11}$, we can write $Q$ as $$ Q=\begin{pmatrix}\frac{a_{11}}{\sqrt{a_{11}^2+a_{21}^2}} & \frac{a_{21}}{\sqrt{a_{11}^2+a_{21}^2}}\\\frac{a_{21}}{\sqrt{a_{11}^2+a_{21}^2}} & \frac{-a_{11}}{\sqrt{a_{11}^2+a_{21}^2}}\end{pmatrix} $$ And from here, we can see that our $R$ matrix is $$ R=\begin{pmatrix}\sqrt{a_{11}^2+a_{21}^2} & \frac{a_{11}a_{12}+a_{21}a_{22}}{\sqrt{a_{11}^2+a_{21}^2}}\\ 0 & \frac{a_{21}a_{12}-a_{11}a_{22}}{\sqrt{a_{11}^2+a_{21}^2}}\end{pmatrix} $$

Solving it numerically by this method would be counter-productive, as you'd have to invert a $7\times 7$ matrix repeatedly until sufficient convergence is acquired. The system you would be iteratively solving, if you were to use Newton's method, is $$ \begin{pmatrix}r_{11}&0&0&0&q_{11}&0&0\\r_{12}&r_{22}&0&0&0&q_{11}&q_{12}\\0&0&r_{11}&0&q_{21}&0&0\\0&0&r_{12}&r_{22}&0&q_{21}&q_{22}\\2q_{11}&0&2q_{21}&0&0&0&0\\0&2q_{12}&0&2q_{22}&0&0&0\\q_{12}&q_{11}&q_{22}&q_{21}&0&0&0\end{pmatrix}\begin{pmatrix}\Delta q_{11}\\\Delta q_{12}\\\Delta q_{21}\\\Delta q_{22}\\\Delta r_{11}\\\Delta r_{12}\\\Delta r_{22}\end{pmatrix}=\begin{pmatrix}a_{11}-q_{11}r_{11}\\a_{12}-q_{11}r_{12}-q_{12}r_{22}\\a_{21}-q_{21}r_{11}\\a_{22}-q_{21}r_{21}-q_{22}r_{22}\\1-q_{11}^2-q_{21}^2\\1-q_{12}^2-q_{22}^2\\-q_{11}q_{12}-q_{21}q_{22}\end{pmatrix} $$ which is obviously vastly more complicated than the original matrix.