Proving that a product of matrices invertible

Question

Given $R_x$ a Positive Definite (PD) covariance matrix of size $M\times M$ and $C$ a full rank $M \times N$ matrix, I want to prove that $C^* R_x^{-1} C$ is invertible to derive the Linearly Constrained Minimum Variance Beamforming.

My ideas so far:

1. Since $R_x$ commutes with its adjoint, it can be written using the eigendecomposition $R_x = U \Lambda U^*$
2. $R_x$ is PD, $R_x^{-1}$ is also PD since $\lambda_i > 0 \Longrightarrow \lambda_i^{-1} > 0$
3. Matrix $U$ defines an orthonormal basis and $C$ is full rank. Can view $U^* C$ as a projection onto this basis.

Answer 1

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

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

---

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.

---

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.

Answer 2

Thanks for your answer Cedron! Taking your same assumption $N \leq M$, and by definition of PD, $x^* R_x^{-1} x > 0\quad \forall x \in \mathbb{R}^M \setminus \{0\}$ and since $C$ is full rank $\dim (\mathcal{R}(C)) = \min(M,N)= N$. By the rank-nulity theorem, $\dim (\mathcal{R}(C)) + \dim(\mathcal{N}(A))=N$, so we have that the null-space is trivial. This means the projection $\tilde{x} := C y \neq 0\quad \forall y \in \mathbb{R}^N \setminus \{0\}$. Hence \begin{align} \tilde{x} = 0 \Longleftrightarrow y = 0 \tag{1} \end{align} Now we can see that $\tilde{x}^* R_x^{-1} \tilde{x} > 0\quad \forall \tilde{x} \neq 0$ following from PD of $R_x^{-1}$ so using the latter and (1), \begin{align} \tilde{x}^* R_x^{-1} \tilde{x} := y^* C^* R_x^{-1} C y > 0\quad \forall y \in \mathbb{R}^N \setminus \{0\} \tag{2} \end{align} and thus $C^* R_x^{-1} C$ is PD and hence invertible.