3
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ @OriolB Your comment is hard to decipher. I get how you derived it, I'm just a bit puzzled about what it says. $\endgroup$ – Cedron Dawg Nov 22 '19 at 22:04
  • $\begingroup$ Sorry about that @cedron, I incorporated my comment in your reply inside the yellow box since it was hard to format as a comment. $\endgroup$ – Oriol B Nov 22 '19 at 22:06
  • $\begingroup$ @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. $\endgroup$ – Cedron Dawg Nov 22 '19 at 22:11
  • $\begingroup$ @OriolB Ponder my latest appendum. $\endgroup$ – Cedron Dawg Nov 23 '19 at 0:03
  • $\begingroup$ 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!) $\endgroup$ – Oriol B Nov 23 '19 at 22:22
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ $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$ ? $\endgroup$ – Fat32 Nov 22 '19 at 16:28
  • $\begingroup$ You're welcome, see my followup. $\endgroup$ – Cedron Dawg Nov 22 '19 at 20:19
  • $\begingroup$ I've added an update, check it out. $\endgroup$ – Cedron Dawg Nov 22 '19 at 21:58
  • $\begingroup$ If $N \ge M$ then $min(M,N) = M$. Why did you change that? $\endgroup$ – Cedron Dawg Nov 23 '19 at 23:14
  • $\begingroup$ Of course your assumption was $N \leq M$ so I just forgot to change this part (it was a mere typo) $\endgroup$ – Oriol B Nov 24 '19 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.