# Proof of Congruence Transformation

1. May 18, 2009

### azizz

Consider the following statement

Let T (size: nxm) be a complex matrix. Then if A of dimension nxn is positive semidefinite then T*AT >= 0.

Now I was wondering if the converse is true aswel? In my math book they used the converse statement to proof something, but is it possible to say that if T*AT >= 0 (positive semidefinite) then A>= 0?

Note: I used the symbol * to indicate the Hermittian.

Someone got some tips for me?

2. May 18, 2009

### jbunniii

It's not true in general. Suppose, for example, that T is n x 1. So it's a particular column vector; let's call it $$x_0$$ to emphasize that fact.

Then in that case, T*AT >= 0 means simply that

$$x_0^* A x_0 \geq 0$$ (scalar inequality)

for that specific $$x_0$$ (or any scalar multiple of $$x_0$$). But in order to conclude that A is positive semidefinite, you would need

$$x^* A x \geq 0$$

for EVERY column vector x.

: A sufficient condition for the conclusion you desire would be that T must be surjective. Do you see why?

3. May 18, 2009

### azizz

Thanks for the fast replay. Let me see if i got.

A>=0 implies T*AT>=0 if T has full column rank. That means that for every column (i) of T we have Ti*ATi>=0.

If T did not have full column rank then there are linear dependent columns for which it does not hold that Ti*ATi>=0.

4. May 18, 2009

### jbunniii

No, that's not right. A >= 0 implies T*AT >= 0 for ANY complex n x m matrix T.

Why is this? Because

x*(T*AT)x = (Tx)*A(Tx) = y*Ay >= 0 because A is positive semidefinite

(here I have defined y = Tx for added clarity)

You asked about the converse: when does T*AT >= 0 imply A >= 0?

A sufficient condition is for T to be surjective, i.e., for T to have full ROW rank. (Not full column rank! The n x 1 example I gave in the last post has full column rank, but the desired result does not hold.)

Why is it sufficient for T to be surjective? Let y be any n x 1 vector. We want

y*Ay >= 0.

Since T is surjective, there exists a (m x 1) vector x such that y = Tx.

Then:

y*Ay = (Tx)*A(Tx) = x*(T*AT)x* >= 0 because T*AT is positive semidefinite. QED.

The next natural question is: is it also NECESSARY for T to be surjective? I'll let you think about that one.