QR decomposition with permutation matrix

[mathmari]

Hey! :giggle:

At the QR-decomposition with permutation matrix is the matrix $R$ equal to $R=G_3^{-1}P_1G_2^{-1}P_0G_1^{-1}A$ or $G_3P_1G_2P_0G_1A=R$? Which is the correct one? Or are these two equivalent?
In general, it holds that $QR=PA$, right?

:unsure:

 

[I like Serena]

At the QR-decomposition with permutation matrix is the matrix $R$ equal to $R=G_3^{-1}P_1G_2^{-1}P_0G_1^{-1}A$ or $G_3P_1G_2P_0G_1A=R$? Which is the correct one? Or are these two equivalent?

Hey mathmari!

It depends on how we define the $G_i$ and $P_j$ to say which one we should use.
The important part is that we get indeed a right upper matrix when we multiply them.
Other than that, those 2 expressions are equivalent but not the same.

In general, it holds that $QR=PA$, right?

According to wiki, we have $QR=AP$.

 

[mathmari]

I have done the following : \begin{align*}\begin{pmatrix}3 & 1 & -3 & 2 \\ -2 & 1 & 0 & 0 \\ 2 & -2 & 4 & 1 \\ 0 & -1 & -1 & 3\end{pmatrix} & \ \overset{Z_2:Z_2+\frac{2}{3}\cdot Z_1}{\longrightarrow} \ \begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & \frac{5}{3} & -2 & \frac{4}{3} \\ 2 & -2 & 4 & 1 \\ 0 & -1 & -1 & 3\end{pmatrix} \\ & \overset{Z_3:Z_3-\frac{2}{3}\cdot Z_1}{\longrightarrow} \begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & \frac{5}{3} & -2 & \frac{4}{3} \\ 0 & -\frac{8}{3} & 6 & -\frac{1}{3} \\ 0 & -1 & -1 & 3\end{pmatrix} \\ & \overset{Z_2\leftrightarrow Z_3}{\longrightarrow} \begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & -\frac{8}{3} & 6 & -\frac{1}{3} \\ 0 & \frac{5}{3} & -2 & \frac{4}{3} \\ 0 & -1 & -1 & 3\end{pmatrix} \\ & \overset{Z_3:Z_3+\frac{5}{8}\cdot Z_2}{\longrightarrow} \begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & -\frac{8}{3} & 6 & -\frac{1}{3} \\ 0 & 0 & \frac{7}{4} & \frac{9}{8}\\ 0 & -1 & -1 & 3\end{pmatrix} \\ & \overset{Z_4:Z_4-\frac{3}{8}\cdot Z_2}{\longrightarrow} \begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & -\frac{8}{3} & 6 & -\frac{1}{3} \\ 0 & 0 & \frac{7}{4} & \frac{9}{8}\\ 0 & 0 & -\frac{13}{4} & \frac{25}{8}\end{pmatrix} \\ & \overset{Z_3 \leftrightarrow Z_4}{\longrightarrow} \begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & -\frac{8}{3} & 6 & -\frac{1}{3} \\ 0 & 0 & -\frac{13}{4} & \frac{25}{8} \\ 0 & 0 & \frac{7}{4} & \frac{9}{8} \end{pmatrix} \\ & \overset{Z_4 : Z_4+\frac{7}{13}\cdot Z_3}{\longrightarrow} \begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & -\frac{8}{3} & 6 & -\frac{1}{3} \\ 0 & 0 & -\frac{13}{4} & \frac{25}{8} \\ 0 & 0 & 0 & \frac{73}{26} \end{pmatrix} \end{align*}
After the Gauss elimination method do we get the matrix $R=G_3^{-1}P_1G_2^{-1}P_0G_1^{-1}A$ : \begin{equation*}R=\begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & -\frac{8}{3} & 6 & -\frac{1}{3} \\ 0 & 0 & -\frac{13}{4} & \frac{25}{8} \\ 0 & 0 & 0 & \frac{73}{26} \end{pmatrix} \approx\begin{pmatrix}3 & 1 & -3 & 2 \\ 0 & -2,6667 & 6 & -0,3333 \\ 0 & 0 & -3,25 & 3,125 \\ 0 & 0 & 0 & 2,8077 \end{pmatrix}\end{equation*}
From the steps of Gauss method we get the matrices \begin{equation*}G_1=\begin{pmatrix}1 & 0 & 0 &0 \\ \frac{2}{3} & 1 & 0 & 0 \\ -\frac{2}{3} & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix} \ , \ G_2=\begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & \frac{5}{8} & 1 & 0 \\ 0 & -\frac{3}{8} & 0 & 1\end{pmatrix} \ \text{ and } \ G_3=\begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & \frac{7}{13} & 1\end{pmatrix}\end{equation*}
We have the permutation matrices \begin{equation*}P_0=\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \ \text{ and } \ P_1=\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\end{equation*} We have \begin{equation*}P=P_1\cdot P_0=\begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}\end{equation*}
We have that:
\begin{equation*}G_3\cdot P_1\cdot G_2\cdot P_0\cdot G_1\cdot A = R \Rightarrow A=\left (G_3\cdot P_1\cdot G_2\cdot P_0\cdot G_1\right )^{-1}\cdot R \Rightarrow PA=P\cdot \left (G_3\cdot P_1\cdot G_2\cdot P_0\cdot G_1\right )^{-1}\cdot R\end{equation*} So we have that $PA=QR$ with $Q=P\cdot \left (G_3\cdot P_1\cdot G_2\cdot P_0\cdot G_1\right )^{-1}$.
\begin{align*}Q&=P\cdot \left (G_3\cdot P_1\cdot G_2\cdot P_0\cdot G_1\right )^{-1}=P\cdot G_1^{-1}\cdot P_0^{-1}\cdot G_2^{-1}\cdot P_1^{-1}\cdot G_3^{-1}\\ & = \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 &0 \\ -\frac{2}{3} & 1 & 0 & 0 \\ \frac{2}{3} & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & -\frac{5}{8} & 1 & 0 \\ 0 & \frac{3}{8} & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{pmatrix}\cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & -\frac{7}{13} & 1\end{pmatrix} \\ & = \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 &0 \\ -\frac{2}{3} & 1 & 0 & 0 \\ \frac{2}{3} & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}\cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & -\frac{5}{8} & 1 & 0 \\ 0 & \frac{3}{8} & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -\frac{7}{13} & 1 \\ 0 & 0 & 1 & 0\end{pmatrix} \\ & = \begin{pmatrix}1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 &0 \\ -\frac{2}{3} & 1 & 0 & 0 \\ \frac{2}{3} & 0 & 1 & 0 \\ 0 & 0 & 0 & 1\end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & -\frac{5}{8} & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & \frac{3}{8} & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -\frac{7}{13} & 1 \\ 0 & 0 & 1 & 0\end{pmatrix} \\ & = \begin{pmatrix}1 & 0 & 0 &0 \\ \frac{2}{3} & 0 & 1 & 0 \\ 0 & 0 & 0 & 1
\\ -\frac{2}{3} & 1 & 0 & 0\end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & -\frac{5}{8} & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & \frac{3}{8} & 0 & 1\end{pmatrix}\cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -\frac{7}{13} & 1 \\ 0 & 0 & 1 & 0\end{pmatrix} \\ & = \begin{pmatrix}1 & 0 & 0 &0 \\ \frac{2}{3} & 1 & 0 & 0 \\ 0 & \frac{3}{8} & 0 & 1
\\ -\frac{2}{3} & -\frac{5}{8} & 1 & 0\end{pmatrix} \cdot \begin{pmatrix}1 & 0 & 0 &0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & -\frac{7}{13} & 1 \\ 0 & 0 & 1 & 0\end{pmatrix} \\ & = \begin{pmatrix}1 & 0 & 0 &0 \\ \frac{2}{3} & 1 & 0 & 0 \\ 0 & \frac{3}{8} & 1 & 0
\\ -\frac{2}{3} & -\frac{5}{8} & -\frac{7}{13} & 1\end{pmatrix} \\ & \approx \begin{pmatrix}1 & 0 & 0 &0 \\ 0,6667 & 1 & 0 & 0 \\ 0 & 0,375 & 1 & 0
\\ -0,6667 & -0,625 & -0,5385 & 1\end{pmatrix} \end{align*} Which of the expressions of #1 is the correct one? :unsure:

 

