Rank of a Submatrix

Question

Let $$B=\left[\begin{array}{c |cc} 1 & \begin{array}{ccc}0 & \cdots & 0\end{array} \\ \hline \begin{array}{c}0\\ \vdots\\0\end{array} & B' \\ \end{array}\right],$$ where $B'$ is an $m \times n$ submatrix of $B$. Prove that if $rank(B)=r$, then $rank(B')=r-1$.

Here is an attempt at a proof. As you will notice, I am not sure how to finish it, so hopefully someone might help me with finishing it.

First note that $f : F^n \to F^{n+1}$ defined by

$$f(v) = f(\begin{bmatrix} v_1 \\ \vdots \\ v_n \\ \end{bmatrix}) = \begin{bmatrix} 0 \\ v_1 \\ \vdots \\ v_n \\ \end{bmatrix}$$

is a injective linear operator and therefore maps linearly independent sets to linearly independent sets. For simplicity, we may write $f(v) = \begin{bmatrix} 0 \\ v \\ \end{bmatrix}$

Let $B = [e_1 ~|~ b_1 ~|~ b_2 ~|~ \dots ~|~ b_n]$, where $e_1$ is the first column of $B$, $b_2$ the second, etc; similarly, let $B' = [b_1' ~|~ b_2' ~|~ \dots ~|~ b_n']$. Then it can easily be seen that $b_i = f(b_i')$. Moreover, let $S$ denote the maximal set of linearly independent columns of $B$, and let $S'$ denote the same thing of $B'$; then we have $rank(B)=|S|$ and $rank(B')=|S'|$. Since the columns of $B$ have zeros in their first entry, clearly the first column $e_1$ cannot be in the span of the remaining columns and is therefore included in $S$.

Here is the part I am having trouble with. I am trying to argue that $S = \{e_1\} \cup f(S')$. The sets involved in the union are clearly disjoint, since $e_1 \notin f(F^n)$, so $|S| = 1 + |f(S')|$. Since injective maps preserve cardinality, we have $|f(S')| = |S'| = rank(B')$, and the problem follows immediately.

I am being a knucklehead; I can't figure out how to finish this last step. I could use some help.

EDIT: When you read this post, if you could please check that the dimensions of the matrix are consistent with the spaces over which $f$ acts, I would appreciate that, since I often mess up those details.

Answer 1

Your approach is good, but the hint points to the opposite direction.

Let $\{b_{i_1},b_{i_2},\dots,b_{i_r}\}$ be a maximal linearly independent set of columns of $B$, with $1\le i_1<i_2<\dots<i_r\le n$.

If $i_1\ne1$, we can add $b_1$ to the set, getting a linearly independent set, because $b_1$ does not belong to the span of the columns from $2$ to $n$. This would contradict maximality and therefore $i_1=1$.

The set $\{b_{i_2},\dots,b_{i_r}\}$ is linearly independent, and so is the corresponding set of columns of $B'$ (why?).

Suppose the rank of $B'$ is not $r-1$. Then the rank of $B'$ is greater than $r-1$. Thus there are $r$ columns of $B'$ that form a linearly independent set. Adding $0$ at the top of these columns gives a linearly independent set of columns of $B$ (your map $f$ plays a role here). Adding to this set the first column $b_1$ yields a linearly independent set of columns of $B$ of size $r+1$: contradiction.

Answer 2

A set of columns $c_1, \ldots, c_k$ of $B'$ are linearly dependent iff the columns $\pmatrix{1\cr 0\cr}, \pmatrix{0\cr c_1\cr}, \ldots, \pmatrix{0\cr c_k}$ of $B$ are linearly dependent.

One way is obvious: if $\sum_j a_j c_k = 0$ then $0 \pmatrix{1\cr 0\cr} + \sum_j a_j \pmatrix{0\cr c_j} = 0$.

The other way is almost as obvious: if $a_0 \pmatrix{1\cr 0\cr} + \sum_j a_j \pmatrix{0\cr c_j} = 0$, then by looking at the first entries we must have $a_0 = 0$ and by looking at the others $\sum_j a_j c_j = 0$.

Answer 3

Another way is to use $$rank(A+B) \leq rank(A) + rank(B)$$ and the fact that rank of sub-matrix can't exceed the original matrix. I leave the fun of finding the solution to you.