TITLE: What is the criterion for a matrix containing vectors and their permutations being invertible?
QUESTION [5 upvotes]: Consider the matrix $A\in\mathbb{R}^{m\times 2m}$. Let any arbitrary choice of $m$ columns of $A$ be linearly independent. Together with a permutation $P\in\mathcal{P_{2m}}$, one can build the matrix $$B:=\begin{bmatrix}A\\AP\end{bmatrix}\in\mathbb{R}^{2m\times 2m}\text{ .}$$
Which conditions does $P$ need to satisfy, so that $B$ is invertible? 
I would like to have just a criterion for the matrix P.
The rest of this post shows an example and conjectures I already have from experiments. I had a look at $4\times 4$, $6\times 6$, $8\times 8$ and $10\times 10$ matrices $A$, all permutations $P$ and the determinants of $B$.
Example
$$B_1=\begin{bmatrix}
a_1&b_1&c_1&d_1\\
a_2&b_2&c_2&d_2\\\hline
\mathbf{b_1}&\mathbf{a_1}&c_1&d_1\\
\mathbf{b_2}&\mathbf{a_2}&c_2&d_2\\
\end{bmatrix}\qquad ,\qquad
B_2=\begin{bmatrix}
a_1&b_1&c_1&d_1\\
a_2&b_2&c_2&d_2\\\hline
\mathbf{c_1}&\mathbf{a_1}&\mathbf{b_1}&d_1\\
\mathbf{c_2}&\mathbf{a_2}&\mathbf{b_2}&d_2\\
\end{bmatrix}$$
$B_1$ is always singular ($\det B_1=0$) and $B_2$ always invertible ($\det B_2\neq 0$).
Conjectures
What helps is looking at derangements. A derangement is a permutation which does not assign an element its original position. It is said that the elements are deranged.
Conjecture 1:
Matrix $B$ is invertible if at least $2m-1$ columns of $A$ are deranged by $P$.
Conjecture 2:
The matrix $B$ is regular if at least $m+1$ columns of $A$ are deranged by $P$ and the permutation consists of a cycle of at least size $m$.
Both conjectures are no "if and only if" relations. There are definitely permutations which do not fulfill the criterion but lead to invertible $B$'s. What I also saw when I was investigating small $m$'s was, that all permutations with the same number and sizes of cycles always lead to the same result. In the example $B_1$ has one cycle of size 2 and every permutation with a single cycle and size 2 leads to a singular matrix. $B_2$'s permutation has one cycle of size 3 and every such permutation lead to an invertible matrix $B_2$.
I would be happy if I could show at least conjecture 1 for all $m$. Conjecture 2 would be even better. But I don't have an idea how. Any other criterion of $P$ leading to an invertible matrix $B$ are fine as well.

REPLY [3 votes]: Sorry, these are perhaps two remarks, but they are a bit large for a comment.
Generally, you may multiply $B$ by $\begin{bmatrix}X^{-1}&0\\0&X^{-1}\end{bmatrix}$ where $X$ is the left half of $A$, thus assuming that $A=\begin{bmatrix}E&Y\end{bmatrix}$. In this case, the formula
$$
  \det\begin{bmatrix}E&Y\\Z&T\end{bmatrix}
  =\det\begin{bmatrix}E&Y\\0&T-ZY\end{bmatrix}
  =\det(T-ZY)
$$
may be helpful.
Specifically, I do not see that $B_2$ is always invertible. Putting $Y=\begin{bmatrix}-1&1\\-1&2\end{bmatrix}$ (all pairs of columns of $A$ are independent!), then you get
$$
  \det B_2=\det\begin{bmatrix}1&0&-1&1\\0&1&-1&2\\-1&1&0&1\\-1&0&1&2\end{bmatrix}=0
$$
(the formula above may help). This seems to disprove both conjectures...
{"set_name": "stack_exchange", "score": 5, "question_id": 221630}