MHB B=Q^TAQ has a LU decomposition

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Decomposition
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
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
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. 🤔
 
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:
 
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:
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:
 
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? 🤔
 
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?
 
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.
 
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:
 

Similar threads

Back
Top