Characterization of matrices with same column spaces

Question

Given $G = \begin{pmatrix} A & B \\ B^T & C \end{pmatrix}$ symmetric positive semi-definite and $B$ symmetric positive semi-definite, is there a way to impose that \begin{equation} ColumnSpace(C) = ColumnSpace(B) \end{equation} with convex constaints (linear constraint, linear matrix inequalities, etc) ?

Answer 1

This is not possible.

Note that since the number of columns of $B$ and $C$ are the same, they span the same column space if and only if it is possible to express $B$ as linear combinations of the columns of $C$.

This is equivalent to say that there exists a matrix $Z$ such that $CZ-B=0$. However, this matrix $Z$ needs to satisfy a few conditions to avoid certain pathological problems such as the case where $B=0$ and $C\ne0$. Noting that if one can express $B$ in terms of $C$, that means that the other round is possible and, therefore, that $Z$ must be invertible.

Unfortunately, invertibility is not a convex constraint since $Z$ is not (semi)definite. However, if you assume that no column of $B$ and $C$ is zero, then it is possible to show that there will be an invertible solution $Z$ to the inequality. The difficulty is that there may be an infinite number of solution to $CZ-B=0$ and the solver may pick one that is non-invertible. Finding $Z$ such that $||K||_1$ is minimum seems to do the trick to choose the "simplest" of those solutions. (i.e. the sparsest one) which will be invertible.