[I like Serena]

Which of the expressions of #1 is the correct one?

You have defined the matrices $G_i$ and $P_j$ such that $G_3\cdot P_1\cdot G_2\cdot P_0\cdot G_1\cdot A = R$ haven't you?
So that is the correct expression.
What were you uncertain about? (Wondering)

However, didn't you do an LR-decomposition with permutation rather than a QR-decomposition? :unsure:
Note that the resulting $Q$ is not orthogonal.

 

[mathmari]

You have defined the matrices $G_i$ and $P_j$ such that $G_3\cdot P_1\cdot G_2\cdot P_0\cdot G_1\cdot A = R$ haven't you?
So that is the correct expression.
What were you uncertain about? (Wondering)

So the expression $R=G_3^{-1}P_1G_2^{-1}P_0G_1^{-1}A$ is wrong, isn't it? :unsure:

However, didn't you do an LR-decomposition with permutation rather than a QR-decomposition? :unsure:
Note that the resulting $Q$ is not orthogonal.

Ah yes, it is the LR-decomposition. (Malthe)

 

[I like Serena]

So the expression $R=G_3^{-1}P_1G_2^{-1}P_0G_1^{-1}A$ is wrong, isn't it?

It looks wrong to me yes. :unsure:

 

[mathmari]

It looks wrong to me yes. :unsure:

Ok! Thanks! :geek: