QR decomposition with permutation matrix

In summary, QR decomposition with permutation matrix is a mathematical technique used to factorize a matrix into an orthogonal matrix and an upper triangular matrix, with the additional use of a permutation matrix. This method differs from standard QR decomposition by incorporating the use of a permutation matrix, which helps improve the numerical stability and efficiency of the decomposition. The purpose of using a permutation matrix in QR decomposition is to improve the conditioning of the triangular matrix and reduce the number of operations needed. This decomposition is useful in solving linear systems of equations, as well as in various fields such as engineering, physics, and statistics. It also has applications in data compression, signal processing, image processing, and machine learning algorithms.
  • #1
mathmari
Gold Member
MHB
5,049
7
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:
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
mathmari said:
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. 🤔

mathmari said:
In general, it holds that $QR=PA$, right?
According to wiki, we have $QR=AP$. 🤔
 
  • #3
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:
 
  • #4
mathmari said:
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.
 
Last edited:
  • #5
Klaas van Aarsen said:
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:
Klaas van Aarsen said:
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)
 
  • #6
mathmari said:
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:
 
  • #7
Klaas van Aarsen said:
It looks wrong to me yes. :unsure:

Ok! Thanks! :geek:
 

Related to QR decomposition with permutation matrix

1. What is QR decomposition with permutation matrix?

QR decomposition with permutation matrix is a method used in linear algebra to decompose a matrix into two matrices, Q and R. The Q matrix is an orthogonal matrix (meaning its columns are orthogonal to each other) and the R matrix is an upper triangular matrix. The permutation matrix is used to rearrange the columns of the original matrix before the QR decomposition is performed.

2. What is the purpose of using a permutation matrix in QR decomposition?

The purpose of using a permutation matrix in QR decomposition is to improve the stability and accuracy of the decomposition process. It allows for the rearrangement of the columns of the original matrix to minimize round-off errors and prevent the creation of very small or large numbers in the resulting matrices.

3. How is a permutation matrix created?

A permutation matrix is created by rearranging the rows of an identity matrix. The rows are rearranged according to the desired permutation, and the resulting matrix is a permutation matrix. For example, if the desired permutation is (2,1,3), the first row of the identity matrix would become the second row of the permutation matrix, the second row would become the first row, and the third row would remain unchanged.

4. What is the significance of the Q and R matrices in QR decomposition with permutation matrix?

The Q and R matrices in QR decomposition with permutation matrix have important properties that make them useful in various applications. The Q matrix is orthogonal, meaning its columns are perpendicular to each other, and it can be used to solve systems of linear equations. The R matrix is upper triangular, making it easy to compute determinants and inverses.

5. What are the advantages of using QR decomposition with permutation matrix over other matrix decomposition methods?

QR decomposition with permutation matrix has several advantages over other matrix decomposition methods. It is more stable and accurate, as the permutation matrix helps to reduce round-off errors. It is also more efficient, as it requires fewer operations to decompose a matrix compared to other methods such as LU decomposition. Additionally, the Q and R matrices have useful properties that make them valuable in various applications.

Similar threads

  • Linear and Abstract Algebra
Replies
7
Views
788
  • Linear and Abstract Algebra
Replies
1
Views
1K
  • Linear and Abstract Algebra
Replies
5
Views
2K
  • Linear and Abstract Algebra
Replies
28
Views
3K
  • Linear and Abstract Algebra
Replies
15
Views
4K
  • Linear and Abstract Algebra
2
Replies
52
Views
2K
  • Linear and Abstract Algebra
Replies
1
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
1K
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
6
Views
1K
Back
Top