Return to Answer

Oriole B inserted:

Clearly, $y \ne 0$ yet $Cy$ is. The rank of $C$ is 2.

Oriol B inserted:

Clearly, $y \ne 0$ yet $Cy$ is. The rank of $C$ is 2.

Response to OriolB's "Of course your assumption ..." comment:

By "your assumption" you mean my second case of $N \le M$. I didn't get that, sorry.

It seems that you have removed the "less than or" part of step 5, thus proving it invertible. I had left it hanging since you had said you were only interested in $N>M$ which I proved was not invertible in the first case.

For the $N>M$ case, perhaps a pseudo-inverse will suffice for your greater purposes.

I'm not sure where your misconception arises. Here is a concrete counter example:

Suppose $M=2,N=3$

$$ \begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$

$$ Cy = 0 $$

Clearly, $y \ne 0$ yet $Cy$ is. The rank of $C$ is 2.

First, this question is probably better for MATH.SE, but I'll give it a shot.

It's been a long long time since I did this stuff.

If $N > M$:

1. $C^*$ has rank M.

2. $R_x^{-1}$ has rank M. (or it wouldn't exist as an inverse)

3. Therefore $C^*R_x^{-1}$ has rank M, since $R_x^{-1}$ is a full rank square matrix.

4. $C$ has rank M

5. $C^*R_x^{-1}C$ has rank less than or equal to M and is NxN.

6. $C^*R_x^{-1}C$ is a not a full rank square matrix and is thus not invertible.

If $N \le M$:

1. $C^*$ has rank N.

2. $R_x^{-1}$ has rank M. (or it wouldn't exist as an inverse)

3. Therefore $C^*R_x^{-1}$ has rank N.

4. $C$ has rank N

5. $C^*R_x^{-1}C$ has rank less than or equal to N and is NxN.

6. $C^*R_x^{-1}C$ could be full rank square matrix and is thus could be invertible.

At this point, I am not sure what is required for $C^*R_x^{-1}C$ to have rank N. I have narrowed the results, but not fully answered your question.

Gosh, I hope I have this right.

https://math.stackexchange.com/questions/1524444/connection-between-rank-and-positive-definiteness

https://math.stackexchange.com/questions/272049/rank-of-matrix-ab-when-a-and-b-have-full-rank

Starting with another disclaimer: Ordinarily I don't answer questions here unless I am fairly rock solid in my understanding of the subject matter. In this case, as the edit history shows, I am muddling about quite a bit.

I had to look up the Frobenius inequality and I understand how you get $ M \leq \text{rank}(C^* R_x^{-1} C) $ from it in the $N \ge M$ case. I still don't see how it could be greater than $M$.

Oriole B inserted:

Regarding your question about the Frobenius inequality, I derived it as follows: $\text{rank}(C^* R_x^{-1} C) \geq \text{rank}(C^*R_x^{-1}) + \text{rank}(R_x^{-1}C) - \text{rank}(R_x^{-1})=\text{rank}(C^*R_x^{-1}) + \text{rank}(R_x^{-1}C) - M $. And by now using Sylvester's rank inequality, we get $\text{rank}(C^*R_x^{-1}C) \geq \text{rank}(C^*R_x^{-1}) + \text{rank}(R_x^{-1}C) - M \geq rank(C^*) + \text{rank}(R_x^{-1}) - M + \text{rank}(R_x^{-1}) + \text{rank}(C) - M - M = \text{rank}(C^*) + \text{rank}(C) - M = M $ and the last inequality follows by the assumption.

I do feel confident in my $N>M$ argument, but thanks to this addition, you can change #5 to saying the rank of $C^* R_x^{-1} C$ is $M$. However, if $ N > M $, then the rank is still smaller than the dimension and it is still not invertible. It should be with $N=M$.

I'm still mucking with the $N \le M$ case. Using Frobenius you get $ \text{rank}(C^* R_x^{-1} C) \ge 2N - M $. For $N=M$ it looks like the result will have rank N and be NxN so it will be invertible.

Since the $N<M$ case is of no interest to you I am stopping for a while on this.

https://artofproblemsolving.com/community/c364309h1480887_rank_inequalities_and_some_consequences

Another update:

I think I found the first flaw in your argument. I mean, there has to be one in order for mine to be correct. ;-)

$C$ is $M$x$N$ and $y$ is $N$x$1$ so $Cy$ is $M$x$1$.

$Cy$ can be interpreted as the linear combination of $N$ $M$ length vectors. If $N>M$, your assertion that Cy can't be zero is false.

First, this question is probably better for MATH.SE, but I'll give it a shot.

It's been a long long time since I did this stuff.

If $N > M$:

1. $C^*$ has rank M.

2. $R_x^{-1}$ has rank M. (or it wouldn't exist as an inverse)

3. Therefore $C^*R_x^{-1}$ has rank M, since $R_x^{-1}$ is a full rank square matrix.

4. $C$ has rank M

5. $C^*R_x^{-1}C$ has rank less than or equal to M and is NxN.

6. $C^*R_x^{-1}C$ is a not a full rank square matrix and is thus not invertible.

If $N \le M$:

1. $C^*$ has rank N.

2. $R_x^{-1}$ has rank M. (or it wouldn't exist as an inverse)

3. Therefore $C^*R_x^{-1}$ has rank N.

4. $C$ has rank N

5. $C^*R_x^{-1}C$ has rank less than or equal to N and is NxN.

6. $C^*R_x^{-1}C$ could be full rank square matrix and is thus could be invertible.

At this point, I am not sure what is required for $C^*R_x^{-1}C$ to have rank N. I have narrowed the results, but not fully answered your question.

Gosh, I hope I have this right.

https://math.stackexchange.com/questions/1524444/connection-between-rank-and-positive-definiteness

https://math.stackexchange.com/questions/272049/rank-of-matrix-ab-when-a-and-b-have-full-rank

Starting with another disclaimer: Ordinarily I don't answer questions here unless I am fairly rock solid in my understanding of the subject matter. In this case, as the edit history shows, I am muddling about quite a bit.

I had to look up the Frobenius inequality and I understand how you get $ M \leq \text{rank}(C^* R_x^{-1} C) $ from it in the $N \ge M$ case. I still don't see how it could be greater than $M$.

Oriole B inserted:

Regarding your question about the Frobenius inequality, I derived it as follows: $\text{rank}(C^* R_x^{-1} C) \geq \text{rank}(C^*R_x^{-1}) + \text{rank}(R_x^{-1}C) - \text{rank}(R_x^{-1})=\text{rank}(C^*R_x^{-1}) + \text{rank}(R_x^{-1}C) - M $. And by now using Sylvester's rank inequality, we get $\text{rank}(C^*R_x^{-1}C) \geq \text{rank}(C^*R_x^{-1}) + \text{rank}(R_x^{-1}C) - M \geq rank(C^*) + \text{rank}(R_x^{-1}) - M + \text{rank}(R_x^{-1}) + \text{rank}(C) - M - M = \text{rank}(C^*) + \text{rank}(C) - M = M $ and the last inequality follows by the assumption.

I do feel confident in my $N>M$ argument, but thanks to this addition, you can change #5 to saying the rank of $C^* R_x^{-1} C$ is $M$. However, if $ N > M $, then the rank is still smaller than the dimension and it is still not invertible. It should be with $N=M$.

I'm still mucking with the $N \le M$ case. Using Frobenius you get $ \text{rank}(C^* R_x^{-1} C) \ge 2N - M $. For $N=M$ it looks like the result will have rank N and be NxN so it will be invertible.

Since the $N<M$ case is of no interest to you I am stopping for a while on this.

https://artofproblemsolving.com/community/c364309h1480887_rank_inequalities_and_some_consequences

Another update:

I think I found the first flaw in your argument. I mean, there has to be one in order for mine to be correct. ;-)

$C$ is $M$x$N$ and $y$ is $N$x$1$ so $Cy$ is $M$x$1$.

$Cy$ can be interpreted as the linear combination of $N$ $M$ length vectors (the columns of C). If $N>M$, your assertion that Cy can't be zero is false.