B=Q^TAQ has a LU decomposition

In summary, the conversation is discussing the implications of a not necessarily symmetric, strictly positive definite matrix $A$ and an orthogonal matrix $Q$ on the existence of an LU decomposition for $B=Q^TAQ$. The conversation explores the possibility of a counterexample to the statement that all leading principal minors of $B$ are non-zero, and concludes that the statement is actually a combination of two statements: one stating that a not necessarily symmetric, positive definite matrix always has an LU decomposition, and the other stating that conjugating such a matrix with an orthogonal matrix also preserves the property of having an LU decomposition.
  • #1
mathmari
Gold Member
MHB
5,049
7
Hey! 😊

I saw the below sentence in some notes:

Let $A\in \mathbb{R}^{n\times n}$ be a not necessarily symmetric, strictly positive definite matrix, $x^TAx>0$, $x\neq 0$ und $Q\in \mathbb{R}^{n\times n}$ an orthogonal matrix, then $B=Q^TAQ$ has a LU decomposition.

I want to understand this implication, so I thought that this could hold for the following reason:

Since the matrix $A$ is strictly positive definite matrix, we know that the determinant is always positiv, i.e. not zero.

The determinant of $Q$ and $Q^T$ can neither be zero.

Therefore we get that the determinant of $B$ is not zero.

In this case a LU decomposition exists if the leading principal minors are not $0$, right? :unsure:
 
Mathematics news on Phys.org
  • #2
Hey mathmari!

All true. (Nod)

Moreover, the determinant of $Q$ is either +1 or -1.
We also have that $A$ will have a LU decomposition (if we pick $Q=I$).
Furthermore, $B$ is the representation of $A$ in a different orthonormal basis. Apparently this preserves the property that LU decomposition is possible. 🤔
 
  • #3
Klaas van Aarsen said:
All true. (Nod)

Moreover, the determinant of $Q$ is either +1 or -1.
We also have that $A$ will have a LU decomposition (if we pick $Q=I$).
Furthermore, $B$ is the representation of $A$ in a different orthonormal basis. Apparently this preserves the property that LU decomposition is possible. 🤔

So what we need to know is the leading principal minors are not $0$, right? Do we know that? :unsure:
 
  • #4
mathmari said:
So what we need to know is the leading principal minors are not $0$, right? Do we know that?
I'm not aware of a proposition that says so. (Shake)

So let's approach the problem from the other side and see how far we get with a proof by contradiction (or a proof by counterexample for that matter).

Suppose there is a not necessarily symmetric, strictly positive definite matrix $A$ and orthogonal $Q$ such that $B=Q^T A Q$ does not have an LU decomposition.
Can we find such $A$ and $Q$?

As a first step, suppose $A$ is a 2x2 matrix.
And suppose $A$ has 0 at the left top, so that it has a leading principal minor that is zero, which ensures there is no LU decomposition.
And suppose $Q$ is the identity matrix.
Can we find such an $A$ that is a not necessarily symmetric, strictly positive definite matrix? 🤔
 
Last edited:
  • #5
Klaas van Aarsen said:
I'm not aware of a proposition that says so. (Shake)

Neither I was aware, I found that in some notes that I found online.

Is there an other proposition that it is better to use here? :unsure:
Klaas van Aarsen said:
So let's approach the problem from the other side and see how far we get with a proof by contradiction (or a proof by counterexample for that matter).

Suppose there is a not necessarily symmetric, strictly positive definite matrix $A$ and orthogonal $Q$ such that $B=Q^T A Q$ does not have an LU decomposition.
Can we find such $A$ and $Q$?

As a first step, suppose $A$ is a 2x2 matrix.
And suppose $A$ has 0 at the left top, so that it has a leading principal minor that is zero, which ensures there is no LU decomposition.
And suppose $Q$ is the identity matrix.
Can we find such an $A$ that is a not necessarily symmetric, strictly positive definite matrix? 🤔

So that $A$ is strictly positive definite all eigenvalues have to be positive. So let $A=\begin{pmatrix}0 & -1 \\ 1 & 2\end{pmatrix}$. This matrix has the eigenvalue $1$. :unsure:
 
  • #6
mathmari said:
So that $A$ is strictly positive definite all eigenvalues have to be positive. So let $A=\begin{pmatrix}0 & -1 \\ 1 & 2\end{pmatrix}$. This matrix has the eigenvalue $1$.

That's a counter example isn't it?
So the statement is the OP is false isn't it? 🤔
 
  • #7
Klaas van Aarsen said:
That's a counter example isn't it?
So the statement is the OP is false isn't it? 🤔

Aa so the sentence is not true at all?
 
  • #8
