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.


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.


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$.


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.


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.