Rank of a partitioned matrix with an identity matrix

Question

Suppose $X$ is any real-valued rectangular matrix. $C$ is a matrix with zeros and 1s.

How can I show that

$$ Rank \left[ \begin{array}{c|c} X & I_m - XC \\ \end{array} \right] = m $$

Answer 1

Presumably, $m$ is meant to be the number of rows in $X$.

Note that the $m \times n$ matrix $A$ has rank $m$ (full row rank) if and only if $Ax = b$ has a solution for every $b \in \Bbb R^n$. In this case we note that for any $b$, the vector $x = (Cb,b)$ is such that $$ \pmatrix{X & I - XC}x = \pmatrix{X & I - XC} \pmatrix{Cb\\ b} = XCB + (I - XC)b = b. $$ So, your matrix indeed has full row rank.

Answer 2

@Omnomnomnom has given a solution in terms of row-rank $\rho_r$; here's one in terms of column-rank $\rho_c$.

Note that for any matrices $M, N$ each column of the product $MN$ is a linear combination of the columns of $M$. Then by performing column operations we obtain

$$ \rho_c \begin{bmatrix} X & I-XC\\ \end{bmatrix} = \rho_c \begin{bmatrix} X & I-XC+XC\\ \end{bmatrix} = \rho_c \begin{bmatrix} X & I\\ \end{bmatrix} = \rho_c \begin{bmatrix} X-IX & I\\ \end{bmatrix} = \rho_c \begin{bmatrix} O & I\\ \end{bmatrix} =m. $$