mathmari said:
Aa so the sentence is not true at all?
I don't think so.
We found a counter example after all.
Unless we are overlooking something of course, but at this time I don't see what. 🤔
I was hoping it would help us to figure out why we couldn't find a counter example, but ah well, it happens.
 
  • #9
What is the difference between positive definite matrix and strictly positive definite matrix? :unsure:
 
  • #10
mathmari said:
What is the difference between positive definite matrix and strictly positive definite matrix?
It's the same thing. The adjective 'strictly' merely emphasizes that we are really talking about greater than zero, and that we are not talking about positive semi-definite. 🤔
 
  • #11
If $B$ is positive definite then all leading principal minors are nonzero and then the matrix has an LU decomposition.

Is this implication correct?

To show that $B$ is positive definite do we have to show that $x^TBx>0$ ? Or also that $B$ is symmetric?

For the first one we have:
$$x^TBx=x^TQ^TAQx=(Qx)^TA(Qx) >0$$

If we have to shwo also that $B$ is symmetric, I have done the following:
$$B^T=(Q^TAQ)^T=Q^TA^TQ$$
But how can we continue wihout knowing if $A$ is symmetric or not?

:unsure:
 
Last edited by a moderator:
  • #12
I think I had it wrong after all.
The matrix $\begin{pmatrix}0&-1\\1&2\end{pmatrix}$ has only eigenvalue 1, but that is not enough to make it positive definite.
Consider that $\begin{pmatrix}1&0\end{pmatrix}\begin{pmatrix}0&-1\\1&2\end{pmatrix}\begin{pmatrix}1\\0\end{pmatrix}=0$, which implies that it is not positive definite.

So positive eigenvalues are not enough to make a matrix positive definite. I think it also has to be symmetric.
However, it appears that if a matrix is positive definite, then even if it is not symmetric, it does have an LU decomposition.

In other words, we don't need to distinguish whether either matrix is symmetric or not. 😅

Either way, the statement in the OP is actually a combination of 2 statements.
The first is that a not necessarily symmetric, positive definite matrix always has an LU decomposition.
The second is that if such a matrix is conjugated with an orthogonal matrix, it has again an LU decomposition.

You have just proven the second part, which leaves the first part. 🤔
 
Last edited:
  • #13
Let's try to prove that a not necessarily symmetric, positive definite matrix $A$ always has an LU decomposition. 🤔

We already know that this is the case iff $A$ is invertible with leading principle minors that are non-zero.
A positive definite matrix is invertible.

Let's try a proof by contradiction.
Suppose $A$ has a leading principle minor $A_k$ that has determinant zero.
Then there must be a vector $x_k$ such $A_k x_k=0$.
Suppose we fill out $x_k$ with zeroes to get a vector $x_n$. Then $A x_n=0$ isn't it? And therefore $x_n^T A x_n=0$ as well.
This implies that $A$ is not positive definite, which is a contradiction.
Therefore $A$ is invertible with leading principle minors that are non-zero.

Thus $A$ has an LU decomposition. :geek:
 

FAQ: B=Q^TAQ has a LU decomposition

What is LU decomposition?

LU decomposition is a method used in linear algebra to factorize a matrix into a lower triangular matrix (L) and an upper triangular matrix (U). This decomposition is useful in solving systems of linear equations and finding inverses of matrices.

How is LU decomposition related to B=Q^TAQ?

B=Q^TAQ is a form of similarity transformation, where Q is an orthogonal matrix and A is a square matrix. LU decomposition of A can be used to find the similarity transformation of B, which can help in solving problems involving B.

What is the significance of having a LU decomposition for B=Q^TAQ?

Having a LU decomposition for B=Q^TAQ means that the matrix A can be easily factorized into two triangular matrices, which simplifies the computations involved in solving problems involving B. This decomposition also allows for efficient computation of the determinant and inverse of A.

Is LU decomposition unique for B=Q^TAQ?

No, LU decomposition is not unique for B=Q^TAQ. This is because there can be different choices for the orthogonal matrix Q and the triangular matrices L and U that can satisfy the equation B=Q^TAQ. However, the diagonal elements of L and U are unique.

Can LU decomposition be used for non-square matrices?

No, LU decomposition can only be applied to square matrices. For non-square matrices, other methods such as QR decomposition or singular value decomposition (SVD) can be used for factorization.

Similar threads

Replies
2
Views
1K
Replies
13
Views
2K
Replies
5
Views
2K
Replies
1
Views
2K
Replies
1
Views
905
Replies
6
Views
9K
Replies
6
Views
1K
Replies
5
Views
3K
Back
Top