Increase rank by stacking two matrices?

Question

Let $A$ be an $m\times n$ integer matrix with $m<n$ satisfying that all $m\times m$ submatrices of $A$ have rank $m$.

Let $A_i$ be a matrix obtained from $A$ by deleting $i$th column for $i=1,...,n$.

Is that true that $$rank\begin{pmatrix} A_i \\ A_jP \end{pmatrix}>rank(A_i)=m$$ for any $(n-1)\times (n-1)$ permutation matrix $P$ and $i\neq j$? (If necessary, we may assume $m\le n-2$.)

A first try might be is that true that $$rank\begin{pmatrix} A_i \\ A_j\end{pmatrix}>rank(A_i)=m$$ for any $i\neq j$?

Answer 1

The conjecture is false if there are no restrictions on $A, i, j$. Here is a counter-example for $m=3, n=6$. It is obvious how to generalize this to other $m,n$.

$$ A= \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 8 & 16 & 32 \\ 1 & 3 & 9 & 27 & 81 & 243 \end{pmatrix}\\ \,\,\\ B = \begin{pmatrix} A_6 \\ A_1\end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 4 & 8 & 16 \\ 1 & 3 & 9 & 27 & 81\\ 1 & 1 & 1 & 1 & 1 \\ 2 & 4 & 8 & 16 & 32 \\ 3 & 9 & 27 & 81 & 243 \\ \end{pmatrix}\\ $$

$B$ has rank $m=3$ because its row $4 =$ row $1$, and row $5=2\times $row $2$, and row $6=3\times $ row $3$.

What happened is that $A_i$ has rank $m$ and a null space $N_i$ of dimension $n-1-m$, and same for $A_j$. The null space of $B$ is the intersection $N_i \cap N_j$, because only vectors in the intersection can make every row of $B$ vanish. Thus, $B$ will have rank $> m$ unless $N_i = N_j$. This obviously won't happen for most $A, i, j$, but sadly, highly contrived counter-examples exist, as shown above.

---

Some simple restrictions might prevent this from happening though, e.g.

For any $A, i, j$, if $j = i \pm 1$ i.e. they are neighboring columns, then $rank(B) > m$.

Proof: Without loss we assume $j = i + 1$, then $A_i$ and $A_j$ will differ in each one's $i$th column only. Now pick any $m$ columns which are different from $i$. Since these $m$ columns are independent, we can write the $i$th column as a linear combination of these $m$ columns, i.e. we can find $v \in N_i$ where $v$ has a non-zero entry at $i$, and the only other non-zero entries are among the $m$.

However, this vector is certainly $\notin N_j$ since the $i$th column is different in $A_j$ and cannot be written as the same linear combination of the other $m$ columns (which are equal in $A_i$ and $A_j$). So $N_i \neq N_j$ and we have $dim(nullspace(B)) < n-1-m$ and hence $rank(B) > m$.