B=Q^TAQ has a LU decomposition

[mathmari]

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:

 

[I like Serena]

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.

 

[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.

So what we need to know is the leading principal minors are not $0$, right? Do we know that? :unsure:

 

[I like Serena]

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?

 

[mathmari]

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:

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:

 

[I like Serena]

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?

 

[mathmari]

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?

 

[I like Serena]

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.

 

[mathmari]

What is the difference between positive definite matrix and strictly positive definite matrix? :unsure:

 

[I like Serena]

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.

 

[mathmari]

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:

 

[I like Serena]

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.

 

[I like Serena]

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: