Proving that a product of matrices invertible
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 &gt; 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$.

Oriol 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&gt;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 &gt; 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&lt;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&gt;M$, your assertion that Cy can't be zero is false.



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

Suppose $M=2,N=3$

$$
\begin{bmatrix}
1 &amp; 0 &amp; 1 \\
0 &amp; 1 &amp; 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.



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&gt;M$ which I proved was not invertible in the first case.

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