How can we show/prove that a rank-$1$ matrix is non-convex?

Question

In my optimization problem, I have a matrix $X = v v^H$ where $H$ denotes the complex conjugate transpose and $v \in \mathbb C^n$. This is a rank-$1$ matrix. In the published literature, it is mentioned that rank-$1$ matrix is also non-convex but I am unable to understand this. Can someone explain this to me why rank-$1$ matrix is also non-convex?

Answer 1

Let me give this a go since I was wondering the same thing. Are you asking why the set of rank 1 matrices is not convex? Let's consider the following:

$x_1 = [0,1]^T$, $x_2 = [1,0]^T$. Therefore $x_1x_1^T = \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix}$ and $x_2x_2^T = \begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix}$.

We note at this point that both $x_1x_1^T$ and $x_2x_2^T$ fall into the set of rank-1 matrices. However, their combination does not, and we can demonstrate this:

$\theta x_1x_1^T + (1-\theta)x_2x_2^T = \begin{bmatrix} 1-\theta & 0 \\ 0 & \theta \end{bmatrix}$, which is a rank-2 matrix. We cannot express this in the form $x_0 x_0^T$, (because what would $x_0$ be to allow me to get $x_0 x_0^T$ as seen above?) and it does not fall into the same set as the first two matrices $x_1x_1^T$ and $x_2x_2^T$.

Therefore the set of rank-1 matrices is not convex.