# Proving that a product of matrices invertible

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.

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

• @OriolB Your comment is hard to decipher. I get how you derived it, I'm just a bit puzzled about what it says. – Cedron Dawg Nov 22 '19 at 22:04
• Sorry about that @cedron, I incorporated my comment in your reply inside the yellow box since it was hard to format as a comment. – Oriol B Nov 22 '19 at 22:06
• @OriolB Yeah, you did so while I was editing, so you must have missed my edit. I have left it there, but I think it would have been better for you to append your own answer so no one is confused about authorship. I have re-inserted my edit. – Cedron Dawg Nov 22 '19 at 22:11
• @OriolB Ponder my latest appendum. – Cedron Dawg Nov 23 '19 at 0:03
• you are absolutely right. The range being $M$ means that the null-space is $N−M$ not zero, so there are cases like yours where we obtain zero for a non-zero input. Sorry for the silly confusion, I just confused the dimensions. Check my updated answer (now with your same assumption!) – Oriol B Nov 23 '19 at 22:22

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.

• $x$ is a (complex valued in general) vector, right ? so the product $x R_x^{-1} x$ does not define anything. I think you meant $x^H R_x^{-1} x$ ? – Fat32 Nov 22 '19 at 16:28
• You're welcome, see my followup. – Cedron Dawg Nov 22 '19 at 20:19
• I've added an update, check it out. – Cedron Dawg Nov 22 '19 at 21:58
• If $N \ge M$ then $min(M,N) = M$. Why did you change that? – Cedron Dawg Nov 23 '19 at 23:14
• Of course your assumption was $N \leq M$ so I just forgot to change this part (it was a mere typo) – Oriol B Nov 24 '19 at 9:33